BZOJ3196:Tyvj1730平衡树问题

### 题目描述
需要设计一种数据结构来维护一个有序数列，并支持以下五种操作：
1. 查询数值k在指定区间内的排名。
2. 查询指定区间内排名为k的数值。
3. 修改数列中某一位置的数值。
4. 查询指定区间内小于k的最大数值（前驱）。
5. 查询指定区间内大于k的最小数值（后继）。

### 输入格式
第一行包含两个整数n和m，分别表示有序序列的长度和操作次数。第二行包含n个整数，表示初始的有序序列。接下来m行，每行第一个整数opt表示操作类型，随后根据操作类型提供相应参数。

### 输出格式
对于每个查询类操作（1, 2, 4, 5），输出一行结果。

### 示例输入
```
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
```

### 示例输出
```
2
4
3
4
9
```

### 数据范围
- n 和 m 的范围：n, m ≤ 50000
- 序列中每个数的范围：[0, 1e8]
- 注意：操作5中的k可能为负数

### 解决方案
此题采用线段树套用平衡树（Treap）的方法解决。以位置为关键字建立线段树，在线段树的每个节点上再建一棵以权值为关键字的Treap。

#### 操作实现
1. **查询排名**：在线段树中找到区间的位置，在对应的Treap中统计比k小的元素数量。
2. **查询排名为k的值**：通过二分查找确定答案，并利用查询排名的操作进行验证。
3. **修改数值**：等价于先删除旧值再插入新值，需在线段树中所有包含该位置的区间执行此操作。
4. **查询前驱**：在线段树中找到区间的位置，在每个区间的Treap中寻找小于k的最大值。
5. **查询后继**：在线段树中找到区间的位置，在每个区间的Treap中寻找大于k的最小值。

#### 注意事项
- 对于重复数值的处理，可以在Treap上维护一个权重属性weight。
- 查询操作应确保有明确的终止条件，避免死循环。

### 代码实现
```cpp
#include
#include
#include
#include
#define N 3000005
using namespace std;

struct treap {
int fix, weight, size, l, r, data;
} a[N];

int ans, num, root[N], tot = 0, x[50005], n, m;

void Push_up(int x) {
a[x].size = a[a[x].l].size + a[a[x].r].size + a[x].weight;
}

void zag(int &x) {
int o = a[x].l;
a[x].l = a[o].r;
a[o].r = x;
a[o].size = a[x].size;
Push_up(x);
x = o;
}

void zig(int &x) {
int o = a[x].r;
a[x].r = a[o].l;
a[o].l = x;
a[o].size = a[x].size;
Push_up(x);
x = o;
}

void New_node(int &x, int data) {
x = ++tot;
a[x].weight = a[x].size = 1;
a[x].data = data;
a[x].fix = rand();
a[x].l = a[x].r = 0;
}

void Insert(int &x, int data) {
if (!x) {
New_node(x, data);
return;
}
a[x].size++;
if (a[x].data == data) {
a[x].weight++;
return;
}
if (data Insert(a[x].l, data);
if (a[a[x].l].fix } else {
Insert(a[x].r, data);
if (a[a[x].r].fix }
}

void Delet(int &x, int data) {
if (a[x].data == data) {
if (a[x].weight > 1) {
a[x].weight--;
a[x].size--;
return;
}
if (a[x].l * a[x].r == 0) x = a[x].l + a[x].r;
else if (a[a[x].l].fix zag(x);
Delet(x, data);
} else {
zig(x);
Delet(x, data);
}
return;
}
a[x].size--;
if (a[x].data > data) Delet(a[x].l, data);
else Delet(a[x].r, data);
}

void Build(int x, int l, int r, int now, int data) {
Insert(root[x], data);
if (l == r) return;
int m = (l + r) >> 1;
if (now <= m) Build(x <<1, l, m, now, data);
else Build(x <<1 | 1, m + 1, r, now, data);
}

void Askrank(int x, int data) {
if (!x) return;
if (a[x].data == data) {
ans += a[a[x].l].size;
return;
}
if (a[x].data > data) Askrank(a[x].l, data);
else {
ans = ans + a[a[x].l].size + a[x].weight;
Askrank(a[x].r, data);
}
}

void Getrank(int x, int lx, int rx, int l, int r, int data) {
if (lx >= l && rx <= r) {
Askrank(root[x], data);
return;
}
if (lx == rx) return;
int m = (lx + rx) >> 1;
if (l <= m) Getrank(x <<1, lx, m, l, r, data);
if (r > m) Getrank(x <<1 | 1, m + 1, rx, l, r, data);
}

void Getnum(int l, int r, int k) {
int lx = 0, rx = 100000000;
while (lx <= rx) {
int m = (lx + rx) >> 1;
ans = 1;
Getrank(1, 1, n, l, r, m);
if (ans <= k) {
lx = m + 1;
num = m;
} else rx = m - 1;
}
}

void Modify(int x, int l, int r, int p, int data, int c) {
Delet(root[x], data);
Insert(root[x], c);
if (l == r) return;
int m = (l + r) >> 1;
if (p <= m) Modify(x <<1, l, m, p, data, c);
else Modify(x <<1 | 1, m + 1, r, p, data, c);
}

void Askpre(int x, int data) {
if (!x) return;
if (a[x].data >= data) Askpre(a[x].l, data);
else {
if (ans Askpre(a[x].r, data);
}
}

void Getpre(int x, int lx, int rx, int l, int r, int data) {
if (lx >= l && rx <= r) {
Askpre(root[x], data);
return;
}
if (lx == rx) return;
int m = (lx + rx) >> 1;
if (l <= m) Getpre(x <<1, lx, m, l, r, data);
if (r > m) Getpre(x <<1 | 1, m + 1, rx, l, r, data);
}

void Asknext(int x, int data) {
if (!x) return;
if (a[x].data > data) {
if (a[x].data Asknext(a[x].l, data);
} else Asknext(a[x].r, data);
}

void Getnext(int x, int lx, int rx, int l, int r, int data) {
if (lx >= l && rx <= r) {
Asknext(root[x], data);
return;
}
if (lx == rx) return;
int m = (lx + rx) >> 1;
if (l <= m) Getnext(x <<1, lx, m, l, r, data);
if (r > m) Getnext(x <<1 | 1, m + 1, rx, l, r, data);
}

void Print(int x) {
printf("%d\n", x);
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
for (int i = 1; i <= n; i++) Build(1, 1, n, i, x[i]);
while (m--) {
int q, l, r, k, p;
scanf("%d", &q);
switch (q) {
case 1:
scanf("%d%d%d", &l, &r, &k);
ans = 1;
Getrank(1, 1, n, l, r, k);
Print(ans);
break;
case 2:
scanf("%d%d%d", &l, &r, &k);
Getnum(l, r, k);
Print(num);
break;
case 3:
scanf("%d%d", &l, &k);
p = x[l];
x[l] = k;
Modify(1, 1, n, l, p, k);
break;
case 4:
scanf("%d%d%d", &l, &r, &k);
ans = 0;
Getpre(1, 1, n, l, r, k);
Print(ans);
break;
case 5:
scanf("%d%d%d", &l, &r, &k);
ans = 100000000;
Getnext(1, 1, n, l, r, k);
Print(ans);
break;
}
}
return 0;
}
```

### 总结
涉及平衡树的问题容易因操作名称相似而导致错误，如zig和zag，因此编码时务必仔细检查，确保逻辑正确无误。