链接： https://www.lydsy.com/JudgeOnline/problem.php?id=3223
题面：
3223: Tyvj 1729 文艺平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 7451 Solved: 4657
[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
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 2e5+;
const int inf = 0x3f3f3f;
int n,m,sz,rt;
int c[M][],fa[M],v[M],siz[M];
bool rev[M]; inline void up(int k){
int l = c[k][],r = c[k][];
siz[k] = siz[l] + siz[r] + ;
} void pushdown(int k){
int l = c[k][],r = c[k][];
if(rev[k]){
rev[k] = ; rev[l]^=; rev[r]^=;
swap(c[k][],c[k][]);
}
} void rotate(int x,int &k){
int y = fa[x],z = fa[y],l,r;
if(c[y][] == x) l = ;
else l = ;
r = l^;
if(y == k) k = x;
else {
if(c[z][]==y) c[z][]=x;
else c[z][] = x;
}
fa[x] = z;fa[y] = x;fa[c[x][r]]=y;
c[y][l]=c[x][r]; c[x][r]=y;
up(y); up(x);
} void splay(int x,int &k){
while(x != k){
int y = fa[x],z = fa[y];
if(y != k){
if(c[y][]==x^c[z][]==y)rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
} int find(int k,int rk){
if(rev[k]) pushdown(k);
int l = c[k][],r = c[k][];
if(siz[l] + == rk) return k;
else if(siz[l] >= rk) return find(l,rk);
else return find(r,rk-siz[l]-);
} inline void reve(int l,int r){
int x = find(rt,l),y = find(rt,r+);
splay(x,rt); splay(y,c[x][]);
int z = c[y][];
rev[z] ^= ;
} inline void build(int l,int r,int f)
{
if(l>r)return;
int now=l,last=f;
if(l==r)
{
v[now]=l;siz[now]=;fa[now]=last;
if(l<f)c[last][]=now;
else c[last][]=now;
return;
}
int mid=(l+r)>>;now=mid;
build(l,mid-,mid);build(mid+,r,mid);
v[now]=mid;fa[now]=last;
if(mid<f)c[last][]=now;
else c[last][]=now;
up(now);
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
int x,y;
cin>>n>>m;
build(,n+,); rt = (n+) >> ;
for(int i = ;i <= m;i ++){
cin>>x>>y;
reve(x,y);
}
for(int i = ;i <= n;i ++){
cout<<find(rt,i+)-<<" ";
}
cout<<endl;
}