BZOJ 3223: Tyvj 1729 文艺平衡树 splay

3223: Tyvj 1729 文艺平衡树

Time Limit: 10 Sec   Memory Limit: 128 MB

Submit: 4614  

Solved: 2699

[

Submit][

Status][

Discuss]

Description

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

Input

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

Output

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

Sample Input

5 3

1 3

1 3

1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

本蒟蒻终于会写splay啦

上次说要写splay不记得是多久远了。。。

今天难得心情不好，决定补坑

狂打5遍，心情舒畅

这题卡PE 差评

2017.8.3再次更改模板

#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<complex>
#include<iostream>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<map>
#include<set>
using namespace std;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
	return x*f;
}
void print(int x)
{if(x<0)putchar('-'),x=-x;if(x>=10)print(x/10);putchar(x%10+'0');}

const int N=100100;

int size[N],ch[N][2],fa[N],root;

bool rev[N];

inline void pushup(int k)
{size[k]=size[ch[k][0]]+size[ch[k][1]]+1;}

inline void pushdown(int k)
{
	if(rev[k])
	{
		rev[ch[k][0]]^=1;rev[ch[k][1]]^=1;
		swap(ch[k][0],ch[k][1]);
		rev[k]=0;
	}
}

void build(int l,int r,int last)
{
	if(l>r)return ;
	int now=(l+r)>>1;
	fa[now]=last;now<last?ch[last][0]=now:ch[last][1]=now;
	if(l==r){size[now]=1;return ;}
	build(l,now-1,now);build(now+1,r,now);
	pushup(now);
}

int find(int k,int rk)
{
	pushdown(k);
	if(size[ch[k][0]]>=rk)return find(ch[k][0],rk);
	if(size[ch[k][0]]+1<rk)return find(ch[k][1],rk-size[ch[k][0]]-1);
	return k;
}

inline void rotate(int x,int &k)
{
	int y=fa[x],z=fa[y],l,r,t;
	ch[y][0]==x?l=0:l=1;r=1^l;
	if(y==k)k=x;else ch[z][1]==y?ch[z][1]=x:ch[z][0]=x;
	fa[x]=z;fa[y]=x;
	t=ch[x][r];ch[y][l]=t;ch[x][r]=y;fa[t]=y;
	pushup(x);pushup(y);
}

void splay(int x,int &k)
{
	while(x^k)
	{
		int y=fa[x],z=fa[y];
		if(y^k)
		{
			if((ch[y][0]==x)^(ch[z][0]==y))rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}


void rever(int l,int r)
{
	int x=find(root,l),y=find(root,r);
	splay(x,root);splay(y,ch[x][1]);
	rev[ch[y][0]]^=1;
}

int main()
{
	int n=read(),m=read();
	register int i,x,y;
	build(1,n+2,0);root=(n+3)>>1;
	while(m--){x=read();y=read();rever(x,y+2);}
	for(i=1;i<=n;++i)print(find(root,i+1)-1),putchar(' ');
	return 0;
}
/*
5 3
1 3
1 3
1 4

4 3 2 1 5
*/