本blog会讲一些简单的Splay的应用，包括但不局限于
1. Splay 维护数组下标，支持区间reserve操作，解决区间问题
2. Splay 的启发式合并（按元素多少合并）
3. 线段树+Splay 大常数树套树
一、Splay维护区间下标解决区间翻转问题
思想： 对于数组的下标是不可重复的，我们使用平衡树维护下标，利用Splay的splay操作，让区间都在一棵子树内。
然后直接输出这颗子树的维护信息，由于维护的是子树信息，那么父亲的信息一定可以由两个儿子推出。
于是就可以类似于线段树的操作了（用儿子信息维护父亲信息）。
[LuoGu 模板] 文艺平衡树 ： 维护区间翻转，输出最终区间形态。
Solution ：
考虑splay函数的实质，就是把节点x转到目标节点，并且让Splay树保持BST的性质。
那么显然，对于维护序列下标，其维护的值便是元素对于数组的位置。（一个节点左边儿子子树的位置都小于该节点）
对于一个区间进行翻转，那么事实上就是 把l和r下标交换，l+1和r-1下标交换...
那么如何确定这个区间呢，不妨把[l-1]转到根节点，[r+1]转到根节点的右儿子，那么对于根节点右儿子的左儿子所在子树
就可以描述为[l,r]区间。
然而，对于Splay本身来说是不能出现下标为0的情况的，否则会死循环，在(1)中已经讲的非常明确了，所以我们仍然加入一个哨兵节点，对于所有区间均+1
在代码中的实现是这样的。
需要注意的是，特殊的，对于维护位置(下标)是不会出现重复元素的，那么所有节点cnt的值都是1，就省略了。
最后这颗Splay的中序遍历就是最终区间。
# include <bits/stdc++.h> # define inf (0x3f3f3f3f) using namespace std; const int N=2e5+10; inline int read() { int X=0,w=0; char c=0; while(c<‘0‘||c>‘9‘) {w|=c==‘-‘;c=getchar();} while(c>=‘0‘&&c<=‘9‘) X=(X<<3)+(X<<1)+(c^48),c=getchar(); return w?-X:X; } void write(int x) { if (x<0) putchar(‘-‘),x=-x; if (x>9) write(x/10); putchar(x%10+‘0‘); } void writeln(int x){ write(x);putchar(‘\n‘); } struct Splay{ # define ls(x) (t[x][0]) # define rs(x) (t[x][1]) int t[N][2],size[N],val[N],par[N]; bool rev[N]; int root,tot; Splay(){ root=0,tot=0;insert(-inf);insert(inf);} int check (int x) { return rs(par[x])==x;} void pushup(int x) { size[x]=size[ls(x)]+size[rs(x)]+1;} void rotate(int x) { int y=par[x],k=check(x); t[y][k]=t[x][k^1]; par[t[x][k^1]]=y; t[x][k^1]=y; t[par[y]][check(y)]=x; par[x]=par[y]; par[y]=x; pushup(y); pushup(x); } void splay(int x,int goal=0) { while (par[x]!=goal) { int y=par[x],z=par[y]; if (z!=goal) rotate(check(x)==check(y)?y:x); rotate(x); } if (!goal) root=x; } void down(int x) { if (rev[x]) { swap(ls(x),rs(x)); rev[ls(x)]^=1; rev[rs(x)]^=1; rev[x]=0; } } void insert(int x){ int cur=root,p=0; while (cur && val[cur]!=x) p=cur,cur=t[cur][x>val[cur]]; cur=++tot; if (p) t[p][x>val[p]]=cur; t[cur][0]=t[cur][1]=0; val[cur]=x; par[cur]=p; size[cur]=1; splay(cur); } int kth_id(int k) { int cur=root; while (true) { down(cur); if (t[cur][0] && k<=size[ls(cur)]) cur=ls(cur); else if (k>size[ls(cur)]+1) { k-=size[ls(cur)]+1; cur=rs(cur); } else return cur; } } void reserve(int l,int r) { int x=kth_id(l),y=kth_id(r+2); splay(x); splay(y,x); rev[ls(y)]^=1; } void print(int x) { down(x); if (ls(x)) print(ls(x)); if (val[x]!=-inf&&val[x]!=inf) printf("%d ",val[x]); if (rs(x)) print(rs(x)); } }tr; int main() { int n=read(),m=read(); for (int i=1;i<=n;i++) tr.insert(i); for (int i=1;i<=m;i++) { int l=read(),r=read(); tr.reserve(l,r); } tr.print(tr.root); return 0; }
用Splay维护3个操作
1 L R V : 区间[L,R]每个元素+V
2 L R ：将区间[L,R]翻转
3 L R ：输出区间[L,R]的最小值
Hint ： 元素初始值都为 0
Solution：
原文：https://www.cnblogs.com/ljc20020730/p/10628090.html
