线段树差分经典题。

解：

对于题目中要求的维护区间颜色种数，暴力维护必定不可取。于是，我们考虑线段树的性质：从下向上维护左右区间信息。

那么，我们可不可以利用这一点来简单维护它的颜色种类数呢？

我们可以维护一组地雷（颜色）的开头和结尾。

显然，我们这样可以任意求出任意区间的开头数和结尾数。那么，复杂的区间修改就变成了单点修改。

注意线段树的性质，也就是说，即使它的开头不在询问区间，只要它覆盖了，就一定不会遗漏。

那么，套用差分公式，r-l+1,即

query_s(1,r,1)-query_e(1,l-1,1)

其中，query_s是查询开头数，query_e是查询结尾数。

问题得解。

代码：

#include
     
      #include
      
       using namespace std;int n,m,opt,x,y;struct node{    int l,r,st,ed;}tr[500000];void build(int l,int r,int x){    tr[x].l=l;tr[x].r=r;    if(l==r){        tr[x].st=tr[x].ed=0;        return;    }int mid=l+r>>1;    build(l,mid,x<<1);    build(mid+1,r,x<<1|1);    tr[x].ed=tr[x<<1].ed+tr[x<<1|1].ed;    tr[x].st=tr[x<<1].st+tr[x<<1|1].st;}void change_s(int goal,int x){    if(tr[x].l==tr[x].r)tr[x].st++;    else{        int mid=(tr[x].l+tr[x].r)>>1;        if(goal<=mid)change_s(goal,x<<1);        else change_s(goal,x<<1|1);        tr[x].st=tr[x<<1].st+tr[x<<1|1].st;    }}void change_e(int goal,int x){    if(tr[x].l==tr[x].r)tr[x].ed++;    else{        int mid=(tr[x].l+tr[x].r)>>1;        if(goal<=mid)change_e(goal,x<<1);        else change_e(goal,x<<1|1);        tr[x].ed=tr[x<<1].ed+tr[x<<1|1].ed;    }}int query_s(int l,int r,int x){    if(tr[x].l==l&&tr[x].r==r)return tr[x].st;    else{        int mid=(tr[x].l+tr[x].r)>>1;        if(r<=mid)return query_s(l,r,x<<1);        else if(mid
       
        >1;        if(r<=mid)return query_e(l,r,x<<1);        else if(mid