12
11
2015
0

【tyvj1729】【bzoj3223】【Splay】文艺平衡树

 文艺平衡树
时间: 1000ms / 空间: 131072KiB / Java类名: Main

背景

此为平衡树系列第二道:文艺平衡树

描述

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

输入格式

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n)  m表示翻转操作次数
接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

输出格式

输出一行n个数字,表示原始序列经过m次变换后的结果

测试样例1

输入

5 3 
1 3 
1 3 
1 4

输出

4 3 2 1 5

备注

n,m<=100000 

 

1、理解树中节点的含义以及节点所记录的信息:

每个节点的值即为该节点的编号 故用id[]储存信息(这道题是给出的是1~n的有序数列,满足id[i]==i 故可省略id[])

  建树:不用Splay Tree的插入旋转操作,普通的二分建树即可

void build(int l,int r,int k)
{
	if(l>r) return;
	/*这个是必要的
	可以模拟建树过程
		/*get嵌套注释~
		i     7   3
		id[i] 1   2
		/
		1   2
	上述情况就会用到该语句
	*/
	int now=id[l],last=id[k];
	if(l==r)
	{
		fa[now]=last;
		s[now]=1;
		if(l<k)
			tr[last][0]=now;
		else
			tr[last][1]=now;
		return;
	}
	int mid=l+r>>1;
	now=id[mid];
	build(l,mid-1,mid);	build(mid+1,r,mid);//mid为根,左右建树
//===l>r return后到这里将未加入的节点加入mid
	fa[now]=last;
	pushup(mid);

	if(mid<k)//比较值 故不是now和last
		tr[last][0]=now;
	else tr[last][1]=now;
}

2、区间翻转操作:

Splay处理区间[l,r],将l-1转至根部,将r+1转至根的右孩子,这样根的右孩子的左子树便为[l,r]。

为了处理l==1||r==n的情况,新增两个节点 0,n+1。方便起见,将所有节点的编号加1。则在树中插入节点为1到n+2  节点1和节点n+2是没有意义的

int find(int p,int rank)
{
	pushdown(p);
	int l=tr[p][0],r=tr[p][1];
	if(s[l]+1==rank) return p;
	else if(s[l]>=rank) return find(l,rank);//返回l即可,不用tr[p][0]
	else return find(r,rank-s[l]-1);
}
void rever(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(x,rt);
	splay(y,tr[x][1]);
	int z=tr[y][0];
	rev[z]^=1;//标记
}

3、Rotate操作:旋转四步走

 

void rotate(int x,int &p)
{
	int y=fa[x],z=fa[y];
	int l,r;
	if(tr[y][0]==x) l=0;
	else l=1;
	r=l^1;
	//===换根===/
	if(y==p)
		p=x;
	else
	{
		if(tr[z][0]==y) tr[z][0]=x;
		else tr[z][1]=x;
	}
	//===换父亲===/
	fa[x]=z;fa[y]=x;
	fa[tr[x][r]]=y;
	//===换儿子===/
	tr[y][l]=tr[x][r];
	tr[x][r]=y;
	//===更新所维护的值(顺序随意)/
	pushup(y);pushup(x);
}

其中if(y==p) p=x;

注意这里表示单旋或双旋第二步的操作。此时z并非第一步时的z,而是y旋转到根后新的父节点。正如第一行 z=fa[y] 这里的z是变化的。当然随着旋转,y所指结点也可能变化。

4、 update(p)操作:对以p为根的树进行更新

根据更新的方向分为pushup()和pushdown()

pushup()为从下向上更新

pushdown()为从上向下更新

本来更新操作放函数中即可,单另出来便于之后维护更多属性。


我的代码:

#include<cstdio>
#include<iostream>
#include<cstdlib>
#define for2(i,s,t) for(int i=(s);i<=(t);i++)
using namespace std;
const int M=100000+10;
int n,m,rt,tot;
int tr[M][2],id[M],fa[M],s[M];
bool rev[M];
inline void pushup(int p)
{
	int l=tr[p][0],r=tr[p][1];
	s[p]=s[l]+s[r]+1;
}
inline void pushdown(int p)
{
	int l=tr[p][0],r=tr[p][1];
	if(rev[p])
	{
		swap(tr[p][0],tr[p][1]);
		rev[l]^=1;rev[r]^=1;
		rev[p]=0;
	}
}
void rotate(int x,int &p)
{
	int y=fa[x],z=fa[y];
	int l,r;
	if(tr[y][0]==x) l=0;
	else l=1;
	r=l^1;
	if(y==p)
		p=x;
	else
	{
		if(tr[z][0]==y) tr[z][0]=x;
		else tr[z][1]=x;
	}
	fa[x]=z;fa[y]=x;
	fa[tr[x][r]]=y;
	tr[y][l]=tr[x][r];
	tr[x][r]=y;
	pushup(y);pushup(x);
}
void splay(int x,int &p)
{
	while(x!=p)
	{
		int y=fa[x],z=fa[y];
		if(y!=p)
		{
			if((tr[y][0]==x)^(tr[z][0]==y))
				rotate(x,p);
			else
				rotate(y,p);
		}
		rotate(x,p);
	}
}
void build(int l,int r,int k)
{
	if(l>r) return;
	int now=id[l],last=id[k];
	if(l==r)
	{
		fa[now]=last;
		s[now]=1;
		if(l<k)
			tr[last][0]=now;
		else
			tr[last][1]=now;
		return;
	}
	int mid=l+r>>1;
	now=id[mid];
	build(l,mid-1,mid);	build(mid+1,r,mid);
	fa[now]=last;
	pushup(mid);
	if(mid<k)
		tr[last][0]=now;
	else tr[last][1]=now;
}
int find(int p,int rank)
{
	pushdown(p);
	int l=tr[p][0],r=tr[p][1];
	if(s[l]+1==rank) return p;
	else if(s[l]>=rank) return find(l,rank);
	else return find(r,rank-s[l]-1);
}
void rever(int l,int r)
{
	int x=find(rt,l),y=find(rt,r+2);
	splay(x,rt);
	splay(y,tr[x][1]);
	int z=tr[y][0];
	rev[z]^=1;
}
int main()
{
	scanf("%d%d",&n,&m);
	for2(i,1,n+2) id[i]=++tot;
	build(1,n+2,0);
	rt=(n+3)>>1;
	for2(i,1,m)
	{
		int L,R;
		scanf("%d%d",&L,&R);
		rever(L,R);
	}
	for2(i,2,n+1)
		printf("%d ",find(rt,i)-1);
	return 0;
}
Category: 伸展树 | Tags: | Read Count: 187

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com