【题意】两种操作，[L,R]种新的树（不覆盖原来的），或查询[L,R]树的种类数。n<=50000。

【算法】树状数组||线段树

【题解】这题可以用主席树实现……不过因为不覆盖原来的，所以有更简单的方法。

括号法，对于每个K=1的操作标记左右括号的位置。

对于每个K=2的操作，答案就是right前面的左括号数量-(left-1)前面的右括号数量、

用树状数组或线段树优化。

注意数组在传递给函数时是传递地址，即在函数中修改即相当于修改原数组。

线段树：

#include
      
       const int maxn=50010;struct treess{
    int l,r,sum[3];}t[maxn*3];int n,m,a,b,c;void build(int k,int l,int r){    t[k].l=l;t[k].r=r;    if(l!=r)     {        int mid=(l+r)>>1;        build(k<<1,l,mid);        build(k<<1|1,mid+1,r);     }}void insert(int k,int x,int kind){    int left=t[k].l,right=t[k].r;    if(left==right)t[k].sum[kind]++;     else      {          int mid=(left+right)>>1;          if(x<=mid)insert(k<<1,x,kind);           else insert(k<<1|1,x,kind);          t[k].sum[kind]=t[k<<1].sum[kind]+t[k<<1|1].sum[kind];      }}int ask(int k,int l,int r,int kind){    int left=t[k].l,right=t[k].r;    if(l<=left&&right<=r)return t[k].sum[kind];    int mid=(left+right)>>1,ans=0;    if(l<=mid)ans=ask(k<<1,l,r,kind);    if(r>mid)ans+=ask(k<<1|1,l,r,kind);    return ans;}int main(){    scanf("%d%d",&n,&m);    build(1,1,n);    for(int i=1;i<=m;i++)     {         scanf("%d%d%d",&a,&b,&c);         if(a==1)          {              insert(1,b,1);              insert(1,c,2);         }        else printf("%d\n",ask(1,1,c,1)-ask(1,1,b-1,2));     }    return 0;}
      

树状数组：

#include
      
       #define lowbit(x) x&-xconst int maxn=50010;int left[maxn],right[maxn],n,m,a,b,c;void add(int a[],int x){
     for(int i=x;i<=n;i+=lowbit(i))a[i]++;}int search(int a[],int x){    int ans=0;    for(int i=x;i>0;i-=lowbit(i))ans+=a[i];    return ans;}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=m;i++)     {         scanf("%d%d%d",&a,&b,&c);         if(a==1)          {              add(left,b);              add(right,c);         }        else printf("%d\n",search(left,c)-search(right,b-1));     }    return 0;}