首页 > 代码库 > POJ 3580 (伸展树)
POJ 3580 (伸展树)
题目链接: http://poj.org/problem?id=3580
题目大意：对一个序列进行以下六种操作。输出MIN操作的结果。
解题思路：
六个操作，完美诠释了伸展树有多么吊。注意，默认使用Lazy标记，在pushdown中维护。
ADD操作：为x~y元素加一个d值。首先用split切出x~y元素。然后改变给切出的root->add，root->min，root->v。再merge进原序列。
REVERSE操作：把x~y元素反转。首先用split切出x~y元素，然后改变root->flip标记。再merge进原序列。
REVOLVE操作：把x~y元素偏移T位。注意T可以为负。负向左，正向右。
首先对T进行修正。T=(T%(r-l+1)+(r-l+1))%(r-l+1))，参考自cxlove大神，这样正负方向就一致了，而且解决了没必要的偏移。
这样问题就转化为把[x,y]序列变成left+[y-T+1,y]+[x,y-T]+right，同样参考自cxlove大神。
那么只要split出[x,y-T]就行了。
INSERT操作：在第x元素后插入P。首先切出[1,x],然后merge这个新的P元素,再merge右段。
注意一下，虽然伸展树是意义上的BST，但是伸展树一旦为了维护原有序列顺序，则可以不再遵循BST的左<=中<=右原则。
这里的INSERT就是，把P元素merge到右边是防止BST维护改变顺序（merge只对left进行BST维护）。
DELETE操作：切出左右两段，merge即可。
MIN操作：求x~y元素最小值。依赖于pushup(也就是maintain)，每次变动都要维护root-v，root->left,root->right三部分的最小值。
首先切出[x,y]，root->minn就是结果。
额外吐槽一下build操作，首先在0号位置加一个inf大的前置结点，这样就可以split出[x,y]这个段了，如果没有前置结点，则应该这么切[1,x-1],当x=1时就完蛋了。
build(0,n)。这样0号点就被放在了最左边。build的时候为了保持原序列顺序，根据位置进行二分build。在最初把伸展树的高度给压下去。
因为伸展树的平衡性能实在太差，如果build成链，那么就要完蛋啦。
#include "cstdio"#include "cstdlib"#include "time.h"#include "queue"#include "vector"#include "cstring"using namespace std;struct node{ node *ch[2]; long long v,s,minn,flip,add; node() {s=flip=add=0;minn=1<<29;} void maintain() { s=1; s+=ch[0]->s; s+=ch[1]->s; minn=min(v,min(ch[0]->minn,ch[1]->minn)); } void push_down() { if(flip) { flip = 0; swap(ch[0], ch[1]); ch[0]->flip = !ch[0]->flip; ch[1]->flip = !ch[1]->flip; } if(add) { ch[0]->add+=add;ch[1]->add+=add; ch[0]->v+=add;ch[1]->v+=add; ch[0]->minn+=add;ch[1]->minn+=add; add=0; } } int cmp(int x) { int d = x-ch[0]->s; if(d == 1) return -1; return d <= 0 ? 0 : 1; }};node *null=new node();node *root;node *left,*mid,*right,*oo;vector<int> ans;long long arr[200005];void rotate(node* &o,int d){ node *k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; o->maintain();k->maintain(); o=k;}void splay(node* &o,int k){ o->push_down(); int d=o->cmp(k); if(d==1) k-=o->ch[0]->s+1; if(d!=-1) { node *p=o->ch[d]; p->push_down(); int d2=p->cmp(k); if(d2!=-1) { int k2=(d2==0?k:k-p->ch[0]->s-1); splay(p->ch[d2],k2); if(d==d2) rotate(o,d^1);else rotate(o->ch[d],d); } rotate(o,d^1); }}node *merge(node* left,node *right){ splay(left,left->s); left->ch[1]=right; left->maintain(); return left;}void split(node *o, int k, node *&left, node *&right){ splay(o, k); left = o; right = o->ch[1]; o->ch[1] = null; left->maintain();}void build(int l,int r,node* &o){ if(l>r) return; int mid=(l+r)>>1; o=new node;o->v=arr[mid];o->minn=arr[mid];o->s=1;o->ch[0]=o->ch[1]=null; build(l,mid-1,o->ch[0]); build(mid+1,r,o->ch[1]); o->maintain();}void INSERT(int x,int v){ split(root,x+1,left,oo); node *tt=new node; tt->v=v;tt->s=1;tt->minn=v;tt->ch[0]=tt->ch[1]=null; root=merge(merge(left,tt),oo);}void DELETE(int x){ split(root,x,left,oo); split(oo,1,mid,right); root=merge(left,right);}void MIN(int a,int b){ split(root,a,left,oo); split(oo,b-a+1,mid,right); printf("%lld\n",mid->minn); root=merge(merge(left,mid),right);}void REVOLVE(int a,int b,int c){ if(!c) return; node *tt; split(root,a,left,oo); split(oo,b-a+1,mid,right); //切出[a,b] split(mid,b-c-a+1,tt,oo);//切出[a,b-c] tt=merge(oo,tt);//合并即可 root=merge(merge(left,tt),right);}void ADD(int a,int b,int c){ //切出[a,b] if(!c) return; split(root,a,left,oo); split(oo,b-a+1,mid,right); mid->add+=c; mid->v+=c; mid->minn+=c; root=merge(merge(left,mid),right);}void REVERSE(int a,int b){ split(root,a,left,oo); split(oo,b-a+1,mid,right); mid->flip^=1; root=merge(merge(left,mid),right);}int main(){ //freopen("0.in","r",stdin); //freopen("0.out","w",stdout); int n,m,l,r,x; char cmd[10]; arr[0]=1<<29;//前置结点防止干扰 while(scanf("%d",&n)!=EOF) { for(int i=1;i<=n;i++) scanf("%lld",&arr[i]); build(0,n,root); scanf("%d",&m); while(m--) { scanf("%s",cmd); if(!strcmp(cmd,"ADD")) { scanf("%d%d%d",&l,&r,&x); ADD(l,r,x); } if(!strcmp(cmd,"REVERSE")) { scanf("%d%d",&l,&r); REVERSE(l,r); } if(!strcmp(cmd,"REVOLVE")) { scanf("%d%d%d",&l,&r,&x); REVOLVE(l,r,(x%(r-l+1)+(r-l+1))%(r-l+1)); } if(!strcmp(cmd,"INSERT")) { scanf("%d%d",&l,&x); INSERT(l,x); } if(!strcmp(cmd,"DELETE")) { scanf("%d",&l); DELETE(l); } if(!strcmp(cmd,"MIN")) { scanf("%d%d",&l,&r); MIN(l,r); } } root=left=right=oo=null; }}
| 13476518 | neopenx | 3580 | Accepted | 8680K | 1047MS | C++ | 4510B | 2014-09-25 17:10:36 |
POJ 3580 (伸展树)