Splay
普通平衡树：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
const int inf=0x3f3f3f3f;
int n,tot,root;
int ch[maxn][2],fa[maxn],val[maxn],cnt[maxn],size[maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
return res*f;
}
bool check(int p){return ch[fa[p]][1]==p;}
void up(int p){size[p]=size[ch[p][0]]+size[ch[p][1]]+cnt[p];}
void rotate(int p)
{
int x=fa[p],y=fa[x],k=check(p),z=ch[p][k^1];//x->father,y->grandfather
ch[x][k]=z,fa[z]=x;
ch[y][check(x)]=p,fa[p]=y;
ch[p][k^1]=x,fa[x]=p;
up(x),up(p);
}
void splay(int p,int goal)
{
while(fa[p]!=goal)
{
int x=fa[p],y=fa[x];
if(y!=goal)
{
if(check(p)==check(x)) rotate(x);
else rotate(p);
}
rotate(p);
}
if(!goal) root=p;
}
void insert(int k)
{
int p=root,last=0;
while(p&&val[p]!=k) last=p,p=ch[p][val[p]<k];
if(p) cnt[p]++;
else
{
p=++tot;
if(last) ch[last][val[last]<k]=p;
ch[p][0]=ch[p][1]=0;fa[p]=last;val[p]=k;cnt[p]=size[p]=1;
}
splay(p,0);
}
void find(int k)//p(val=k)->root
{
int p=root;
while(ch[p][val[p]<k]&&val[p]!=k)p=ch[p][val[p]<k];
splay(p,0);
}
int kth(int k)
{
//puts("11");
int p=root;
while(23333)
{
if(ch[p][0]&&k<=size[ch[p][0]]) p=ch[p][0];
else if(k>size[ch[p][0]]+cnt[p]) k-=size[ch[p][0]]+cnt[p],p=ch[p][1];
else return p;
}
}
int pre(int k)
{
find(k);
if(val[root]<k) return root;
int p=ch[root][0];
while(ch[p][1]) p=ch[p][1];
return p;
}
int nxt(int k)
{
find(k);
if(val[root]>k) return root;
int p=ch[root][1];
while(ch[p][0]) p=ch[p][0];
return p;
}
void delet(int k)
{
int last=pre(k),next=nxt(k);
splay(last,0),splay(next,root);//ch[next][0] only have p(val=k)
int del=ch[next][0];
if(cnt[del]>1) cnt[del]--,splay(del,0);
else ch[next][0]=0,up(next),up(root);
}
int main()
{
n=read();
insert(inf),insert(-inf);
for(int i=1;i<=n;i++)
{
int op=read(),k=read();
if(op==1)insert(k);
if(op==2)delet(k);
if(op==3)find(k),printf("%d\n",size[ch[root][0]]);
if(op==4)printf("%d\n",val[kth(k+1)]);//insert->inf/-inf
if(op==5)printf("%d\n",val[pre(k)]);
if(op==6)printf("%d\n",val[nxt(k)]);
}
return 0;
}文艺平衡树：
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,m,tot,root;
int ch[maxn][2],fa[maxn],val[maxn],cnt[maxn],size[maxn];
bool rev[maxn];
inline int read()
{
char c=getchar();int res=0,f=1;
while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9') res=res*10+c-'0',c=getchar();
return res*f;
}
bool check(int p){return ch[fa[p]][1]==p;}
void up(int p){size[p]=size[ch[p][0]]+size[ch[p][1]]+cnt[p];}
inline void down(int p)
{
if(!rev[p]) return;
swap(ch[p][0],ch[p][1]);
rev[ch[p][0]]^=1;rev[ch[p][1]]^=1;rev[p]=0;
}
inline void rotate(int p)
{
int x=fa[p],y=fa[x],k=check(p),z=ch[p][k^1];
ch[x][k]=z,fa[z]=x;
ch[y][check(x)]=p,fa[p]=y;
ch[p][k^1]=x,fa[x]=p;
up(x),up(p);
}
inline void splay(int p,int goal)
{
while(fa[p]!=goal)
{
int x=fa[p],y=fa[x];
if(y!=goal)
{
if(check(p)==check(x)) rotate(x);
else rotate(p);
}
rotate(p);
}
if(!goal) root=p;
}
inline void insert(int k)
{
int p=root,last=0;
while(p&&val[p]!=k) last=p,p=ch[p][val[p]<k];
if(p) cnt[p]++;
else
{
p=++tot;
if(last) ch[last][val[last]<k]=p;
ch[p][0]=ch[p][1]=0;fa[p]=last;val[p]=k;cnt[p]=size[p]=1;
}
splay(p,0);
}
inline int kth(int k)
{
int p=root;
while(2333)
{
down(p);
if(ch[p][0]&&k<=size[ch[p][0]]) p=ch[p][0];
else if(k>size[ch[p][0]]+cnt[p]) k-=size[ch[p][0]]+cnt[p],p=ch[p][1];
else return p;
}
}
inline void reverse(int l,int r)
{
int x=kth(l),y=kth(r+2);//l->l-1,r->r+1
splay(x,0);splay(y,x);
rev[ch[y][0]]^=1;
}
void print(int p)
{
down(p);
if(ch[p][0]) print(ch[p][0]);
if(val[p]&&val[p]<=n) printf("%d ",val[p]);
if(ch[p][1]) print(ch[p][1]);
}
int main()
{
n=read(),m=read();
for(int i=0;i<=n+1;i++) insert(i);
for(int i=1;i<=m;i++){int l=read(),r=read();reverse(l,r);}
print(root);
return 0;
}