【模板】二逼平衡树（树套树）
题目链接：ybt金牌导航4-7-5 / luogu P3380
题目大意
要你支持一些操作。
求一个数的区间排名，一个区间的排名第 k，修改数组的一个数，求一个区间中一个数的前驱后继。
思路
考虑到它有了一个区间，我们不能直接用平衡树来搞。
那我们就有一个想法，用一个方法表示出所有区间，都建一个平衡树。
当然会锅。
那我们想一下，你其实可以把它分成几个区间——线段树。
然后就想到了线段树套平衡树的做法。
线段树记录位置，然后每个节点都是一个平衡树。
一开始建就直接枚举它覆盖的范围，直接一个一个数插入。
（我们这里用的是 fhq Treap）
然后你区间排名就是把那些关联的平衡树都找出来，看里面总共有多少个数小于这个数。然后这个个数加一就是排名。
（我这里用的是小于等于，所以要看有多少个小于等于 (x-1) 的再加一）
接着是求排名第 k，我们并没有什么优秀的方法，所以我们二分这个数，然后看排名是否小于等于 k。
（这个地方就是 (nlog^3n)，比较不优，听说可以权值线段树套平衡树，线段树记录数值，平衡树记录范围，但我不会搞）
然后修改，那我们就把包含它的区间（线段树上到这个点的链）都找出来处理，先把之前的数删掉，然后再插入。
删掉的话我们只删一个，所以我们把这个大小的数字（们）组成的平衡树割出来，然后只用删一个，就把根节点删掉（把左右儿子合并）就好了。
然后就是前驱后继，那也是同样的方法，在每个分割出的区间都求一次，然后取最大 / 最小值就可以。
记得处理没有前驱没有后继的情况。
代码
#include<queue>
#include<cstdio>
#include<cstdlib>
#include<iostream>
using namespace std;
int n, m, a[50001], root, tot;
int op, x, y, z;
struct Tree_in {
int ls, rs, sz, yj, val;
}tree[4000001];
struct Tree_out {
int rt;
}t[200001];
int newpoint(int num) {
int re = ++tot;
tree[re] = (Tree_in){0, 0, 1, rand(), num};
return re;
}
void up(int now) {
tree[now].sz = tree[tree[now].ls].sz + tree[tree[now].rs].sz + 1;
}
pair <int, int> split_val(int now, int val) {
if (!now) return make_pair(0, 0);
pair <int, int> re;
if (val < tree[now].val) {
re = split_val(tree[now].ls, val);
tree[now].ls = re.second;
up(now);
re.second = now;
}
else {
re = split_val(tree[now].rs, val);
tree[now].rs = re.first;
up(now);
re.first = now;
}
return re;
}
int merge(int x, int y) {
if (!x) return y;
if (!y) return x;
if (tree[x].yj < tree[y].yj) {
tree[x].rs = merge(tree[x].rs, y);
up(x);
return x;
}
else {
tree[y].ls = merge(x, tree[y].ls);
up(y);
return y;
}
}
void insert_(int &now, int num) {
pair <int, int> x = split_val(now, num);
now = merge(merge(x.first, newpoint(num)), x.second);
}
int ask_bigger_(int &now, int num) {
pair <int, int> x = split_val(now, num);
int re = tree[x.first].sz;
now = merge(x.first, x.second);
return re;
}
void delete_(int &now, int num) {
pair <int, int> x = split_val(now, num);
pair <int, int> y = split_val(x.first, num - 1);
y.second = merge(tree[y.second].ls, tree[y.second].rs);
//删掉的话这里是只删一个，对了防止多个相同的都被删，我们把这些数组成的平衡树割出来，然后把它的根节点丢掉（即把左右儿子合并，就可以只删一个）
now = merge(merge(y.first, y.second), x.second);
}
int ask_pre_(int &now, int num) {
pair <int, int> x = split_val(now, num - 1);
int X = x.first, lst = -2147483647;
while (X) {
lst = X;
X = tree[X].rs;
}
now = merge(x.first, x.second);
if (lst == -2147483647) return lst;
return tree[lst].val;
}
int ask_nxt_(int &now, int num) {
pair <int, int> x = split_val(now, num);
int X = x.second, lst = 2147483647;
while (X) {
lst = X;
X = tree[X].ls;
}
now = merge(x.first, x.second);
if (lst == 2147483647) return lst;
return tree[lst].val;
}
void build(int now, int l, int r) {
if (l == r) {
t[now].rt = newpoint(a[l]);
return ;
}
else {
for (int i = l; i <= r; i++)//每个点枚举它覆盖的范围，一个一个加
insert_(t[now].rt, a[i]);
}
int mid = (l + r) >> 1;
build(now << 1, l, mid);
build(now << 1 | 1, mid + 1, r);
}
int ask_bigger(int now, int l, int r, int L, int R, int num) {//记得排名要加一个，而且这里是大于等于 num 的个数
if (L <= l && r <= R) {
return ask_bigger_(t[now].rt, num);
}
int re = 0, mid = (l + r) >> 1;
if (L <= mid) re += ask_bigger(now << 1, l, mid, L, R, num);
if (mid < R) re += ask_bigger(now << 1 | 1, mid + 1, r, L, R, num);
return re;
}
int ask_kth(int l, int r, int rnk) {
int L = 0, R = 1e8, ans = 0;
while (L <= R) {
int mid = (L + R) >> 1;
if (ask_bigger(1, 1, n, l, r, mid - 1) + 1 <= rnk) {
ans = mid;
L = mid + 1;
}
else R = mid - 1;
}
return ans;
}
void change(int now, int l, int r, int pl, int num) {
delete_(t[now].rt, a[pl]);//交换的就跑出有影响的所有区间（线段树上到它的链）
insert_(t[now].rt, num);//然后删掉之前的，放上现在的
if (l == r) return ;
int mid = (l + r) >> 1;
if (pl <= mid) change(now << 1, l, mid, pl, num);
else change(now << 1 | 1, mid + 1, r, pl, num);
}
int ask_pre(int now, int l, int r, int L, int R, int num) {
if (L <= l && r <= R) {
return ask_pre_(t[now].rt, num);
}
int mid = (l + r) >> 1, re = -2147483647;
if (L <= mid) re = max(re, ask_pre(now << 1, l, mid, L, R, num));
if (mid < R) re = max(re, ask_pre(now << 1 | 1, mid + 1, r, L, R, num));
return re;
}
int ask_nxt(int now, int l, int r, int L, int R, int num) {
if (L <= l && r <= R) {
return ask_nxt_(t[now].rt, num);
}
int mid = (l + r) >> 1, re = 2147483647;
if (L <= mid) re = min(re, ask_nxt(now << 1, l, mid, L, R, num));
if (mid < R) re = min(re, ask_nxt(now << 1 | 1, mid + 1, r, L, R, num));
return re;
}
int main() {
srand(19491001);
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
}
build(1, 1, n);
while (m--) {
scanf("%d", &op);
if (op == 1) {
scanf("%d %d %d", &x, &y, &z);
printf("%d
", ask_bigger(1, 1, n, x, y, z - 1) + 1);
continue;
}
if (op == 2) {
scanf("%d %d %d", &x, &y, &z);
printf("%d
", ask_kth(x, y, z));
continue;
}
if (op == 3) {
scanf("%d %d", &x, &y);
change(1, 1, n, x, y);
a[x] = y;
continue;
}
if (op == 4) {
scanf("%d %d %d", &x, &y, &z);
printf("%d
", ask_pre(1, 1, n, x, y, z));
continue;
}
if (op == 5) {
scanf("%d %d %d", &x, &y, &z);
printf("%d
", ask_nxt(1, 1, n, x, y, z));
continue;
}
}
return 0;
}