STL:rope（新手不建议学习）

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
const int N=2e5+10;
rope<int>tr;rope<int>trr;
int main()
{
	int n,q;cin>>n>>q;
	for(int i=1;i<=n;i++)tr.push_back(i),trr.push_back(n-i+1);
	while(q--)
	{
		int l,r;cin>>l>>r;l--,r--;
		rope<int>fr,fr1,mid,mid1,bk,bk1;
		if(l!=0)fr=tr.substr(0,l);if(r!=n-1)fr1=trr.substr(0,n-r-1);
		mid=tr.substr(l,r-l+1);mid1=trr.substr(n-r-1,r-l+1);
		if(r!=n-1)bk=tr.substr(r+1,n-r-1);if(l!=0)bk1=trr.substr(n-l,l);
        tr.clear();trr.clear();
		tr.append(fr),tr.append(mid1),tr.append(bk);
		trr.append(fr1),trr.append(mid),trr.append(bk1);
	} 
	for(int y:tr)cout<<y<<' ';
	return 0;
}

C06【模板】FHQ Treap P3391 文艺平衡树

#include<bits/stdc++.h>
using namespace std;
#define lc(p) tr[p].ls
#define rc(p) tr[p].rs
const int N=1e5+10;
struct node{int ls,rs,val,siz,rev,rnd;}tr[N]; int rt,trlen;
int newd(int v){ tr[++trlen]={0,0,v,1,0,rand()};return trlen; }
void pushup(int p){ tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1; }
void pushdown(int p)
{
    if(!tr[p].rev)return ;
    swap(lc(p),rc(p));
    tr[lc(p)].rev^=1;
    tr[rc(p)].rev^=1;
    tr[p].rev=0;
}
void split(int p,int k,int &x,int &y)
{
    if(p==0){x=y=0;return;}
    pushdown(p);
    if(tr[lc(p)].siz<k)
    {
        x=p;
        split(rc(p),k-tr[lc(p)].siz-1,rc(x),y);
    }
    else
    {
        y=p;
        split(lc(p),k,x,lc(y));
    }
    pushup(p);
}
int merge(int x,int y)
{
    if( !x || !y )return x+y;
    if(tr[x].rnd<tr[y].rnd)
    {
        pushdown(x);
        rc(x)=merge(rc(x),y);
        pushup(x);
        return x;
    }
    else
    {
        pushdown(y);
        lc(y)=merge(x,lc(y));
        pushup(y);
        return y;
    }
}
void reverse(int l,int r)
{
    int x,y,z;
    split(rt,l-1,x,y);
    split(y,r-l+1,y,z);
    tr[y].rev^=1;
    rt=merge(merge(x,y),z);
}
void dfs(int p)
{
    if(!p)return ;
    pushdown(p);
    dfs(lc(p));
    printf("%d ",tr[p].val);
    dfs(rc(p));
}
int main()
{
    int n,m;scanf("%d%d",&n,&m);
    rt=trlen=0;
    for(int i=1;i<=n;++i)rt=merge(rt,newd(i));
    while(m--)
    {
        int l,r;scanf("%d%d",&l,&r);
        reverse(l,r);   
    }
    dfs(rt);
    return 0;
}

C04【模板】Splay P3391 文艺平衡树
【题解】by 2018liuzhiyuan：

//用中序遍历表示序列，通过对树的对称翻转实现中序遍历（即序列）的改变。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e5+10;
struct trnode
{
	int d,c,f,son[2];//d表示原序列对应的数，伸展树并不按d来排名,不必把多个节点压成一个点。 
	bool v;//翻转标记。1则要翻转。这样实际上是为了实现lazy操作。 
}tr[N];int root,len,n,m;
void update(int x)
{
	int lc=tr[x].son[0],rc=tr[x].son[1];
	tr[x].c=tr[lc].c+tr[rc].c+1;
}
void bt(int &x,int f,int l,int r)//build tree
{
	if(l>r){x=0;return;}
	int m=(l+r)>>1;
	x=++len;tr[len].d=m;tr[len].c=1;tr[len].f=f;tr[len].v=0;
	bt(tr[x].son[0],x,l,m-1);
	bt(tr[x].son[1],x,m+1,r);
	tr[x].c=tr[tr[x].son[0]].c+tr[tr[x].son[1]].c+1;
}
void rotate(int x,int w)
{
	int f=tr[x].f,ff=tr[f].f,r,R;
	
	r=tr[x].son[w];R=f;
	tr[R].son[1^w]=r;
	if(r)tr[r].f=R;
	
	r=x;R=ff;
	if(tr[R].son[0]==f){tr[R].son[0]=r;}else{tr[R].son[1]=r;}
	tr[r].f=R;
	
	r=f;R=x;
	tr[R].son[w]=r;
	tr[r].f=R;
	
	update(f);
	update(x);
}
void splay(int x,int rt)
{
	
	while(tr[x].f!=rt)
	{
		
		int f=tr[x].f,ff=tr[f].f;
		if(ff==rt)
		{
			if(tr[f].son[0]==x)rotate(x,1);else rotate(x,0);
		}
		else
		{
			     if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1);
			else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0);
			else if(tr[ff].son[0]==f&&tr[f].son[1]==x)rotate(x,0),rotate(x,1);
			else if(tr[ff].son[1]==f&&tr[f].son[0]==x)rotate(x,1),rotate(x,0);
		}
	}
	if(!rt)root=x;
}
void wh(int x)//维护翻转标记
{
	int &lc=tr[x].son[0],&rc=tr[x].son[1];
	swap(lc,rc);
	tr[lc].v^=1;
	tr[rc].v^=1;
	tr[x].v=0;
}
int findnum(int k)//找排名为k，即中序遍历排第k的编号 
{
	int x=root;
	while(1)
	{
		if(tr[x].v)wh(x);
		int lc=tr[x].son[0],rc=tr[x].son[1];
		if(tr[lc].c>=k)x=lc;
		else if(tr[lc].c+1>=k)break;
		else k-=tr[lc].c+1,x=rc;
	}
	
	return x;
	
}
void fz(int l,int r)//对中序遍历排名为l~r进行翻转
{
	int x=findnum(l-1),y=findnum(r+1);
	splay(x,0);splay(y,x);
	tr[tr[y].son[0]].v^=1;
}
#define g getchar()
void qr(int &x)
{
	char c=g;x=0;
	while(!('0'<=c&&c<='9'))c=g;
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
void write(int x)//快写 
{
	if(x/10)write(x/10);putchar(x%10+'0');
}
void pri(int x)//中序遍历。
{
	
	if(!x)return;
	if(tr[x].v)wh(x);
	pri(tr[x].son[0]);
	if(tr[x].d!=0)write(tr[x].d),putchar(' ');
	pri(tr[x].son[1]);
}
int main()
{
	qr(n);qr(m);
	bt(root,0,0,n+1);//多加两个边界点。 
	tr[len].d=0;//设定边界
	while(m--)
	{
		int l,r;qr(l);qr(r);l++;r++;
		fz(l,r);
	}
	pri(root);
	puts("");
	return 0;
}