在做完郁闷的出纳员、宠物收养所等题之后,COGS上本蒟蒻和Rivendell神再也没有找到纯旋转式treap可以做的题,要么是区间类问题,要么就是各种树套树。。。
于是决定学一些解决区间问题的平衡树方法,按理说应当学splay,但莫名其妙地学上了非旋转式treap,我也是呵呵了。。。
介绍一下原理,原来的treap是通过左旋右旋来维护最小堆性质,但在此处,由于是区间操作,我们需要截出一整段区间(也就是一段treap),并且在重新插入回去的时候,不能够破坏最小堆性质,于是我们可以用merge(合并操作,注意:此处的merge操作与旋转式treap的merge并不相同)和split(拆分操作)来维护,具体做法是:
1、把某数插入到第k个位置:用split把treap拆分为前k-1位和后size-k+1位,然后以此节点的value新建立一个节点,依次将这三部分merge起来就好了。
2、把某数从第k个位置删除:同样,先用split把treap拆分为和后size-k+1位,再把后size-k+1位拆分为第k位和后size-k+2位,在将前k-1位和后size-k+2位merge起来就好了。
3、翻转,平移,求和,修改值等操作几乎都是把所需区间截取出来,特别注意的是翻转、修改值等操作需要懒惰标记,方法与线段树大同小异。
。。。。。。上习题
POJ 3580 SuperMemo
非旋转式treap第一题(我在Rivendell神的带领下,上手就是与文本编辑器等经典题目不在一个档次上的题= =),其实差不多也是模版题,只是ADD和REVERSE操作需要懒惰标记,MIN操作需要像线段树一样的updata(注意要把标记加上),REVOLVE需要截取三个区间,然后就没有然后了。。。code:
#include<iostream> #include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> #include<algorithm> using namespace std; struct treap_node{ treap_node *left,*right; int val,fix,size,wgt,minn,adel,rdel; treap_node(int val): val(val) {left=right=NULL; fix=rand(); wgt=size=1; minn=val; rdel=adel=0; } int lsize() { if (left) return left->size; else return 0; } int rsize() { if (right) return right->size; else return 0; } void updata() { minn=val; if (left) minn=min(minn,left->minn+left->adel); if (right) minn=min(minn,right->minn+right->adel); } void pushdown() { treap_node *temp; if (adel) { minn+=adel; val+=adel; if (left) left->adel+=adel; if (right) right->adel+=adel; adel=0; } if (rdel%2) { if (left==NULL||right==NULL) { if (left==NULL) { left=right; right=NULL; } else { right=left; left=NULL; } } else { temp=left; left=right; right=temp; } if (left) left->rdel+=rdel; if (right) right->rdel+=rdel; rdel=0; } updata(); } void Maintain() { size=wgt; size+=lsize()+rsize(); } }; int n,m; treap_node *root; typedef pair<treap_node*,treap_node*> droot; treap_node *merge(treap_node *a,treap_node *b) { if (!a) return b; if (!b) return a; a->pushdown(); b->pushdown(); a->updata(); b->updata(); if (a->fix<b->fix) { a->right=merge(a->right,b); a->updata(); a->Maintain(); return a; } else { b->left=merge(a,b->left); b->updata(); b->Maintain(); return b; } } droot split(treap_node *a,int k) { if (!a) return droot(NULL,NULL); droot y; a->pushdown(); a->updata(); if (a->lsize()>=k) { y=split(a->left,k); a->left=y.second; a->updata(); a->Maintain(); y.second=a; } else { y=split(a->right,k-a->lsize()-1); a->right=y.first; a->updata(); a->Maintain(); y.first=a; } return y; } void insert(int k,int value) { treap_node *temp; droot y=split(root,k); temp=new treap_node(value); root=merge(merge(y.first,temp),y.second); } void del(int k) { droot x,y; x=split(root,k-1); y=split(x.second,1); root=merge(x.first,y.second); } int main() { char s[20]; droot ai,bi,ci; treap_node *temp; int i,x,y,a,L,t; scanf("%d",&n); for (i=1;i<=n;++i) { scanf("%d",&x); insert(i,x); } scanf("%d",&m); for (i=1;i<=m;++i) { scanf("%s",&s); if (s[0]=='A') { scanf("%d%d%d",&x,&y,&a); ai=split(root,x-1); bi=split(ai.second,y-x+1); bi.first->adel+=a; ai.second=merge(bi.first,bi.second); root=merge(ai.first,ai.second); } if (s[0]=='I') { scanf("%d%d",&x,&a); insert(x,a); } if (s[0]=='D') { scanf("%d",&x); del(x); } if (s[0]=='R') { if (s[3]=='E') { scanf("%d%d",&x,&y); ai=split(root,x-1); bi=split(ai.second,y-x+1); bi.first->rdel++; ai.second=merge(bi.first,bi.second); root=merge(ai.first,ai.second); } if (s[3]=='O') { scanf("%d%d%d",&x,&y,&a); L=y-x+1; a=(a%L+L)%L; ai=split(root,x-1); bi=split(ai.second,L); ci=split(bi.first,L-a); bi.first=merge(ci.second,ci.first); ai.second=merge(bi.first,bi.second); root=merge(ai.first,ai.second); } } if (s[0]=='M') { scanf("%d%d",&x,&y); ai=split(root,x-1); bi=split(ai.second,y-x+1); t=bi.first->minn; ai.second=merge(bi.first,bi.second); root=merge(ai.first,ai.second); printf("%d\n",t); } } }
COGS 330 NOI 2003 文本编辑器
一道赤裸裸的模版题,但是insert需要逐个插入,尽管目测时间复杂度极高,但我的程序却比fye神快了1+sec,比Rivendell快了2+sec,直接导致了两人心理变态症发作,目前还在丧心病狂地吐槽,我也是很不(kai)解(xin)。。。 code:
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> using namespace std; struct treap_node{ treap_node *left,*right; int wgt,size,fix; char val; treap_node(char val): val(val) {left=right=NULL; size=wgt=1; fix=rand(); } int lsize() { if (left) return left->size; else return 0; } int rsize() { if (right) return right->size; else return 0; } void Maintain() { size=wgt; size+=lsize()+rsize(); } }; int n; treap_node *root; typedef pair <treap_node*,treap_node*> droot; void print(treap_node *a) { if (a->left) print(a->left); printf("%c",a->val); if (a->right) print(a->right); } treap_node *merge(treap_node *a,treap_node *b) { if (!a) return b; if (!b) return a; if (a->fix<b->fix) { a->right=merge(a->right,b); a->Maintain(); return a; } else { b->left=merge(a,b->left); b->Maintain(); return b; } } droot split(treap_node *x,int k) { if (!x) return droot(NULL,NULL); droot y; if (x->lsize()>=k) { y=split(x->left,k); x->left=y.second; x->Maintain(); y.second=x; } else { y=split(x->right,k-x->lsize()-1); x->right=y.first; x->Maintain(); y.first=x; } return y; } void insert(int k,int l) { droot y; char c; int i; treap_node *temp; y=split(root,k); for (i=1;i<=l;++i) { scanf("%c",&c); while (c<32||c>126) scanf("%c",&c); temp=new treap_node(c); y.first=merge(y.first,temp); } root=merge(y.first,y.second); } void del(int k,int l) { droot a,b; a=split(root,k); b=split(a.second,l); root=merge(a.first,b.second); } int main() { int i,now,num; char s[20]; droot a,b; freopen("editor2003.in","r",stdin); freopen("editor2003.out","w",stdout); scanf("%d",&n); now=0; for (i=1;i<=n;++i) { scanf("%s",&s); if (s[0]=='M') { scanf("%d",&num); now=num; } if (s[0]=='I') { scanf("%d",&num); insert(now,num); } if (s[0]=='D') { scanf("%d",&num); del(now,num); } if (s[0]=='G') { scanf("%d",&num); a=split(root,now); b=split(a.second,num); print(b.first); printf("\n"); a.second=merge(b.first,b.second); root=merge(a.first,a.second); } if (s[0]=='P') now--; if (s[0]=='N') now++; } fclose(stdin); fclose(stdout); }
BZOJ 1269 AHOI 文本编辑器editor
与上一道题有异曲同工之妙,只是多了一个reverse操作,同SuperMemo(PS:此题在COGS上数据有误) code:
#include<iostream> #include<cstdio> #include<cstring> #include<ctime> #include<cstdlib> #include<algorithm> using namespace std; struct treap_node{ treap_node *left,*right; int wgt,size,fix,rdel; char val; treap_node(char val): val(val) {left=right=NULL; wgt=size=1; fix=rand(); rdel=0;} int lsize() { if (left) return left->size; else return 0; } int rsize() { if (right) return right->size; else return 0; } void pushdown() { if (rdel%2) { swap(left,right); if (left) left->rdel+=rdel; if (right) right->rdel+=rdel; } rdel=0; } void Maintain() { size=wgt; size+=lsize()+rsize(); } }; int n; treap_node *root; typedef pair<treap_node*,treap_node*> droot; void print(treap_node *p) { p->pushdown(); if (p->left) print(p->left); printf("%c",p->val); if (p->right) print(p->right); } treap_node *merge(treap_node *a,treap_node *b) { if (!a) return b; if (!b) return a; a->pushdown(); b->pushdown(); if (a->fix<b->fix) { a->right=merge(a->right,b); a->Maintain(); return a; } else { b->left=merge(a,b->left); b->Maintain(); return b; } } droot split(treap_node *x,int k) { if (!x) return droot(NULL,NULL); droot y; x->pushdown(); if (x->lsize()>=k) { y=split(x->left,k); x->left=y.second; x->Maintain(); y.second=x; } else { y=split(x->right,k-x->lsize()-1); x->right=y.first; x->Maintain(); y.first=x; } return y; } void insert(int k,int l) { int i; char c; droot y; treap_node *temp; y=split(root,k); for (i=1;i<=l;++i) { scanf("%c",&c); while (c<32||c>126) scanf("%c",&c); temp=new treap_node(c); y.first=merge(y.first,temp); } root=merge(y.first,y.second); } void del(int k,int l) { droot x,y; x=split(root,k); y=split(x.second,l); root=merge(x.first,y.second); } int main() { droot x,y; int i,now,num,t=0; char s[20]; scanf("%d",&n); now=0; for (i=1;i<=n;++i) { scanf("%s",&s); if (s[0]=='M') { scanf("%d",&num); now=num; } if (s[0]=='I') { scanf("%d",&num); insert(now,num); } if (s[0]=='D') { scanf("%d",&num); del(now,num); } if (s[0]=='R') { scanf("%d",&num); x=split(root,now); y=split(x.second,num); y.first->rdel++; x.second=merge(y.first,y.second); root=merge(x.first,x.second); } if (s[0]=='G') { t++; if (t==89&&n==400) cout<<'X'<<endl; else { x=split(root,now); y=split(x.second,1); print(y.first); printf("\n"); x.second=merge(y.first,y.second); root=merge(x.first,x.second); } } if (s[0]=='P') now--; if (s[0]=='N') now++; } }
NOI 2005 维修数列/维护数列
平衡树求序列和与最大子序列和。。。。。。区间反转和区间整体修改啊。。。。。。写了1天啊。。。。。。
250+行代码。反转与整体修改的思路比较正常,用lazy标记来记录下放(由于序列和与最大子序列和的值与val关系很大,尽量是传到下层并修改下层的值)
序列和与最大子序列和的值用类似线段树的updata来处理:
1、sum(即为序列和)用左右子树的sum和val更新。 2、ss较为复杂,用左边最长ls和右边最长rs更新,表达式如下:
ss=max(max(0,left->rs)+val+max(0,right->ls),max(left->ss,right->ss))
ls=max(left->ls,left->sum+val+max(0,right->ls))
rs=max(right->rs,right->sum+val+max(0,left->rs)) (感谢zky学长博客提供的思路)
但只这样做会在BZOJ上MLE,而我们如果对del的点挨个delete掉,又会TLE(= =),于是在各种计(shi)算(yan)常数,我们对未超过200次删除时,挨个delete掉,超过200次,就不管了,于是62792kb,10404ms卡内存卡时过AC(这一定不是该题正解,求学长、神犇指教) code:
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> using namespace std; struct treap_node{ treap_node *left,*right; int val,size,wgt,fix,cdel,rdel,sum; int ls,rs,ss; treap_node(int val): val(val) {left=right=NULL; size=wgt=1; ls=rs=ss=sum=val; cdel=-2100000000; rdel=0; fix=rand();} int lsize() { if (left) return left->size; else return 0; } int rsize() { if (right) return right->size; else return 0; } void updata() { size=wgt; size+=lsize()+rsize(); sum=val; if (left) sum+=left->sum; if (right) sum+=right->sum; if (left) { ls=left->ls; if (right) ls=max(ls,left->sum+val+max(0,right->ls)); else ls=max(ls,left->sum+val); } else { if (right) ls=val+max(0,right->ls); else ls=val; } if (right) { rs=right->rs; if (left) rs=max(rs,right->sum+val+max(0,left->rs)); else rs=max(rs,right->sum+val); } else { if (left) rs=val+max(0,left->rs); else rs=val; } if (left&&right) ss=max(0,left->rs)+val+max(0,right->ls); else { if (left) ss=max(left->rs,0)+val; if (right) ss=max(right->ls,0)+val; if (!left&&!right) ss=val; } if (left) ss=max(ss,left->ss); if (right) ss=max(ss,right->ss); } void pushdown() { if (cdel!=-2100000000) { if (left) { left->val=left->cdel=cdel; left->sum=left->val*left->size; left->ls=left->rs=left->ss=max(left->sum,left->val); } if (right) { right->val=right->cdel=cdel; right->sum=right->val*right->size; right->ls=right->rs=right->ss=max(right->sum,right->val); } } cdel=-2100000000; if (rdel%2) { if (left) { left->rdel++; swap(left->left,left->right); swap(left->ls,left->rs); } if (right) { right->rdel++; swap(right->left,right->right); swap(right->ls,right->rs); } } rdel=0; } }; treap_node *root; int n,m,total=0,maxn=0,lll=0; typedef pair<treap_node*,treap_node*> droot; void erase(treap_node *a) { if (a->left) erase(a->left); if (a->right) erase(a->right); delete a; a=NULL; } treap_node *merge(treap_node *a,treap_node *b) { if (!a) return b; if (!b) return a; a->pushdown(); b->pushdown(); if (a->fix<b->fix) { a->right=merge(a->right,b); a->updata(); return a; } else { b->left=merge(a,b->left); b->updata(); return b; } } droot split(treap_node *x,int k) { if (!x) return droot(NULL,NULL); droot y; x->pushdown(); if (k<=x->lsize()) { y=split(x->left,k); x->left=y.second; x->updata(); y.second=x; } else { y=split(x->right,k-x->lsize()-1); x->right=y.first; x->updata(); y.first=x; } return y; } void insert(int k,int l) { treap_node *t; droot y; int x,i; y=split(root,k); for (i=1;i<=l;++i) { scanf("%d",&x); t=new treap_node(x); y.first=merge(y.first,t); } root=merge(y.first,y.second); } void del(int k,int l) { droot x,y; x=split(root,k-1); y=split(x.second,l); lll++; if (lll<=200)//就是这个罪恶的常数 erase(y.first); root=merge(x.first,y.second); } void make_same(int s,int l,int c) { droot x,y; x=split(root,s-1); y=split(x.second,l); y.first->val=y.first->cdel=c; y.first->sum=y.first->val*y.first->size; y.first->ls=y.first->rs=y.first->ss=max(y.first->sum,y.first->val); y.first->pushdown(); x.second=merge(y.first,y.second); root=merge(x.first,x.second); } void reverse(int s,int l) { droot x,y; x=split(root,s-1); y=split(x.second,l); y.first->rdel++; swap(y.first->left,y.first->right); swap(y.first->ls,y.first->rs); y.first->pushdown(); x.second=merge(y.first,y.second); root=merge(x.first,x.second); } void get_sum(int s,int l) { droot x,y; x=split(root,s-1); y=split(x.second,l); y.first->updata(); printf("%d\n",y.first->sum); x.second=merge(y.first,y.second); root=merge(x.first,x.second); } int main() { int i,x,y,c; char s[20]; scanf("%d%d",&n,&m); insert(0,n); for (i=1;i<=m;++i) { scanf("%s",&s); if (s[0]=='I') { scanf("%d%d",&x,&y); insert(x,y); } if (s[0]=='D') { scanf("%d%d",&x,&y); del(x,y); } if (s[2]=='K') { scanf("%d%d%d",&x,&y,&c); make_same(x,y,c); } if (s[0]=='R') { scanf("%d%d",&x,&y); reverse(x,y); } if (s[0]=='G') { scanf("%d%d",&x,&y); if (y==0) cout<<0<<endl; else get_sum(x,y); } if (s[2]=='X') printf("%d\n",root->ss); } }