现在的位置: 首页 > 综合 > 正文

可持久化(非旋转式)treap 学习记录

2015年04月22日 ⁄ 综合 ⁄ 共 11780字 ⁄ 字号 评论关闭

在做完郁闷的出纳员、宠物收养所等题之后,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);
	  }
}

【上篇】
【下篇】

抱歉!评论已关闭.