依然是线段树，和POJ 2528比较类似，增加了查询某段区间内颜色种类数目的要求，这里由于颜色总数T值比较小(1<=T<=30)，因此可以用一个int以位相量的形式来表示某段区间包含的颜色情况。这里lazy tag用来表示结点的区间是否只含一种颜色。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
#include<cstdio> int l,t,o,ml; char s[2]; struct node { int c; char b; node *l,*r; }mem[1000000],*root; void ins(int l,int r,int L,int R,int k,node *p) { if(l==L&&r==R) { p->b=1; p->c=k; return; } if(p->b) { p->b=0; if(!p->l) { p->l=&mem[ml++]; p->l->l=p->l->r=0; p->r=&mem[ml++]; p->r->l=p->r->r=0; } p->l->b=1; p->l->c=p->c; p->r->b=1; p->r->c=p->c; } int m=L+R>>1; if(r<=m) ins(l,r,L,m,k,p->l); else if(l>=m+1) ins(l,r,m+1,R,k,p->r); else { ins(l,m,L,m,k,p->l); ins(m+1,r,m+1,R,k,p->r); } p->c=p->l->c|p->r->c; } int ask(int l,int r,int L,int R,node *p) { if(p->b||l==L&&r==R) return p->c; int m=L+R>>1; if(r<=m) return ask(l,r,L,m,p->l); if(l>=m+1) return ask(l,r,m+1,R,p->r); return ask(l,m,L,m,p->l)|ask(m+1,r,m+1,R,p->r); } int main() { int i,j,k; while(~scanf("%d%d%d",&l,&t,&o)) { ml=0; root=&mem[ml++]; root->c=1; root->b=1; root->l=root->r=0; while(o--) { scanf("%s",s); if(s[0]=='C') { scanf("%d%d%d",&i,&j,&k); if(i>j) i^=j^=i^=j; --k; ins(i,j,1,l,1<<k,root); } else { scanf("%d%d",&i,&j); if(i>j) i^=j^=i^=j; k=ask(i,j,1,l,root); for(i=0;k;k>>=1) i+=k&1; printf("%d\n",i); } } } return 0; } |
用C++最快也只有266ms，但代码量只有第一名a3616001(79ms)的一半……这个可以用作自我安慰吗？