1861: [Zjoi2006]Book 书架 - #include <Seter> - using namespace Orz;
1861: [Zjoi2006]Book 书架
http://www.zybbs.org/JudgeOnline/problem.php?id=1861
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 174521 | Seter | 1861 | Accepted | 4588 kb | 624 ms | C/Edit | 2408 B | 2011-11-18 20:37:53 |
一开始写这道题的时候总觉得自己的Splay模板的Join和Remove操作有问题……然后弄了半天各种WA囧，最后发现是题中的Insert操作交换时没更新指针……不过原来的Splay模板还真的有问题……Remove后可能存在未update的节点……改好就A了……
Query：Rank第i个节点后输出此节点的编号
Ask：Splay编号i对应节点后输出根的左子树的大小
Top/Bottom：删除编号i对应节点，找到最左/右边的节点，将编号i对应节点插入。（我的Splay在n=1时会出错，所以我特判了下）
Insert：0就不变，否则找到编号i对应节点的前/后继，与编号i对应节点交换，注意交换后的指针更新！
PS：Remove神马操作之后全部splay或者update一下……避免节点未update……
由于我感嚼我的Splay模板还有问题……所以就不挂Splay模板了囧……
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 | #include <stdio.h>#include <string.h>#define maxn 80000typedef struct _Splay{struct _Splay *c[2],*f;int s,v;}Splay,*PSplay;Splay null,st[maxn],*pt[maxn],*r;int n,m;char str[2000000],*p=str;inline PSplay update(PSplay x){return x->s=x->c[0]->s+x->c[1]->s+1,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]=splay(r2))->f=r1);}inline PSplay Remove(PSplay x){ PSplay t=x->f;_Bool c=t->c[1]==x; if(x->c[0]==&null&&x->c[1]==&null)x->f->c[c]=&null; else if((x->c[0]->f=x->c[1]->f=&null)!=((t=Join(x->c[0],x->c[1]))->f=x->f))x->f->c[c]=t; return splay(t);}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,c;fread(str,1,2000000,stdin); r=null.f=null.c[0]=null.c[1]=&null; for(i=n=getint(),m=getint();i--;(r=st+i)->c[1]=&null){ (pt[st[i].v=getint()-1]=st+i)->s=r->s+1; if((st[i].c[0]=r)!=&null)r->f=st+i; }for(st[0].f=&null;m--;){ while(*p<'A'||*p>'Z')p++; if(*p=='Q')printf("%d\n",(r=Rank(r,getint()))->v+1); else if(*p=='A')printf("%d\n",(r=splay(pt[getint()-1]))->c[0]->s); else if(*p=='I'){ if(!(i=getint()-1,c=getint()))continue; for(r=splay(pt[i])->c[!(c=c!=1)];r->c[c]!=&null;r=r->c[c]); c=r->v;pt[pt[r->v=i]->v=c]=pt[i];pt[i]=r;r=splay(r); }else if(n!=1){ for(c=*p=='B',r=Remove(pt[i=getint()-1]);r->c[c]!=&null;r=r->c[c]); ((pt[i]->f=r)->c[c]=pt[i])->s=1;pt[i]->c[0]=pt[i]->c[1]=&null; r=splay(pt[i]); } }return 0;} |
By Seter
2022年12月18日 21:03
Accidentally I have come across this website and little bit confused about the details shared here. The details center for rheumatology you have shared here are not familiar to me. I am looking here to more updates regarding that and hope that more details will be explained here soon. Keep sharing more updates here.