题面： 【模板】文艺平衡树（Splay）
题解：无
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
using namespace std;
inline int rd(){
int x=,f=;char c=getchar();
while(c<''||c>''){if(c=='-')f=-; c=getchar();}
while(c>=''&&c<=''){x=x*+c-''; c=getchar();}
return f*x;
}
const int maxn=(1e5)+;
int N,M,tot=,val[maxn],siz[maxn],pr[maxn],rt=,chd[maxn][];
int L,R,x,y,z;
bool fl[maxn];
inline int New_node(int a){
val[++tot]=a;
siz[tot]=;
pr[tot]=rand();
return tot;
}
inline void Pushup(int a){
siz[a]=siz[chd[a][]]+siz[chd[a][]]+;
return;
}
inline void Pushdown(int a){
if(fl[a]){
swap(chd[a][],chd[a][]);
if(chd[a][])fl[chd[a][]]^=;
if(chd[a][])fl[chd[a][]]^=;
fl[a]=;
}
return;
}
inline int Merge(int a,int b){
if(!a||!b)return (a+b);
if(pr[a]<pr[b]){
Pushdown(a);
chd[a][]=Merge(chd[a][],b);
Pushup(a);
return a;
}
else{
Pushdown(b);
chd[b][]=Merge(a,chd[b][]);
Pushup(b);
return b;
}
}
inline void Split(int now,int k,int &x,int &y){
if(!now){x=y=; return;}
Pushdown(now);
if(siz[chd[now][]]+<=k){
x=now;
Split(chd[now][],k-siz[chd[now][]]-,chd[now][],y);
}
else {
y=now;
Split(chd[now][],k,x,chd[now][]);
}
Pushup(now);
return;
}
inline void Work(int now){
if(!now)return;
Pushdown(now);
Work(chd[now][]);
printf("%d ",val[now]);
Work(chd[now][]);
return;
}
int main(){
srand();
N=rd();M=rd();
for(int i=;i<=N;i++)rt=Merge(rt,New_node(i));
while(M--){
L=rd();R=rd();
Split(rt,L-,x,y);
Split(y,R-L+,y,z);
fl[y]^=;
rt=Merge(Merge(x,y),z);
}
Work(rt);
return ;
}
By:AlenaNuna