每个区间看做一个颜色，难点在于如何把一个区间都删掉，用一个数组标记被删掉的颜色，然后无视掉这种颜色就可以，好技巧
代码抄的 tag和c好像弄反了
标记这个区间是否为一种颜色，修改时把区间内所有种类的颜色标记即可
#include<bits/stdc++.h> #define ls (x<<1) #define rs (x<<1|1) #define mid ((l+r)>>1) using namespace std; const int maxn=100009; int n,ans; struct node{ int tg,c; }t[maxn<<2]; bool del[200009]; int tot; inline void pd(int x,int l,int r){ t[x].c=0; if(!t[x].tg)return; t[ls].tg=t[rs].tg=t[x].tg; t[x].tg=0; } inline void build(int x,int l,int r){ t[x].c=1;t[x].tg=0; if(l==r)return; build(ls,l,mid);build(rs,mid+1,r); } inline void change(int x,int l,int r,int v){ if(t[x].c==1){ if(!del[t[x].tg]&&t[x].tg)--ans,++tot; del[t[x].tg]=1; t[x].tg=v; return ; } change(ls,l,mid,v);change(rs,mid+1,r,v); t[x].tg=v;t[x].c=1; } inline void changex(int x,int l,int r,int L,int R,int v){ if(L<=l&&r<=R){change(x,l,r,v);return;} pd(x,l,r); if(L<=mid)changex(ls,l,mid,L,R,v); if(R>mid)changex(rs,mid+1,r,L,R,v); } int main(){ scanf("%d",&n);char op[2]; build(1,1,100000);int cnt=0; for(int i=1,l,r;i<=n;i++){ scanf("%s",op); if(op[0]=='A'){ scanf("%d%d",&l,&r);tot=0; ++ans;changex(1,1,100000,l,r,++cnt); printf("%d ",tot); } else printf("%d ",ans); } }