FHQ Treap（无旋Treap）、可持久化平衡树
BB
屯板！
Introduction
FHQ Treap，也称无旋Treap，顾名思义，就是不依靠rotate操作的Treap。FHQ Treap通过split和merge操作完成插入、删除等操作，由于不需要旋转，还可以用于实现 可持久化平衡树
关于FHQ Treap的资料参见下面各题在洛谷的题解
【模板】普通平衡树 - luogu P3369
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
1 插入x数
2 删除x数(若有多个相同的数，因只删除一个)
3 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4 查询排名为x的数
5 求x的前驱(前驱定义为小于x，且最大的数)
6 求x的后继(后继定义为大于x，且最小的数)
Sample Input
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
Sample Output
106465
84185
492737
Solution
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int N = (int)1e5 + 15;
const int inf = 0x3f3f3f3f;
int ch[N][2], w[N], pri[N], sz[N];
int tot;
inline int mrand() {
static int seed = 123456;
return seed = (1LL * seed * 2333 + 1234567891) % 998244353;
}
inline int newNode(int v) {
int x = ++tot;
pri[x] = mrand();
sz[x] = 1;
w[x] = v;
return x;
}
inline void pushUp(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(pri[x] < pri[y]) {
ch[x][1] = merge(ch[x][1], y);
pushUp(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
pushUp(y);
return y;
}
}
inline void split(int rt, int k, int& x, int& y) {
if(!rt) {
x = y = 0;
return;
}
if(w[rt] <= k) {
x = rt;
split(ch[rt][1], k, ch[x][1], y);
} else {
y = rt;
split(ch[rt][0], k, x, ch[y][0]);
}
pushUp(rt);
}
inline int kth(int rt, int k) {
if(sz[ch[rt][0]] + 1 == k) {
return rt;
} else if(sz[ch[rt][0]] >= k) {
return kth(ch[rt][0], k);
} else {
return kth(ch[rt][1], k - sz[ch[rt][0]] - 1);
}
}
int main() {
int rt = 0, m;
scanf("%d", &m);
while(m--) {
int op, x;
scanf("%d%d", &op, &x);
if(op == 1) {
int l, r;
split(rt, x, l, r);
rt = merge(l, merge(newNode(x), r));
} else if(op == 2) {
int p, q, r;
split(rt, x, q, r);
split(q, x - 1, p, q);
q = merge(ch[q][0], ch[q][1]);
rt = merge(p, merge(q, r));
} else if(op == 3) {
int l, r;
split(rt, x - 1, l, r);
printf("%d\n", sz[l] + 1);
rt = merge(l, r);
} else if(op == 4) {
printf("%d\n", w[kth(rt, x)]);
} else if(op == 5) {
int l, r;
split(rt, x - 1, l, r);
printf("%d\n", w[kth(l, sz[l])]);
rt = merge(l, r);
} else {
int l, r;
split(rt, x, l, r);
printf("%d\n", w[kth(r, 1)]);
rt = merge(l, r);
}
}
return 0;
}
【模板】文艺平衡树（Splay） - luogu P3391
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Sample Input
5 3
1 3
1 3
1 4
Sample Output
4 3 2 1 5
Solution
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int N = (int)1e5 + 15;
const int inf = 0x3f3f3f3f;
bool f[N];
int ch[N][2], w[N], pri[N], sz[N];
int tot;
inline int mrand() {
static int seed = 123456;
return seed = (1LL * seed * 2333 + 1234567891) % 998244353;
}
inline int newNode(int v) {
int x = ++tot;
pri[x] = mrand();
sz[x] = 1;
w[x] = v;
return x;
}
inline void pushDown(int x) {
if(f[x]) {
swap(ch[x][0], ch[x][1]);
f[ch[x][0]] ^= 1;
f[ch[x][1]] ^= 1;
f[x] = 0;
}
}
inline void pushUp(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(pri[x] < pri[y]) {
pushDown(x);
ch[x][1] = merge(ch[x][1], y);
pushUp(x);
return x;
} else {
pushDown(y);
ch[y][0] = merge(x, ch[y][0]);
pushUp(y);
return y;
}
}
inline void split(int rt, int k, int& x, int& y) {
if(!rt) {
x = y = 0;
return;
}
pushDown(rt);
if(sz[ch[rt][0]] < k) {
x = rt;
split(ch[rt][1], k - sz[ch[rt][0]] - 1, ch[x][1], y);
} else {
y = rt;
split(ch[rt][0], k, x, ch[y][0]);
}
pushUp(rt);
}
inline void show(int x) {
if(!x) {
return;
}
pushDown(x);
show(ch[x][0]);
printf("%d ", w[x]);
show(ch[x][1]);
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
int rt = 0;
for(int i = 1; i <= n; i++) {
int x = newNode(i);
rt = merge(rt, x);
}
while(m--) {
int l, r;
scanf("%d%d", &l, &r);
int x, y, z;
split(rt, l - 1, x, y);
split(y, r - l + 1, y, z);
f[y] ^= 1;
rt = merge(x, merge(y, z));
}
show(rt);
puts("");
return 0;
}
【模板】可持久化平衡树 - luogu P3835
Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作（对于各个以往的历史版本）：
1 插入x数
2 删除x数(若有多个相同的数，因只删除一个，如果没有请忽略该操作)
3 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
4 查询排名为x的数
5 求x的前驱(前驱定义为小于x，且最大的数，如不存在输出-2147483647)
6 求x的后继(后继定义为大于x，且最小的数，如不存在输出2147483647)
和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本。（操作3, 4, 5, 6即保持原版本无变化）
每个版本的编号即为操作的序号（版本0即为初始状态，空树）
Sample Input
10
0 1 9
1 1 3
1 1 10
2 4 2
3 3 9
3 1 2
6 4 1
6 2 9
8 6 3
4 5 8
Sample Output
9
1
2
10
3
Solution
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
const int N = (int)5e5 + 15;
const int inf = 0x3f3f3f3f;
int ch[N << 7][2], w[N << 7], pri[N << 7], sz[N << 7];
int root[N];
int tot;
inline int mrand() {
static int seed = 123456;
return seed = (1LL * seed * 2333 + 1234567891) % 998244353;
}
inline int newNode(int v) {
int x = ++tot;
pri[x] = mrand();
sz[x] = 1;
w[x] = v;
return x;
}
inline int copyNode(int v) {
if(!v) {
return 0;
}
int x = ++tot;
pri[x] = pri[v];
sz[x] = sz[v];
w[x] = w[v];
ch[x][0] = ch[v][0];
ch[x][1] = ch[v][1];
return x;
}
inline void pushUp(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(pri[x] < pri[y]) {
ch[x][1] = merge(ch[x][1], y);
pushUp(x);
return x;
} else {
ch[y][0] = merge(x, ch[y][0]);
pushUp(y);
return y;
}
}
inline void split(int rt, int k, int& x, int& y) {
if(!rt) {
x = y = 0;
return;
}
rt = copyNode(rt);
if(w[rt] <= k) {
x = rt;
split(ch[rt][1], k, ch[x][1], y);
} else {
y = rt;
split(ch[rt][0], k, x, ch[y][0]);
}
pushUp(rt);
}
inline int kth(int rt, int k) {
if(sz[ch[rt][0]] + 1 == k) {
return rt;
} else if(sz[ch[rt][0]] >= k) {
return kth(ch[rt][0], k);
} else {
return kth(ch[rt][1], k - sz[ch[rt][0]] - 1);
}
}
int main() {
root[0] = merge(newNode(-2147483647), newNode(2147483647));
int m;
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
int op, v, x;
scanf("%d%d%d", &v, &op, &x);
if(op == 1) {
int l, r;
split(root[v], x, l, r);
root[i] = merge(l, merge(newNode(x), r));
} else if(op == 2) {
int p, q, r;
split(root[v], x, q, r);
split(q, x - 1, p, q);
q = merge(ch[q][0], ch[q][1]);
root[i] = merge(p, merge(q, r));
} else if(op == 3) {
int l, r;
split(root[v], x - 1, l, r);
printf("%d\n", sz[l]);
root[i] = merge(l, r);
} else if(op == 4) {
root[i] = copyNode(root[v]);
printf("%d\n", w[kth(root[i], x + 1)]);
} else if(op == 5) {
int l, r;
split(root[v], x - 1, l, r);
printf("%d\n", w[kth(l, sz[l])]);
root[i] = merge(l, r);
} else {
int l, r;
split(root[v], x, l, r);
printf("%d\n", w[kth(r, 1)]);
root[i] = merge(l, r);
}
}
return 0;
}
【模板】可持久化文艺平衡树 - luogu P5055
Description
您需要写一种数据结构，来维护一个序列，其中需要提供以下操作（对于各个以往的历史版本）：
1 在第 ppp 个数后插入数 xxx 。
2 删除第 ppp 个数。
3 翻转区间 [l,r]，例如原序列是 {5,4,3,2,1}，翻转区间 [2,4] 后，结果是 {5,2,3,4,1}。
4 查询区间 [l,r] 中所有数的和。
和原本平衡树不同的一点是，每一次的任何操作都是基于某一个历史版本，同时生成一个新的版本（操作 444 即保持原版本无变化），新版本即编号为此次操作的序号。
本题强制在线。
Sample Input
10
0 1 0 1
1 1 1 2
2 4 1 2
3 1 2 0
4 4 2 1
5 3 5 7
6 4 5 6
4 1 7 1
8 3 4 6
9 4 4 1
Sample Output
3
4
5
10
Solution
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 15;
const int inf = 0x3f3f3f3f;
int ch[N << 7][2], w[N << 7], pri[N << 7], sz[N << 7], f[N << 7];
ll sum[N << 7];
int root[N];
int tot;
inline int mrand() {
static int seed = 123456;
return seed = (1LL * seed * 2333 + 1234567891) % 998244353;
}
inline int newNode(int v) {
int x = ++tot;
pri[x] = mrand();
sz[x] = 1;
sum[x] = w[x] = v;
return x;
}
inline int copyNode(int v) {
if(!v) {
return 0;
}
int x = ++tot;
sum[x] = sum[v];
pri[x] = pri[v];
sz[x] = sz[v];
w[x] = w[v];
ch[x][0] = ch[v][0];
ch[x][1] = ch[v][1];
f[x] = f[v];
return x;
}
inline void pushUp(int x) {
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
sum[x] = sum[ch[x][0]] + sum[ch[x][1]] + w[x];
}
inline void pushDown(int x) {
if(f[x]) {
ch[x][0] = copyNode(ch[x][0]);
ch[x][1] = copyNode(ch[x][1]);
swap(ch[x][0], ch[x][1]);
f[ch[x][0]] ^= 1;
f[ch[x][1]] ^= 1;
f[x] = 0;
}
}
inline int merge(int x, int y) {
if(!x || !y) {
return x | y;
}
if(pri[x] < pri[y]) {
pushDown(x);
ch[x][1] = merge(ch[x][1], y);
pushUp(x);
return x;
} else {
pushDown(y);
ch[y][0] = merge(x, ch[y][0]);
pushUp(y);
return y;
}
}
inline void split(int rt, int k, int& x, int& y) {
if(!rt) {
x = y = 0;
return;
}
pushDown(rt);
rt = copyNode(rt);
if(sz[ch[rt][0]] < k) {
x = rt;
split(ch[rt][1], k - sz[ch[rt][0]] - 1, ch[x][1], y);
} else {
y = rt;
split(ch[rt][0], k, x, ch[y][0]);
}
pushUp(rt);
}
int main() {
int m;
ll lstAns = 0;
scanf("%d", &m);
for(int i = 1; i <= m; i++) {
int op, v;
scanf("%d%d", &v, &op);
if(op == 1) {
ll p, x;
scanf("%lld%lld", &p, &x);
p ^= lstAns;
x ^= lstAns;
int l, r;
split(root[v], p, l, r);
root[i] = merge(l, merge(newNode(x), r));
} else if(op == 2) {
ll p;
scanf("%lld", &p);
p ^= lstAns;
int l, r, z;
split(root[v], p, l, r);
split(l, p - 1, l, z);
root[i] = merge(l, r);
} else if(op == 3) {
ll p, q;
scanf("%lld%lld", &p, &q);
p ^= lstAns;
q ^= lstAns;
int a, b, c;
split(root[v], p - 1, a, b);
split(b, q - p + 1, b, c);
f[b] ^= 1;
root[i] = merge(a, merge(b, c));
} else {
ll p, q;
scanf("%lld%lld", &p, &q);
p ^= lstAns;
q ^= lstAns;
int a, b, c;
split(root[v], p - 1, a, b);
split(b, q - p + 1, b, c);
lstAns = sum[b];
root[i] = merge(a, merge(b, c));
printf("%lld\n", lstAns);
}
}
return 0;
}
