首页 > 代码库 > HDU 4441 Queue Sequence（splay）
HDU 4441 Queue Sequence（splay）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4441
题意：一个数列，三种操作：（1）插入：找到没在当前数列中的最小的正整数i，将其插在位置p之后，并将-i插入某个位置使得满足先进先出（i表示进，-i表示出），这个位置尽量靠右；（2）删除：删掉数字i以及-i；（3）询问：查询i和-i之间的数字的和。
思路：对于没在数列中的数字可以用一个set直接维护。i的插入是正常的splay操作。对于-i的插入，我们首先找到i之前有几个正数，比如有x个，那么-i必然是插在第x+1个负数的前面，因此在splay节点中要保存负数的个数。删除和查询都是splay正常操作。
struct node{ i64 sum; int val; int size[2]; int Size; node *c[2],*p;};node a[N],*root,*nullNode;int cnt;void pushUp(node *p){ if(p==nullNode) return; p->Size=1; p->sum=p->val; p->size[0]=p->size[1]=0; if(p->val>0) p->size[1]++; else if(p->val<0) p->size[0]++; if(p->c[0]!=nullNode) { p->Size+=p->c[0]->Size; p->sum+=p->c[0]->sum; p->size[0]+=p->c[0]->size[0]; p->size[1]+=p->c[0]->size[1]; } if(p->c[1]!=nullNode) { p->Size+=p->c[1]->Size; p->sum+=p->c[1]->sum; p->size[0]+=p->c[1]->size[0]; p->size[1]+=p->c[1]->size[1]; }}int ok(node *p){ return p!=nullNode&&(p!=&a[1])&&(p!=&a[2]);}node *newNode(int val,node *p){ node *e=&a[val>0?val:-val+100000]; e->c[0]=e->c[1]=nullNode; e->p=p; e->Size=1; e->val=e->sum=val; e->size[0]=e->size[1]=0; if(val>0) e->size[1]++; else e->size[0]++; return e;}void init(){ nullNode=new node(); nullNode->size[0]=nullNode->size[1]=0; nullNode->Size=0; nullNode->sum=0; nullNode->c[0]=nullNode->c[1]=nullNode->p=nullNode; root=new node(); root->c[0]=root->c[1]=root->p=nullNode; root->sum=0; root->val=0; root->size[0]=root->size[1]=0; root->Size=1; root->c[1]=new node(); root->c[1]->c[0]=root->c[1]->c[1]=nullNode; root->c[1]->p=root; root->c[1]->sum=root->c[1]->val=-1; root->c[1]->Size=1; root->c[1]->size[0]=root->c[1]->size[1]=0; root->c[1]->size[0]++; pushUp(root);}void zig(node *x){ node *p=x->p,*q=p->p; p->c[0]=x->c[1]; if(x->c[1]!=nullNode) x->c[1]->p=p; x->c[1]=p; p->p=x; x->p=q; if(q!=nullNode) { if(q->c[0]==p) q->c[0]=x; else q->c[1]=x; } pushUp(p); pushUp(x); if(root==p) root=x;}void zag(node *x){ node *p=x->p,*q=p->p; p->c[1]=x->c[0]; if(x->c[0]!=nullNode) x->c[0]->p=p; x->c[0]=p; p->p=x; x->p=q; if(q!=nullNode) { if(q->c[0]==p) q->c[0]=x; else q->c[1]=x; } pushUp(p); pushUp(x); if(root==p) root=x;}void splay(node *x,node *goal){ while(x->p!=goal) { if(x->p->p!=goal) { if(x->p->p->c[0]==x->p) { if(x->p->c[0]==x) zig(x->p),zig(x); else zag(x),zig(x); } else { if(x->p->c[1]==x) zag(x->p),zag(x); else zig(x),zag(x); } } else { if(x->p->c[0]==x) zig(x); else zag(x); } }}void select(int k,node *goal){ node *p=root; while(k!=p->c[0]->Size+1) { if(k<=p->c[0]->Size) p=p->c[0]; else { k-=1+p->c[0]->Size; p=p->c[1]; } } splay(p,goal);}int curNodeNum;void insert(int p,int val){ select(p,nullNode); select(p+1,root); node *e=newNode(val,root->c[1]); root->c[1]->c[0]=e; splay(e,nullNode); curNodeNum++;}node *getPre(node *u){ splay(u,nullNode); u=u->c[0]; while(u->c[1]!=nullNode) u=u->c[1]; return u;}node *getNext(node *u){ splay(u,nullNode); u=u->c[1]; while(u->c[0]!=nullNode) u=u->c[0]; return u;}node *getKth0(int k){ node *p=root; while(1) { if(p->c[0]->size[0]>=k) p=p->c[0]; else if(p->c[0]->size[0]+1==k) { if(p->val<0) return p; k-=p->c[0]->size[0]; p=p->c[1]; } else { k-=p->c[0]->size[0]; if(p->val<0) k--; p=p->c[1]; } }}void del(node *p){ node *u=getPre(p); node *v=getNext(p); splay(u,nullNode); splay(v,root); root->c[1]->c[0]=nullNode; splay(root->c[1],nullNode); curNodeNum--;}set<int> S;int n;void deal(){ S.clear(); init(); curNodeNum=2; int i; for(i=1;i<=100000;i++) S.insert(i); while(n--) { char op[10]; int p; scanf("%s%d",op,&p); if(op[0]==‘i‘) { int t=*S.begin(); S.erase(t); insert(p+1,t); splay(a+t,nullNode); int num=0; if(root->c[0]!=nullNode) num+=root->c[0]->size[1]; if(root->val>0) num++; node *u=getKth0(num); node *v=getPre(u); splay(v,nullNode); splay(u,root); node *tmp=newNode(-t,root->c[1]); root->c[1]->c[0]=tmp; splay(tmp,nullNode); curNodeNum++; } else if(op[0]==‘r‘) { S.insert(p); del(a+p); del(a+p+100000); } else { node *u=a+p; node *v=a+p+100000; splay(u,nullNode); splay(v,root); i64 sum=root->c[1]->c[0]->sum; output(sum); puts(""); } }}int main(){ int num=0; while(scanf("%d",&n)!=-1) { printf("Case #%d:\n",++num); deal(); }}
HDU 4441 Queue Sequence（splay）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。