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;}