Splay

适用题目特征

维护区间翻转。

原理

想要翻转区间，只要将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