2333: [SCOI2011]棘手的操作 - #include <Seter> - using namespace Orz;
2333: [SCOI2011]棘手的操作
http://www.zybbs.org/JudgeOnline/problem.php?id=2333
| RunID | User | Problem | Result | Memory | Time | Language | Code_Length | Submit_Time |
| 219596 | Seter | 2333 | Accepted | 22824 kb | 748 ms | C/Edit | 3032 B | 2012-03-07 20:53:06 |
做了两个多小时，被傻逼错误各种屠，最搞笑的是我没下传标记拍了几组N,M=10000的随机数据都是对的。。。
这题的标准解法是离线算法。。就是先全部U起来，然后处理出DFS序就可以发现每次操作的都是一段区间。。。线段树乱搞就可以了。。好像挺好写的。。。
但是像我这么弱的只能写写在线算法。。其中F3只要全局维护一个堆就行了，A3只要搞个全局变量表示所有数加了多少，那么剩下的东西，由于要合并两堆+取最大值，自然而然想到了可并堆。。。要打标记表示某个点的子树加了多少。。。
可并堆我只会左偏树，但当左链很长的时候好像会囧掉（而且还要支持减小一个数！）。。。于是我选用了随机堆。。。就是合并的时候随机一个儿子合并，这样可以让堆的高度期望在logN级。。那就可以在logN时间内Sink/Swim/将一个点及其祖先们的标记全部下传了。。。
嘛。。。随机的话按照左右左右左右。。。这么随也很快。。。
表示长期不写Splay现在连个rotate操作都写了30+分钟。。。我真是弱暴了。。。
随机数据比Tim快很多。。。看来这个数据还是下了点心思的，说不定就卡掉了左偏树。。。很久以前我写过启发式合并TLE了（不过我不排除我写的程序会死循环的可能）。。。当然如果神犇们要虐配对堆/F-Heap的话说不定也行（二项堆貌似不行）。。。我反正不会。。。
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 | #include<stdio.h>#define H struct Heap#define updt(x) a[x]=a[x<<1]>a[x<<1^1]?a[x<<1]:a[x<<1^1]H{H*c[2],*f;int v,a}T[300000],*S[300000];inline H*tran(H*x){if(x->a){x->v+=x->a;if(x->c[0])x->c[0]->a+=x->a;if(x->c[1])x->c[1]->a+=x->a;x->a=0;}return x;}int n,d,s,f[300000],a[1048576],M;_Bool C;char str[10000000],*p=str,*o=str;inline void UPDT(x){for(x+=M;x>>=1;)updt(x);}inline find(x){ int y=f[x],r=y; while(r!=f[r])r=f[r]; while((f[x]=r)!=(x=y))y=f[y]; return r;}H*Merge(H*x,H*y){ H*t;_Bool c;if(!y)return x;if(!x)return y; tran(x);tran(y); if(x->v<y->v)t=x,x=y,y=t; c=C;C=!C;return(x->c[c]=Merge(x->c[c],y))->f=x;}inline H*Root(H*x){s=0;while(x)S[s++]=x,x=x->f;return S[s-1];}inline void rot(H*x){ H*t=x->f,*x0,*x1;_Bool c=t->c[1]==x; if(t->f)t->f->c[t->f->c[1]==t]=x; if(x0=x->c[0])x->c[0]->f=t;if(x1=x->c[1])x->c[1]->f=t; x->f=t->f;(t->f=x)->c[c]=t;if(x->c[!c]=t->c[!c])x->c[!c]->f=x; t->c[0]=x0;t->c[1]=x1;}inline H*Swim(H*x){while(x->f)if(tran(x->f)->v<tran(x)->v)rot(x);else return x;return x;}inline void Sink(H*x){ while(1){ if(tran(x)->c[0])tran(x->c[0]);if(x->c[1])tran(x->c[1]); if(!x->c[0]||x->c[0]->v<=x->v){ if(!x->c[1]||x->c[1]->v<=x->v)return; else rot(x->c[1]); }else if(!x->c[1]||x->c[1]->v<=x->v)rot(x->c[0]); else rot(x->c[x->c[1]->v>x->c[0]->v]); }}inline getint(){ int re=0;_Bool k; while(*p!='-'&&(*p<'0'||*p>'9'))p++; for(k=*p=='-'&&p++;*p>='0'&&*p<='9';)re=re*10+*p++-48; return k?-re:re;}inline void print(x){ char buf[10],*p=buf; if(x<0)x=-x,*o++='-';if(!x)*o++=48; else{while(x)*p++=x%10+48,x/=10;while(p--!=buf)*o++=*p;} *o++='\n';}main(){ int i=-1,j,q;H*x0,*x1;fread(p,1,10000000,stdin); for(M=1<<32-__builtin_clz((n=getint())-1);++i!=n;)T[f[i]=i].v=a[M+i]=getint(); for(i--;++i!=M;)a[M+i]=1<<31;while(--i)updt(i); for(q=getint();q--;){ while(*p!='A'&&*p!='U'&&*p!='F')p++; if(*p=='A'){ if(*++p=='1'){ p++;i=getint()-1;T[i].v+=j=getint(); if(j<0){ if(T[i].f)x0=x1=0;else x0=T[i].c[0],x1=T[i].c[1]; Sink(T+i); if(!T[i].f)a[M+find(i)]=T[i].v,UPDT(f[i]); else if(x0&&!x0->f)a[M+find(i)]=x0->v,UPDT(f[i]); else if(x1&&!x1->f)a[M+find(i)]=x1->v,UPDT(f[i]); }else if(j&&!Swim(T+i)->f)a[M+find(i)]=T[i].v,UPDT(f[i]); }else if(*p++=='2')i=getint()-1,Root(T+i)->a+=getint(),a[M+find(i)]=tran(S[s-1])->v,UPDT(f[i]); else d+=getint(); }else if(*p=='F'){ if(*++p=='1'){ p++;Root(T+(i=getint()-1)); while(s--)tran(S[s]);print(T[i].v+d); }else if(*p++=='2')print(tran(Root(T+getint()-1))->v+d); else print(a[1]+d); }else if((i=find(getint()-1))!=(j=find(getint()-1))){ if(a[M+i]<a[M+j])i^=j^=i^=j; f[j]=i,Merge(Root(T+i),Root(T+j)),a[M+j]=1<<31,UPDT(j); } }return fwrite(str,1,o-str,stdout),0;} |
By Seter
评论 (0)