本 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;
- }
P3391 [模板] 文艺平衡树(Splay)
[例题 : 序列终结者]
用 Splay 维护 3 个操作
1 L R V : 区间 [L,R] 每个元素 + V
2 L R : 将区间 [L,R] 翻转
3 L R : 输出区间 [L,R] 的最小值
Hint : 元素初始值都为 0
Solution:
Splay 文艺平衡树学习笔记(2)
来源: http://www.bubuko.com/infodetail-3005268.html