BZOJ 3223 Tyvj 1729 文艺平衡树

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

Sample Output

HINT

N,M<=100000

Source

平衡树

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

splay~

第一道自己写出来的splay！虽然只有区间翻转但也好棒啊！

#include<cstdio>#include<iostream>using namespace std;#define inf 999999999int n,m,ll,rr,rev[100001],siz[100001],a[100001],id[100001],root,c[100001][2],fa[100001],val[100001];int read(){	int totnum=0,f=1;char ch=getchar();	while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}	while(ch>='0' && ch<='9') {totnum=totnum*10+ch-'0';ch=getchar();}	return totnum*f;}void pushup(int u){	int l=c[u][0],r=c[u][1];	siz[u]=siz[l]+siz[r]+1;}void pushdown(int u){	int l=c[u][0],r=c[u][1];rev[u]=0;	rev[l]^=1;rev[r]^=1;swap(c[u][0],c[u][1]);}void build(int l,int r,int k){	if(l>r) return;	int now=id[l],la=id[k];	if(l==r)	{		fa[now]=la;siz[now]=1;val[now]=a[l];		if(l<k) c[la][0]=now;		else c[la][1]=now;		return;	}	int mid=(l+r)>>1;now=id[mid];	build(l,mid-1,mid);build(mid+1,r,mid);	fa[now]=la;pushup(mid);	if(mid<k) c[la][0]=now;	else c[la][1]=now;}void rotate(int x,int &k){	int y=fa[x],z=fa[y],l,r;	if(c[y][0]==x) l=0;	else l=1;r=l^1;	if(k==y) k=x;	else if(c[z][0]==y) c[z][0]=x;	else c[z][1]=x;	fa[y]=x;fa[x]=z;fa[c[x][r]]=y;	c[y][l]=c[x][r];c[x][r]=y;	pushup(y);pushup(x);}void splay(int x,int &k){	while(x!=k)	{		int y=fa[x],z=fa[y];		if(y!=k)		{			if(c[y][0]==x ^ c[z][0]==y) rotate(x,k);			else rotate(y,k);		}		rotate(x,k);	}}int findd(int u,int k){	if(rev[u]) pushdown(u);	int l=c[u][0],r=c[u][1];	if(siz[l]+1==k) return u;	if(siz[l]>=k) return findd(l,k);	return findd(r,k-siz[l]-1);}void rever(int l,int r){	int x=findd(root,l),y=findd(root,r+2);	splay(x,root);splay(y,c[x][1]);	int now=c[y][0];	rev[now]^=1;}int main(){	n=read();m=read();a[1]=a[n+2]=-inf;	for(int i=1;i<=n;i++) a[i+1]=i;	for(int i=1;i<=n+2;i++) id[i]=i;	build(1,n+2,0);root=(n+3)>>1;	while(m--)	{		ll=read();rr=read();rever(ll,rr);	}	for(int i=2;i<=n+1;i++) PRintf("%d ",findd(root,i)-1);printf("/n");	return 0;}