http://poj.org/problem?id=3580

伸展樹的各種操作 收口袋大法好 一開始看模板上額外在維護數(shù)列的二叉樹上又加了兩個節(jié)點 root和root->ch[1] 覺得很蒙逼 但是這樣保證了每次取前驅(qū)后繼時不會越界 這兩個節(jié)點的角色就相當(dāng)于數(shù)組中的啊a[0]和a[n+1]

題目很坑逼 數(shù)據(jù)范圍不給 循環(huán)次數(shù)可能是負數(shù)

還要注意longlong不能用max/min 必須手寫

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; #define ll long long #define N 0x3f3f3f3f3f3f3f3fll getmin(ll a,ll b); struct node; node *null;struct node {node *fa,*ch[2];int sz,rev;ll val,minn,laz;void wipe(){fa=ch[0]=ch[1]=null;sz=1,val=0,minn=N,laz=0,rev=0;}int getd(){return fa->ch[1]==this;}void setc(node *tmp,int d){ch[d]=tmp;tmp->fa=this;}void add(ll tlaz){if(this==null) return;val+=tlaz,minn+=tlaz,laz+=tlaz;}void reverse(){if(this==null) return;swap(ch[0],ch[1]);rev^=1;}void pushup(){sz=ch[0]->sz+ch[1]->sz+1;minn=N;if(ch[0]!=null) minn=min(minn,min(ch[0]->val,ch[0]->minn));if(ch[1]!=null) minn=min(minn,min(ch[1]->val,ch[1]->minn));}void pushdown(){if(laz!=0){ch[0]->add(laz);ch[1]->add(laz);laz=0;}if(rev!=0){ch[0]->reverse();ch[1]->reverse();rev=0;}} };node pool[200010]; node *root,*tail; ll ary[100010]; int n,q;void build(node *&cur,node *fa,int l,int r) {int m;if(l>r) return;m=(l+r)/2;cur=tail++;cur->wipe();cur->fa=fa;cur->val=ary[m],cur->minn=N,cur->laz=0,cur->rev=0;build(cur->ch[0],cur,l,m-1);build(cur->ch[1],cur,m+1,r);cur->pushup(); }void init() {node *tmp;tail=pool;null=tail++;null->fa=null->ch[0]=null->ch[1]=null;null->sz=0,null->val=0,null->minn=N,null->laz=0,null->rev=0;tmp=tail++;tmp->wipe();root=tmp;tmp=tail++;tmp->wipe();root->setc(tmp,1);build(root->ch[1]->ch[0],root->ch[1],1,n);root->ch[1]->pushup();root->pushup(); }node *getkth(node *r,int k) {node *cur;cur=r;cur->pushdown();while(cur->ch[0]->sz+1!=k){if(cur->ch[0]->sz+1>k){cur=cur->ch[0];}else{k-=(cur->ch[0]->sz+1);cur=cur->ch[1];}cur->pushdown();}return cur; }void rotate(node *cur) {node *f,*ff;int c,cc;f=cur->fa,ff=cur->fa->fa;f->pushdown();cur->pushdown();c=cur->getd(),cc=f->getd();f->setc(cur->ch[!c],c);cur->setc(f,!c);if(ff->ch[cc]==f) ff->setc(cur,cc);else cur->fa=ff;f->pushup(); }void splay(node *&root,node *tar,node *cur) {while(cur->fa!=tar){if(cur->fa->fa==tar) rotate(cur);else{cur->fa->fa->pushdown();cur->fa->pushdown();cur->pushdown();if(cur->getd()==cur->fa->getd()) rotate(cur->fa);else rotate(cur);rotate(cur);}}cur->pushup();if(tar==null) root=cur; }void insert(node *&cur,node *fa,ll val) {cur=tail++;cur->wipe();cur->fa=fa;cur->val=val,cur->minn=N,cur->laz=0,cur->rev=0; } ll getmin(ll a,ll b) {if(a<b) return a;else return b; }void show() {node *ptr;int i;printf("******\n");for(i=2;i<=n+1;i++){ptr=getkth(root,i);printf("%I64d ",ptr->val);}printf("\n");printf("******\n"); }int main() {ll val,len;int i,l,r;char op[10];scanf("%d",&n);for(i=1;i<=n;i++){scanf("%I64d",&ary[i]);}init();scanf("%d",&q);while(q--){scanf("%s",op);if(strcmp(op,"ADD")==0){scanf("%d%d%I64d",&l,&r,&val);splay(root,null,getkth(root,l));splay(root,root,getkth(root,r+2));root->ch[1]->ch[0]->add(val);root->ch[1]->pushup();root->pushup();}else if(strcmp(op,"REVERSE")==0){scanf("%d%d",&l,&r);splay(root,null,getkth(root,l));splay(root,root,getkth(root,r+2));root->ch[1]->ch[0]->reverse();root->ch[1]->pushup();root->pushup();}else if(strcmp(op,"REVOLVE")==0){scanf("%d%d%I64d",&l,&r,&val);//val=max(val,0ll);len=r-l+1;if(len==1) continue;val+=1000000000ll*len;if(val%len!=0){val%=len;//printf("^^^%I64d^^^\n",val);splay(root,null,getkth(root,l));splay(root,root,getkth(root,r+2));root->ch[1]->ch[0]->reverse();root->ch[1]->pushup();root->pushup();if(val>1){splay(root,null,getkth(root,l));splay(root,root,getkth(root,l+val+1));root->ch[1]->ch[0]->reverse();root->ch[1]->pushup();root->pushup();}if(r-l-val+1>1){splay(root,null,getkth(root,l+val));splay(root,root,getkth(root,r+2));root->ch[1]->ch[0]->reverse();root->ch[1]->pushup();root->pushup();}}}else if(strcmp(op,"INSERT")==0){scanf("%d%I64d",&l,&val);splay(root,null,getkth(root,l+1));splay(root,root,getkth(root,l+2));insert(root->ch[1]->ch[0],root->ch[1],val);root->ch[1]->pushup();root->pushup();}else if(strcmp(op,"DELETE")==0){scanf("%d",&l);splay(root,null,getkth(root,l));splay(root,root,getkth(root,l+2));root->ch[1]->ch[0]=null;root->ch[1]->pushup();root->pushup();}else{scanf("%d%d",&l,&r);splay(root,null,getkth(root,l));splay(root,root,getkth(root,r+2));printf("%I64d\n",getmin(root->ch[1]->ch[0]->val,root->ch[1]->ch[0]->minn));//printf("$$$%lld %lld$$$\n",root->ch[1]->ch[0]->val,root->ch[1]->ch[0]->minn);}//show();}return 0; }/* 10 1 4 7 8 9 6 3 2 5 10 10 REVERSE 3 8 REVOLVE 5 10 -2147483647 DELETE 1 INSERT 0 5 INSERT 10 4 REVOLVE 1 11 -1111111111 REVOLVE 1 11 5 ADD 8 11 2 MIN 1 6 MIN 8 1110 1 2 3 4 5 6 7 8 9 10 15 ADD 4 8 3 MIN 5 7 MIN 7 10 REVERSE 2 5 MIN 2 6 MIN 2 3 INSERT 3 4 MIN 3 4 MIN 5 10 DELETE 6 MIN 3 5 MIN 4 4 REVOLVE 3 6 7 MIN 5 8 MIN 7 10 */

?

總結(jié)

以上是生活随笔為你收集整理的SuperMemo POJ - 3580的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。