文艺平衡树
数组变量名意义
const int o_o=1e5+10;//数组下标大小
int n,m;
struct po{
int f;//父节点
int l_n;//懒标记
int l,r;//左右儿子
int s_z;//子树大小
}t_r[o_o];
int g_g;//根节点 建树
和不同的平衡术不同点在于，它的表示变成区间。
(4)
/ \
/ \
/ \
(2) (6)
/ \ / \
(1) (3) (5) (7)这是一棵初始化的“平衡树”，它的初始化很线段树的每个区间处理很相似。首先找出根节点（一班选区间中间的数），然后它的左右子树的意义在于：代表一个区间。而将数中序遍历则是原序列。
$4$ 的左子树就代表 $[1,3]$，右子树代表 $[5,7]$。
void b_t(int l,int r,int f){
if(l>r)return;//不在区间内，退出
int m_i=(l+r)>>1;
if(m_i<f)t_r[f].l=m_i;//符合平衡树特性，存储左右节点
else t_r[f].r=m_i;
t_r[m_i].f=f;//存父节点
t_r[m_i].s_z=1;//初始化节点大小
if(l==r)return;//子节点，不会再存在左右子树，退出
b_t(l,m_i-1,m_i);//左子树
b_t(m_i+1,r,m_i);//右子树
u_p(m_i);//更新当前节点
}节点更新信息维护及节点子树大小即可。
void u_p(int x){
t_r[x].s_z=t_r[t_r[x].l].s_z+t_r[t_r[x].r].s_z+1;//左右子树大小的和 +1
}旋转
和平衡树的旋转方式相同，但由于我们要让一些节点有目的的向上转，所以要存父节点，和 这里 的思路相同，只是视角从父节点比变成了子节点（或孙节点）。
void b_l(int x,int y,int z){//左旋
//旋转（从根节点向上转）
t_r[y].r=t_r[x].l;
t_r[t_r[y].r].f=y;
t_r[x].l=y;
t_r[y].f=x;//更新父节点
t_r[x].f=z;//更新父节点
u_p(x);//更新节点信息
u_p(y);
}
void b_r(int x,int y,int z){//右旋
//旋转（从根节点向上转）
t_r[y].l=t_r[x].r;
t_r[t_r[y].l].f=y;
t_r[x].r=y;
t_r[y].f=x;//更新父节点
t_r[x].f=z;//更新父节点
u_p(x);//更新节点信息
u_p(y);
}区间翻转
首先，整棵树一定是按照中序遍历输出的（存的时候就是这个目的存的）。接着我们目前会的只有旋转。但是，单纯的旋转并不能改变中序遍历的输出顺序。和 这里 讲的“相对位置”（降维打击变成一维数组的节点左右的关系）的理解相同。
既然是区间翻转那么一定是要有“相对位置”改变的。是时候破坏“先对位置”！，我们将一个节点的左右子树交换，就可以破坏“相对位置”。简单粗暴，行之有效。
现在有了破坏的思路，那么要怎么做呢？
既然是区间翻转，树维护的就是区间，树的特性又是单调的（我们破坏的是值的单调性，但我们这棵树维护的是区间的单调性），那么我们又知道旋转不会破坏单调性，那么我们不难讲我们要旋转的区间放到一个子树中。如下：
(4)
/ \
/ \
/ \
(2) (6)
/ \ / \
(1) (3) (5) (7)现在我们要翻转 $[3,6]$。进行如下处理，将 $[3,6]$ 放到一个子树中。为了方便描述子树坐标，我们将 $2$ 转到根节点，$7$ 为 $2$ 的右节点，更具树的性质（单调性），$[3,6]$ 会变成 $7$ 的左子树。
先处理 $2$：
右旋：
(2)
/ \
/ \
/ \
(1) (4)
/ \
(3) (6)
/ \
(5) (7)$2$ 到达目标地点。
再处理 $7$：
左旋：
(2)
/ \
/ \
/ \
(1) (4)
/ \
(3) (7)
/
(6)
/
(5)左旋：
(2)
/ \
/ \
/ \
(1) (7)
/
(4)
/ \
(3) (6)
/
(5)$7$ 到达目标地点。
现在我们可以将 $4$ 打上懒标记，这个懒标记是需要交换左右子树的懒标记。每次访问到这个点，需要释放并下传。为方便理解，我们释放所有懒标记。
(2)
/ \
/ \
/ \
(1) (7)
/
(4)
/ \
(6) (3)
\
(5)中序遍历：$1,2,6,5,4,3,7$。问题解决。
void x_t(int x,int &k){
while(x!=k){//没有到达预期位置
int y=t_r[x].f;//原点的父节点
int z=t_r[y].f;//原节点的父节点的父节点
if(y!=k){//父节点也没有到达预期
if((t_r[y].l==x)^(t_r[z].l==y))l_r(x,k);//一条链（都是左儿子或右儿子）
else l_r(y,k);//不是一条链
}
l_r(x,k);//父节点到达预期，只用再旋转一次即可到达目的
}
}将目标区间转移到一个子树，遍历整棵子树可以直接放心的打标记，不会影响到其他数据。
注意：我们每回要找 $l-1$ 和 $r+1$，但加入有一棵 $7$ 节点的树。翻转正好是 $[1,7]$，就会出问题。所以我们在一开始时手动加入两个点，$1$，$r+2$，而原区间变为 $[l+1,r+1]$，就可以解决这个问题。
代码
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<vector>
#include<random>
#include<ctime>
using namespace std;
long long r_r(){//快读
long long k=0,f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-')f=-1;
c=getchar();
}
while(isdigit(c)){
k=(k<<1)+(k<<3)+(c^48);
c=getchar();
}
return k*f;
}
const int o_o=1e5+10;//数组下标大小
int n,m;
struct po{
int f;//父节点
int l_n;//懒标记
int l,r;//左右儿子
int s_z;//子树大小
}t_r[o_o];
int g_g;//根节点
void u_p(int x){
t_r[x].s_z=t_r[t_r[x].l].s_z+t_r[t_r[x].r].s_z+1;//左右子树大小的和 +1
}
void p_d(int x){
if(t_r[x].l_n){//释放懒标记
swap(t_r[x].l,t_r[x].r);//交换左右子树
t_r[t_r[x].l].l_n^=1;//懒标记下传
t_r[t_r[x].r].l_n^=1;
t_r[x].l_n=0;//清空懒标记
}
}
void b_l(int x,int y,int z){//左旋
//旋转（从根节点向上转）
t_r[y].r=t_r[x].l;
t_r[t_r[y].r].f=y;
t_r[x].l=y;
t_r[y].f=x;//更新父节点
t_r[x].f=z;//更新父节点
u_p(x);//更新节点信息
u_p(y);
}
void b_r(int x,int y,int z){//右旋
//旋转（从根节点向上转）
t_r[y].l=t_r[x].r;
t_r[t_r[y].l].f=y;
t_r[x].r=y;
t_r[y].f=x;//更新父节点
t_r[x].f=z;//更新父节点
u_p(x);//更新节点信息
u_p(y);
}
void l_r(int x,int &k){
int y=t_r[x].f;//原点父节点
int z=t_r[y].f;//原点的父节点的父节点
if(y==k)k=x;//父节点即目标状态
else{//爷节点即目标状态
if(t_r[z].l==y)t_r[z].l=x;//都是左儿子
else t_r[z].r=x;//都是右儿子
}
if(t_r[y].l==x)b_r(x,y,z);//右旋
else b_l(x,y,z);//左旋
}
void x_t(int x,int &k){
while(x!=k){//没有到达预期位置
int y=t_r[x].f;//原点的父节点
int z=t_r[y].f;//原节点的父节点的父节点
if(y!=k){//父节点也没有到达预期
if((t_r[y].l==x)^(t_r[z].l==y))l_r(x,k);//一条链（都是左儿子或右儿子）
else l_r(y,k);//不是一条链
}
l_r(x,k);//父节点到达预期，只用再旋转一次即可到达目的
}
}
void b_t(int l,int r,int f){
if(l>r)return;//不在区间内，退出
int m_i=(l+r)>>1;
if(m_i<f)t_r[f].l=m_i;//符合平衡树特性，存储左右节点
else t_r[f].r=m_i;
t_r[m_i].f=f;//存父节点
t_r[m_i].s_z=1;//初始化节点大小
if(l==r)return;//子节点，不会再存在左右子树，退出
b_t(l,m_i-1,m_i);//左子树
b_t(m_i+1,r,m_i);//右子树
u_p(m_i);//更新当前节点
}
int g_a(int x,int k){
p_d(x);//释放懒标记
int s=t_r[t_r[x].l].s_z;//左子树大小
if(k==s+1)return x;//左子树大小 +1 即本点的排名
if(k<=s)return g_a(t_r[x].l,k);//被左子树包含
else return g_a(t_r[x].r,k-s-1);//被右子树包含
}
void x_z(int l,int r){
int x=g_a(g_g,l);//在树上找到 x 的坐标
int y=g_a(g_g,r+2);//再树上找到 y 的坐标
x_t(x,g_g);//将 x 换到根节点
x_t(y,t_r[x].r);//将 y 换到根节点右儿子节点
int z=t_r[y].l;//打懒标记
t_r[z].l_n^=1;
}
int main(){
n=r_r(),m=r_r();
g_g=(n+1)/2+1;//定义根
b_t(1,n+2,g_g);//建树（初始化）
for(int i=1;i<=m;i++){
int l=r_r(),r=r_r();
x_z(l,r);//旋转区间
}
for(int i=2;i<=n+1;i++)printf("%d ",g_a(g_g,i)-1);//输出每个数
return 0;
}
