题意: 给你三个数:L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000),表示有一长度为L的板(1~L),
有T种颜色(1~T),然后有O个操作,初始板1~L的颜色为1,"C A B C"表示在区间A,B图上C颜色, "P A B" 表示询问
A,B区间有几种不同的颜色。
#include
#include
#include
#include
#include
#define M 100000 #define LL long long using namespace std; struct Tree { int l,r,c;//c代表颜色,若区间(l,r)的颜色不止一种则c=-1; }tree[M*3]; int color[35];//在查询时,若[A,B]区间内出现过某种颜色k,则color[k]=true; void build(int id,int l,int r) { tree[id].l=l; tree[id].r=r; tree[id].c=1;//初始颜色为1 if(l==r) return ; build(id*2,l,(l+r)/2); build(id*2+1,(l+r)/2+1,r); } void update(int id,int l,int r,int co) { if(tree[id].l>=l&&tree[id].r<=r)//(l,r)完全覆盖id节点 { tree[id].c=co; return; } if(tree[id].c>0)//一直wa在这里 { tree[id*2].c=tree[id*2+1].c=tree[id].c; tree[id].c=-1; } tree[id].c=-1;//没有完全覆盖 int mid=(tree[id].l+tree[id].r)/2; if(mid>=r) update(2*id,l,r,co); else if(mid
0) { color[tree[id].c]=true; return; } if(tree[id].l==tree[id].r) return; int mid=(tree[id].l+tree[id].r)/2; if(mid>=r) P(id*2,l,r); else if(mid
b) swap(a,b); update(1,a,b,c); } else { scanf("%d%d",&a,&b); if(a>b) swap(a,b); memset(color,false,sizeof(color)); P(1,a,b); printf("%d\n",Ans(t)); } } return 0; }