Description

校门外有很多树，有苹果树，香蕉树，有会扔石头的，有可以吃掉补充体力的……如今学校决定在某个时刻在某一段种上一种树，保证任一时刻不会出现两段相同种类的树，现有两个操作：K=1，读入l，r表示在区间[l,r]中种上一种树，每次操作种的树的种类都不同。K=2，读入l，r表示在区间[l,r]之间能见到多少种树（l,r>0）。

---

Input

第一行n,m，表示道路总长为n，共有m个操作。接下来m行，为m个操作。

---

Output

对于每个k=2输出一个答案。

---

Hint

对于20%的数据保证，n,m<=100。 对于60%的数据保证，n <=1000,m<=50000。 对于100%的数据保证，n,m<=50000。

---

Solution

用两个区间的树状数组分别维护起点数量和终点数量。那么查询的时候ans就等于r前面的起点数量减去l-1前面的终点数量。因为l-1前面就已经终点了的话，这种树就不包含在查询的这个区间里面。

#include
    
     #include
     
      #include
      
       #include
       
        #define maxn 50005#define lowbit(x) (x&(-x))#define int long longusing namespace std;int c1[maxn],c2[maxn],c3[maxn],c4[maxn];int n,m,x,y,z;void doAdd(int x,int dd){    int f=x;    while(x<=n){        c1[x]+=f*dd;        c3[x]+=dd;        x+=lowbit(x);    }}void doadd(int x,int dd){    int f=x;    while(x<=n){        c2[x]+=f*dd;        c4[x]+=dd;        x+=lowbit(x);    }}int doFinD(int x){    int f=x,ans=0;    while(x>0){        ans+=(f+1)*c3[x]-c1[x];        x-=lowbit(x);    }    return ans;}int dofinD(int x){    int f=x,ans=0;    while(x>0){        ans+=(f+1)*c4[x]-c2[x];        x-=lowbit(x);    }    return ans;}signed main(){    scanf("%lld%lld",&n,&m);    for(int i=1;i<=m;i++){        scanf("%lld",&x);        if(x==1){            scanf("%lld%lld",&y,&z);            doAdd(y,1);            doAdd(y+1,-1);            doadd(z,1);            doadd(z+1,-1);         }        else if(x==2){            scanf("%lld%lld",&y,&z);            printf("%lld\n",doFinD(z)-dofinD(y-1));        }    }    return 0;}