适用题目特征
维护区间翻转。
原理
想要翻转区间，只要将Splay重构如下。
区间翻转
并且在每次操作后，都模仿类似线段树lazy标记，下传区间翻转标记即可。
PS：Splay实现时，通常需要加入首尾两个节点来处理边界情况，所以最终处理书上相关操作时，都要考虑这个两个节点。
例题
Luogu P3391
代码如下
/*
Luogu P3391
*/
#define method_2
#ifdef method_1
/*
*/
#endif
#ifdef method_2
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n,m;
int a[maxn];
struct Splay{
int sz,tag,f,son[2],val;
}s[maxn];
int rt;
#define pushup(x) (s[x].sz=s[s[x].son[0]].sz+s[s[x].son[1]].sz+1)
#define rever(x) (swap(s[x].son[0],s[x].son[1]),s[x].tag^=1)
#define pushdown(x) (s[x].tag&&(rever(s[x].son[0]),rever(s[x].son[1]),s[x].tag=0))
#define which(x) (s[s[x].f].son[1]==x)
#define connect(x,y,d) (s[s[x].f=y].son[d]=x)
#define split(x,y) (splay(find(x),rt),splay(find((y)+2),s[rt].son[1]),s[s[rt].son[1]].son[0])
inline void rotate(int x,int& k){
register int fa=s[x].f,pa=s[fa].f,d=which(x);pushdown(fa),pushdown(x),
(fa^k?s[pa].son[which(fa)]=x:k=x),s[x].f=pa,connect(s[x].son[d^1],fa,d),connect(fa,x,d^1),pushup(fa),pushup(x);
}
inline void splay(int x,int& k) {int fa;while(x^k) fa=s[x].f,fa^k&&(rotate(which(x)^which(fa)?x:fa,k),0),rotate(x,k);}
inline void build(int l,int r,int& rt){
int mid=l+r>>1;
if(s[rt=mid].sz=1,s[rt].val=a[mid],!(l^r)) return;
l<mid&&(build(l,mid-1,s[rt].son[0]),s[s[rt].son[0]].f=rt),
r>mid&&(build(mid+1,r,s[rt].son[1]),s[s[rt].son[1]].f=rt),
pushup(rt);
}
inline int find(int rk){
int x=rt;
while(x) {
if(pushdown(x),s[s[x].son[0]].sz>=rk) x=s[x].son[0];
else if(!(rk-=s[s[x].son[0]].sz+1)) return x;
else x=s[x].son[1];
}
}
inline void reverse(int l,int r){
int k=split(l,r);rever(k);
}
void dfs(int x){
pushdown(x);
if(s[x].son[0]) dfs(s[x].son[0]);
if(s[x].val!=-INF&&s[x].val!=INF) printf("%d ",s[x].val);
if(s[x].son[1]) dfs(s[x].son[1]);
}
void solve(){
build(1,n+2,rt);
rep(x,2,n+1){
int l,r;scanf("%d%d",&l,&r);
reverse(l,r);
}
dfs(rt);
}
int main() {
// ios::sync_with_stdio(false);
// freopen("文艺平衡树.in","r",stdin);
scanf("%d%d",&n,&m);
a[1]=-INF,a[n+2]=INF;
int x;
rep(i,1,n) a[i+1]=i;
solve();
return 0;
}
#endif
#ifdef method_3
/*
*/
#endif
Luogu P4402
代码如下
/*
Luogu P4402
*/
#define method_1
#ifdef method_1
/*
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<ctime>
#include<string>
#include<bitset>
#define D(x) cout<<#x<<" = "<<x<<" "
#define E cout<<endl
#define rep(i,s,t) for(int i=(s);i<=(t);i++)
#define rep0(i,s,t) for(int i=(s);i<(t);i++)
#define rrep(i,t,s) for(int i=(t);i>=(s);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int maxn=100000+5;
const int INF=0x3f3f3f3f;
int n;
struct s{
int id,val;
bool operator<(const s &h)const{return val<h.val||(val==h.val&&id<h.id);}
}a[maxn];
struct Splay{
int sz,tag,f,son[2];
}s[maxn];
int rt;
#define pushup(x) (s[x].sz=s[s[x].son[0]].sz+s[s[x].son[1]].sz+1)
#define rever(x) (swap(s[x].son[0],s[x].son[1]),s[x].tag^=1)
#define pushdown(x) (s[x].tag&&(rever(s[x].son[0]),rever(s[x].son[1]),s[x].tag=0))
#define which(x) (s[s[x].f].son[1]==x)
#define connect(x,y,d) (s[s[x].f=y].son[d]=x)
#define split(x,y) (splay(find(x),rt),splay(find((y)+2),s[rt].son[1]),s[s[rt].son[1]].son[0])
inline void rotate(int x,int& k){
register int fa=s[x].f,pa=s[fa].f,d=which(x);pushdown(fa),pushdown(x),
(fa^k?s[pa].son[which(fa)]=x:k=x),s[x].f=pa,connect(s[x].son[d^1],fa,d),connect(fa,x,d^1),pushup(fa),pushup(x);
}
inline void splay(int x,int& k) {int fa;while(x^k) fa=s[x].f,fa^k&&(rotate(which(x)^which(fa)?x:fa,k),0),rotate(x,k);}
inline void build(int l,int r,int& rt){
int mid=l+r>>1;
if(s[rt=mid].sz=1,!(l^r)) return;
l<mid&&(build(l,mid-1,s[rt].son[0]),s[s[rt].son[0]].f=rt),
r>mid&&(build(mid+1,r,s[rt].son[1]),s[s[rt].son[1]].f=rt),
pushup(rt);
}
inline int find(int rk){
int x=rt;
while(x) {
if(pushdown(x),s[s[x].son[0]].sz>=rk) x=s[x].son[0];
else if(!(rk-=s[s[x].son[0]].sz+1)) return x;
else x=s[x].son[1];
}
}
inline void reverse(int l,int r){
int k=split(l,r);rever(k);
}
void solve(){
sort(a+2,a+n+2);
build(1,n+2,rt);
rep(x,2,n+1){
splay(a[x].id+1,rt);
int ans=s[s[rt].son[0]].sz;printf("%d ",ans);
reverse(x-1,ans);
}
}
int main() {
// ios::sync_with_stdio(false);
// freopen("机械排序.in","r",stdin);
scanf("%d",&n);
a[1].val=-INF,a[n+2].val=INF;
a[1].id=-INF,a[n+2].id=INF;
int x;
rep(i,1,n) scanf("%d",&x),a[i+1].id=i,a[i+1].val=x;
solve();
return 0;
}
#endif
#ifdef method_2
/*
*/
#endif
#ifdef method_3
/*
*/
#endif
