4487. Can you answer these queries VI - #include <Seter> - using namespace Orz;
4487. Can you answer these queries VI
http://www.spoj.pl/problems/GSS6/
| ID | DATE | USER | PROBLEM | RESULT | TIME | MEM | LANG |
|---|---|---|---|---|---|---|---|
| 6073829 | 2011-11-23 13:25:38 | Seter | Can you answer these queries VI |
accepted edit run |
8.28 | 12M |
C |
1A有木有！超开心……
某日看到fotile主席用4种方法在虐这题，深深被震撼，再次Orz！最神的一种方法是主席自己create的SBT进化版——主席树！主席说主席树可以秒杀一切神题！！！Orz！！！
这个是我A掉的第一个有一堆卫星数据的Splay题……留个念吧……
我对这种题木的唯一感觉就是Splay……空节点的特判我用null.l=null.r=-100000trick掉了，但是没敢插入头尾节点……所以在移动到第一个数前/最后一个数后的时候进行特判了囧……
Q的时候切掉1..i-1,j+1..s，update后输出整棵树的max就可以了……最后再将1..i-1接到最左边，j+1..s接到最右边……虽然这样有点慢但是我想不出更好的方法了T^T
彻底变傻X……可以splay第j个数，如果i=j则就是根的值，否则在左子树中splay第i个数，然后切掉它的左子树和根的右子树，update后再直接接回去……不过这样还是没tbl神犇快……改成C++就快了一点……不开O2其实还是C++快啊……
对一个节点（线段）记录lmax,rmax,max,sum。这四个用节点上的数推一下就可以了，很简单的……
注意改好后对修改的节点update啊……
另外没什么好说的……代码超长……70行TAT
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 | #include <stdio.h>#include <string.h>#define maxn 200000#define max(a,b) ((a)>(b)?(a):(b))typedef struct _Splay{struct _Splay *c[2],*f;int s,v,l,r,m,a;}Splay,*PSplay;Splay null,st[maxn],*stp=st,*r=&null;char str[3000000],*p=str;inline PSplay update(PSplay x){ int ml=max(x->c[1]->l,0),mr=max(x->c[0]->r,0); x->s=x->c[0]->s+x->c[1]->s+1; x->a=x->c[0]->a+x->v+x->c[1]->a; x->l=max(x->c[0]->l,x->c[0]->a+x->v+ml); x->r=max(x->c[1]->r,x->c[1]->a+x->v+mr); return x->m=max(max(x->c[0]->m,x->c[1]->m),ml+x->v+mr),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; update((fx->f=x)->c[!c]=fx); }return x;}inline PSplay splay(PSplay x){ if(x==&null||x->f==&null)return update(x); for(;x->f!=&null;rot(x))if(x->f->f!=&null)rot((x->f->f->c[1]==x->f)==(x->f->c[1]==x)?x->f:x); return update(x);}inline PSplay Join(PSplay r1,PSplay r2){ if(r1==&null)return r2;if(r2==&null)return r1; while(r1->c[1]!=&null)r1=r1->c[1]; return update((splay(r1)->c[1]=r2)->f=r1);}inline PSplay Rank(PSplay r,int x){ _Bool c; if(x<=0||r->s<x)return &null; for(;;r=r->c[c])if(x==r->c[0]->s+1)return splay(r);else if(c=x>r->c[0]->s)x-=r->c[0]->s+1;}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;}main(){ int i,j;PSplay t1,t2;fread(str,1,3000000,stdin); for((null.f=null.c[0]=null.c[1]=&null)->m=null.l=null.r=-1000000,i=getint();i--;stp->v=getint(),r=update(stp++))if((stp->c[0]=r)!=(stp->c[1]=&null))r->f=stp;r->f=&null; while(1){ while(*++p<'A'||*p>'Z')if(!*p)return 0; if(*p=='Q'){ i=getint();t2=(r=Rank(r,j=getint()))->c[1]; if(i==j){printf("%d\n",r->v);continue;} r->c[1]=&null; if(i!=1){ r->c[0]->f=&null; t1=(r->c[0]=Rank(r->c[0],i))->c[0]; (r->c[0]->f=r)->c[0]->c[0]=&null; update(r->c[0]); }printf("%d\n",update(r)->m); if(i!=1)r->c[0]->c[0]=t1,update(r->c[0]); r->c[1]=t2;update(r); }else if(*p=='R')update(((r=Rank(r,getint()))->v=getint(),r)); else if(*p=='D'){ r=Rank(r,getint()); r->c[0]->f=r->c[1]->f=&null; r=Join(r->c[0],r->c[1]); }else if(stp->c[0]=stp->c[1]=&null,i=getint(),stp->v=getint(),i==r->s+1){ while(r->c[1]!=&null)r=r->c[1]; r=splay((stp->f=r)->c[1]=stp++); }else{ stp->c[0]=(stp->f=r=Rank(r,i))->c[0]; update(r->c[0]=r->c[0]->f=stp++);update(r); } }} |
By Seter
2011年12月02日 17:07
敢问fotile主席……鄙人弱菜神犇勿喷。
2011年12月02日 18:09
高一大神