2120: 数颜色 - #include <Seter> - using namespace Orz;
2120: 数颜色
http://www.zybbs.org/JudgeOnline/problem.php?id=2120
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 176421 | Seter | 2120 | Accepted | 12076 kb | 812 ms | C/Edit | 2912 B | 2011-12-02 12:44:43 |
10000个数，10000个操作。每次修改一个数/询问一段区间内不同的数有几个。
有点难想……树状数组线段树套平衡树。每个数第一次出现时随便改成一个负数（我改成了这个数的相反数以避免重值），之后改成前一次出现的位置。询问的时候查找一个区间中比左端点小的数有几个（就是没有前继/是区间中第一次出现的数的个数）。
然后这个可以用平衡树维护。由于询问是对于区间的，所以用树状数组线段树套上……
将点i的颜色修改为j的时候要修改i的后继，颜色j对于i的后继和i本身，这里还要用个平衡树维护每个颜色的位置……对于前/后继不存在的情况还要特判……超麻烦……
我的程序又慢又长……不过好歹是第一个树套树的程序……做个纪念！
Update:改成了树状数组……然后Find的时候如果相等就直接返回……瞬间快了……
但是tim大神SegTree+Splay600+MS！！太神了！！不过18K+的代码长度……
至于长度嘛……为什么2K+的代码会被你们写成6K+……
NZM大神说XXXXXXXX必须离线BIT套BIT乱搞……但是我先去试试我的SB方法……
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 | #include <stdio.h>typedef struct _Splay{struct _Splay *c[2],*f;int s,v;}Splay,*PSplay;Splay null,st[16][10000],*a[10001],*c[1000000];char str[300000],*p=str;int n,k[1000000],b[10000];inline PSplay updt(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+1,x;}inline PSplay near(PSplay x,_Bool c){for(x=x->c[c];x->c[!c]!=&null;x=x->c[!c]);return x;}inline PSplay extr(PSplay x,_Bool c){while(x->c[c]!=&null)x=x->c[c];return x;}inline PSplay node(PSplay x,int v){x->f=x->c[0]=x->c[1]=&null;x->v=v;x->s=1;return x;}inline PSplay rot(PSplay x){ PSplay fx=x->f,ffx=fx->f; _Bool c=fx->c[1]==x,fc=ffx->c[1]==fx; if(fx!=&null){ if((fx->c[c]=x->c[!c])!=&null)fx->c[c]->f=fx; if((x->f=ffx)!=&null)ffx->c[fc]=x; updt((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x,PSplay p){ if(x==&null)return x;for(;x->f!=p;rot(x))if(x->f->f!=p)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return updt(x);}inline PSplay Join(PSplay x,PSplay y){ if(x==&null)return y;if(y==&null)return x;x=splay(extr(x,1),&null); return updt((x->c[1]=splay(y,&null))->f=x);}inline PSplay Remove(PSplay x){x=splay(x,&null);x->c[0]->f=x->c[1]->f=&null;return Join(x->c[0],x->c[1]);}inline PSplay Insert(PSplay r,PSplay x){ _Bool c;if(!r||r==&null)return x; while(r->c[c=r->v<x->v]!=&null)r=r->c[c]; (r->c[c]=x)->f=r;return splay(x,&null);}inline PSplay Find(PSplay r,int x){ PSplay ans=&null;for(;r!=&null;r=r->c[r->v<x])if(r->v==x)return splay(r,&null);else if(r->v>x&&(ans==&null||r->v<ans->v))ans=r; return splay(ans,&null);}inline void BitInsert(i,x){int y=0,s=i-1;for(;i<=n;i+=i&-i)a[i]=Insert(a[i],node(st[y++]+s,x));}inline void BitUpdate(i,x){int y=0,s=i-1;for(;i<=n;i+=i&-i)a[i]=Remove(st[y]+s),a[i]=Insert(a[i],node(st[y++]+s,x));}inline BitQuery(i,y){int ans=0;PSplay x;for(;i;i-=i&-i)ans+=(x=Find(a[i],y))==&null?a[i]->s:(a[i]=x)->c[0]->s;return ans;}inline getint(){ int re=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}main(){ int i=-1,j=0,t;PSplay x;fread(p,1,300000,stdin); null.f=null.c[0]=null.c[1]=&null;n=getint(); for(t=getint();++i!=n;k[b[i]]=i+1){ BitInsert(i+1,k[b[i]=getint()-1]?k[b[i]]:-b[i]); c[b[i]]=Insert(c[b[i]],node(st[15]+i,i+1)); }while(t--)if(*++p=='Q')printf("%d\n",BitQuery(getint(),i=getint())-BitQuery(i-1,i)); else if(*p=='R'){ if(b[i=getint()-1]==(j=getint()-1))continue; if(!c[j])c[j]=&null;c[b[i]]=Remove(st[15]+i); if((x=near(st[15]+i,1))!=&null)BitUpdate(x->v,st[0][i].v); if((x=Find(c[j],i+1))==&null)BitUpdate(i+1,c[j]==&null?-j:(c[j]=splay(extr(c[j],1),&null))->v); else BitUpdate((c[j]=x)->v,i+1),BitUpdate(i+1,c[j]->c[0]==&null?-j:near(c[j],0)->v); c[b[i]=j]=Insert(c[j],node(st[15]+i,i+1)); }else t++;return 0;} |
By Seter
评论 (0)