Treap
Splay
无旋Treap——fhq treap
简介
就是没有旋转操作的 Treap，一些性质什么的都跟 Treap 类似。
算法介绍
(1)merge(x,y)
将两棵“有序”（x中元素的权值最大值小于 y 中元素权值最小值）的Treap合并成一棵。
int ch[N][2], sz[N], pri[N], val[N];
//val 为权值，pri 为优先级，sz 为子树大小
int merge(int x, int y){
if(!x || !y) return x + y;
//若 x 的优先级小，则它应该新树的根
//由于 x 中元素都小于 y 中元素权值，所以合并 x 的右子树和 y
if(pri[x] < pri[y]) return ch[x][1] = merge(ch[x][1], y), modify(x), x;
//另一种情况
else return ch[y][0] = merge(x, ch[y][0]), modify(y), y;
}
(2.1) Split(u, v, x, y)
根据权值 v 将 u 这棵 Treap 分为两棵平衡树 x ,y,其中 x 中元素权值均小于等于 v, y 中元素权值均大于 v。
void split(int u, int v, int &x, int &y){
if(!u) return x = y = 0, void();
if(val[u] <= v) x = u, split(ch[u][1], v, ch[u][1], y); //u 的权值比 v 小，说明 u 以及 u 的左子树都属于 x, 所以递归划分 u 的右子树
else y = u, split(ch[u][0], v, x, ch[u][0]); //另一种情况
modify(u);
}
(2.2) Split(u, kth, x, y)
跟据子树大小将树 u 分成两棵树 x, y。 x 的大小为 k ,他包含树 u 中权值前 k 小的元素。
void split(int u, int k, int &x, int &y){
if(!u) return x = y = 0, void();
if(k <= sz[ch[u][0]]) y = u, split(ch[u][0], k, x, ch[u][0]); //左子树大小大于 k ，说明 u 以及 u 的右子树都在 y 中， 递归划分左子树
else x = u, split(ch[u][1], k - sz[ch[u][0]] - 1, ch[u][1], y);
modify(u);
}
(3) insert
int newnode(int v){ // 新建一个权值为 v 的节点
sz[++tot] = 1, pri[tot] = rnd(), val[tot] = v;
return tot;
}
void insert(int k, int v){ //在以 rt 为根的 Treap 中 k 的位置插入一个值为 v 的元素
split(rt, k, r1, r2); //根据排名分
rt = merge(r1, merge(newnode(v), r2));
}
void insert(int &u, int v){ //在以 u 为根的 Treap 中插入一个值为 v 的元素
split(u, v, r1, r2); //根据权值分
u = merge(r1, merge(newnode(v), r2));
}
//上面两个 split 是不一样的
(4) delte(u,v)
删除 u 为根的 Treap 中权值为 v 的所有元素。
void del(int &u, int v){
int L, R, p, q;
split(u, v, L, R); //调用 (2.1) 对应代码
split(L, v - 1, p, q);
u = merge(L, merge(p, q));
}
注意：此操作会将所有权值为 v 的元素都删除掉，若只删除一个，则需要求出 v 的排名，在调用 split(u,k,x,y) 以便实现删除一个元素。
(5) modify(u,l,r)
对区间 \([l,r]\) 进行操作，例如区间加、区间翻转等。
void modify(int &u, int l, int r){
int L, R, p, q;
split(u, l - 1, L, R); //调用 (2.2) 对应代码
split(R, r - l + 1, p, q);
solve(p);
u = merge(L, merge(p, q));
}
Merge(x, y)
合并两个 “乱序” Treap （即 \(x\) 中的元素并不全小于 \(y\) 中的元素），也就是合并任意两个 Treap。
复杂度 \(O(n\log & n)\)
void Merge(int x, int y){
if(!x || !y) return x + y;
if(pri[x] > pri[y]) swap(x, y);
int L, R;
split(v, val[u], L, R); //调用 (2.1) 对应代码
ch[x][0] = Merge(ch[x][0], L);
ch[x][1] = Merge(ch[x][1], R);
}
其他操作
1.删除
删除一个数 \(v\)：先用 \(v\) 按照权值分裂成两棵树 \(x,z\)，再用 \(v−1\) 按照权值将 \(x\) 分裂成两棵树 \(x,y\)。此时 \(y\) 的所有节点的权值就都是 \(v\)。但是我们只能删一个，因此可以将 \(y\) 的左右节点合并起来，这样 \(y\) 的节点个数就少了一个。最后再合并回来即可。
void del(int v){
int x, y, z;
split(rt, v, x, z), split(x, v - 1, x, y);
y = merge(ch[y][0], ch[y][1]);
rt = merge(merge(x, y), z);
}
2.第 \(k\) 大
查找第 \(k\) 大的数：假设当前遍历到节点 \(u\)。若 \(k≤sz_{ls_u}\) 则向左儿子递归；若 \(k=sz_{ls_u}+1\) 则直接返回 \(val_u\)；否则向右儿子递归。
int kth(int u, int k){
while(1){
if(k <= sz[ch[u][0]]) u = ch[u][0];
else if(k == sz[ch[u][0]] + 1) return u;
else k -= sz[ch[u][0]] + 1, u = ch[u][1];
}
}
3. 前缀/后继
查找 \(v\) 的前驱：用 \(v−1\) 按照权值分裂成 \(x,y\)，再找 \(x\) 的最大值即可（即 \(x\) 的第 \(sz_x\) 大值）。后继同理。
//前驱
split(rt, v - 1, x, y);
printf("%d\n", val[kth(x, sz[x])]);
rt = merge(x, y);
//后继
split(rt, v, x, y);
printf("%d\n", val[tr.kth(y, 1)]);
rt = tr.merge(x, y);
4. 排名
查询 \(v\) 的排名：用 \(v−1\) 按照权值分裂成 \(x,T\)，那么答案即为 \(sz_x+1\)。最后合并。
split(rt, v - 1, x, y);
printf("%d\n", sz[x] + 1);
rt = merge(x, y);
例题
Ⅰ. P3369 【模板】普通平衡树
模板，操作上面都讲过。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 67;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
bool _u;
mt19937 rnd((unsigned)time(0));
int n, tot, rt;
int ch[N][2], sz[N], pri[N], val[N];
struct FHQ{
void modify(int x){sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;}
int new_node(int v){sz[++tot] = 1, val[tot] = v, pri[tot] = rnd(); return tot;}
int merge(int x, int y){
if(!x || !y) return x + y;
if(pri[x] < pri[y]) return ch[x][1] = merge(ch[x][1], y), modify(x), x;
else return ch[y][0] = merge(x, ch[y][0]), modify(y), y;
}
void split(int u, int v, int &x, int &y){
if(!u) return x = y = 0, void();
if(val[u] <= v) x = u, split(ch[u][1], v, ch[u][1], y);
else y = u, split(ch[u][0], v, x, ch[u][0]);
modify(u);
}
int kth(int u, int k){
while(1){
if(k <= sz[ch[u][0]]) u = ch[u][0];
else if(k == sz[ch[u][0]] + 1) return u;
else k -= sz[ch[u][0]] + 1, u = ch[u][1];
}
}
}tr;
bool _v;
int main(){
cerr << abs(&_u - &_v) / 1048576.0 << " MB\n";
n = read();
while(n--){
int opt = read(), v = read(), x, y, z;
if(opt == 1){
tr.split(rt, v, x, y);
rt = tr.merge(tr.merge(x, tr.new_node(v)), y);
} else if(opt == 2){
tr.split(rt, v, x, z), tr.split(x, v - 1, x, y);
y = tr.merge(ch[y][0], ch[y][1]);
rt = tr.merge(tr.merge(x, y), z);
} else if(opt == 3){
tr.split(rt, v - 1, x, y);
printf("%d\n", sz[x] + 1);
rt = tr.merge(x, y);
} else if(opt == 4){
printf("%d\n", val[tr.kth(rt, v)]);
} else if(opt == 5){
tr.split(rt, v - 1, x, y);
printf("%d\n", val[tr.kth(x, sz[x])]);
rt = tr.merge(x, y);
} else{
tr.split(rt, v, x, y);
printf("%d\n", val[tr.kth(y, 1)]);
rt = tr.merge(x, y);
}
}
return 0;
}
Ⅱ. P4146 序列终结者
为了写这篇博客，终于把6个月前没过的代码调出来了。
对于区间反转与区间加，直接打标记就行了。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 51;
int read(){
int x = 0, f = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
return x * f;
}
mt19937 rnd((unsigned)time(0));
int n, m, rt, r1, r2, tot;
int maxn[N], val[N], add[N], sz[N];
int ch[N][2], pri[N];
bool lazy[N];
int newnode(int v){
sz[++tot] = 1, pri[tot] = rnd(), val[tot] = v;
maxn[tot] = v, add[tot] = 0, lazy[tot] = 0;
return tot;
}
void pushup(int u){
sz[u] = sz[ch[u][1]] + sz[ch[u][0]] + 1;
maxn[u] = val[u];
if(ch[u][1]) maxn[u] = max(maxn[u], maxn[ch[u][1]]);
if(ch[u][0]) maxn[u] = max(maxn[u], maxn[ch[u][0]]);
}
void pushdown(int x){
if(lazy[x]){
lazy[ch[x][1]] ^= 1, lazy[ch[x][0]] ^= 1;
swap(ch[x][1], ch[x][0]);
lazy[x] = 0;
}
if(add[x]){
add[ch[x][1]] += add[x], add[ch[x][0]] += add[x];
val[ch[x][1]] += add[x], val[ch[x][0]] += add[x];
maxn[ch[x][1]] += add[x], maxn[ch[x][0]] += add[x];
add[x] = 0;
}
}
int merge(int x, int y){
pushdown(x), pushdown(y);
if(!x || !y) return x + y;
int u;
if(pri[x] < pri[y]) u = x, ch[x][1] = merge(ch[x][1], y);
else u = y, ch[y][0] = merge(x, ch[y][0]);
pushup(u);
return u;
}
void split(int u, int k, int &x, int &y){
if(!u) return x = y = 0, void();
pushdown(u);
if(sz[ch[u][0]] >= k) y = u, split(ch[u][0], k, x, ch[u][0]);
else x = u, split(ch[u][1], k - sz[ch[u][0]] - 1, ch[u][1], y);
pushup(u);
}
void insert(int k, int v){
split(rt, k, r1, r2), rt = merge(r1, merge(newnode(v), r2));
}
int main(){
n = read(), m = read();
for(int i = 1; i <= n; ++i) insert(i - 1, 0);
while(m--){
int opt = read(), l = read(), r = read(), v;
int x, y, z;
if(opt == 1){
v = read();
split(rt, l - 1, x, y);
split(y, r - l + 1, y, z);
val[y] += v, maxn[y] += v, add[y] += v;
rt = merge(x, merge(y, z));
}else if(opt == 2){
split(rt, l - 1, x, y);
split(y, r - l + 1, y, z);
lazy[y] ^= 1;
rt = merge(x, merge(y, z));
}else{
split(rt, l - 1, x, y);
split(y, r - l + 1, y, z);
printf("%d\n", maxn[y]);
rt = merge(x, merge(y, z));
}
}
return 0;
}