题目链接：https://www.luogu.org/problem/P2161
题意：有两种操作，操作A是在区间l,r上染色(每次染的颜色都不同)，同时输出那些与之重叠的颜色的个数并将该颜色完全清空，操作B是统计区间目前还有多少种颜色。
分析：用线段树来做，只用到区间修改，每次修改时都找到只有一种颜色的区间，如果这个颜色还没被删除，就计数并删除。删除可以直接用一个del数组来实现
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int mod=1e9+7; const int maxn=2e5+7; #define ls rt<<1 #define rs rt<<1|1 int cnt=0;//当前颜色的编号 int ans=0;//记录此时还有多少种颜色 int res;//记录一次A操作删去了多少种颜色 struct node{ char opt[2]; int l,r; }a[maxn]; bool same[maxn<<2];//代表该区间内是否同色，1为同色 int tag[maxn<<2];//lazy标记，记录的是颜色 bool del[maxn];//用来标记一种颜色是否被删除 void build(int rt,int l,int r){ same[rt]=1;tag[rt]=0; if(l==r) return ; int mid=(l+r)>>1; build(ls,l,mid); build(rs,mid+1,r); } void pushdown(int l,int r,int rt){ same[rt]=0;//关键！！！！ //能下传就说明一定不是同色 if(!tag[rt])return; //标记下放 tag[ls]=tag[rs]=tag[rt]; tag[rt]=0; } void find(int l,int r,int rt){ if(same[rt]==1){ if(!del[tag[rt]]&&tag[rt]) ans--,res++; del[tag[rt]]=1; tag[rt]=cnt;//记录颜色 return; } int mid=(l+r)>>1; find(l,mid,ls);find(mid+1,r,rs); same[rt]=1;tag[rt]=cnt; } void modify(int l,int r,int s,int t,int rt){ if(s<=l&&r<=t){ find(l,r,rt); return ; } pushdown(l,r,rt); int mid=(l+r)>>1; if(s<=mid) modify(l,mid,s,t,ls); if(t>mid) modify(mid+1,r,s,t,rs); } int main(){ int n;scanf("%d",&n); int st=inf,ed=0;//记录左右端点 for(int i=1;i<=n;i++){ scanf("%s",a[i].opt); if(a[i].opt[0]=='A'){ scanf("%d%d",&a[i].l,&a[i].r); st=min(st,a[i].l);ed=max(ed,a[i].r); } } build(1,st,ed); for(int i=1;i<=n;i++){ if(a[i].opt[0]=='A'){ ++ans;++cnt;res=0; modify(st,ed,a[i].l,a[i].r,1); printf("%d ",res); } else printf("%d ",ans); } return 0; }