树套树之线段树套平衡树（ZOJ2112 Dynamic Rankings)
接上篇：树套树之线段树套线段树
树套树都应该是做一道题就会了的。。
Dynamic Rankings(ZOJ 2112)
题目描述：
某公司开发了一种新型的计算机，它不再仅能找到给定N个数中第k小的数。它变成了一个更强大的系统。对于N个数a[1],a[2],…,a[N]，你可以询问a[i],a[i+1],…,a[j-1],a[j]中第k小的数(i\le j,0\lt k\le j+i-1)。更强大的是，你可以改变一些a[i]的值，然后继续询问，所有的都和之前一样。
你的任务是给计算机写一个程序，使它能够：
1.从输入中读取N个数(1<=N<=50,000)
2.处理M个操作(1<=M<=10,000)，这些操作包括询问a[i],…,a[j]中第k小的数，和将一些a[i]改成t。
分析：
对区间进行操作，我们可以用线段树解决，查找数列中的第k小值，我们可以用平衡树来解决。此题既要对区间进行操作，又要查找该区间中第k小的数，我们可以对线段树的每个节点再建一棵平衡树，维护线段树所记录的这个区间的元素，从而快速地查找该区间的第k 小数。
这里平衡树用Treap实现，也可以使用其它平衡树。
程序如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
const int MAXN = 50010, MAXP = 1000001;
struct point {
int s, ls, rs, v, w, rnd;
}p[MAXP];
int T, n, m, tmp;
int a[50001], root[3 * MAXN];
int size;
void update(int k) {
p[k].s = p[p[k].ls].s + p[p[k].rs].s + p[k].w;
}
void right_rotate(int &k) {
int t = p[k].ls;
p[k].ls = p[t].rs;
p[t].rs = k;
p[t].s = p[k].s;
update(k);
k = t;
}
void left_rotate(int &k) {
int t = p[k].rs;
p[k].rs = p[t].ls;
p[t].ls = k;
p[t].s = p[k].s;
update(k);
k = t;
}
void insert(int &k, int num) {
if(!k) {
k = ++size;
p[k].s = p[k].w = 1;
p[k].ls = p[k].rs = 0;
p[k].rnd = rand();
p[k].v = num;
return;
}
p[k].s++;
if(p[k].v == num) p[k].w++;
else if(num < p[k].v) {
insert(p[k].ls, num);
if(p[p[k].ls].rnd < p[k].rnd)
right_rotate(k);
}
else {
insert(p[k].rs, num);
if(p[p[k].rs].rnd < p[k].rnd)
left_rotate(k);
}
}
void del(int &k, int num) {
if(p[k].v == num) {
if(p[k].w > 1) {
p[k].w--;
p[k].s--;
return;
}
if(p[k].ls * p[k].rs == 0) k = p[k].ls + p[k].rs;
else if(p[p[k].ls].rnd < p[p[k].rs].rnd) {
right_rotate(k);
del(k, num);
}
else {
left_rotate(k);
del(k, num);
}
}
else if(num < p[k].v) {
del(p[k].ls, num);
p[k].s--;
}
else {
del(p[k].rs, num);
p[k].s--;
}
}
void change(int k, int l, int r, int x, int num, int y) {
del(root[k], y);
insert(root[k], num);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) change(k << 1, l, mid, x, num, y);
else change(k << 1 | 1, mid + 1, r, x, num, y);
}
void build(int k, int l, int r, int x, int num) {
insert(root[k], num);
if(l == r) return;
int mid = (l + r) >> 1;
if(x <= mid) build(k << 1, l, mid, x, num);
else build(k << 1 | 1, mid + 1, r, x, num);
}
void find(int k, int num) {
if(!k) return;
if(p[k].v <= num) {
tmp += p[p[k].ls].s + p[k].w;
find(p[k].rs, num);
}
else find(p[k].ls, num);
}
void query(int k, int l, int r, int x, int y, int num) {
if(l == x && r == y) {
find(root[k], num);
return;
}
int mid = (l + r) >> 1;
if(mid >= y) query(k << 1, l, mid, x, y, num);
else if(mid < x) query(k << 1 | 1, mid + 1, r, x, y, num);
else {
query(k << 1, l, mid, x, mid, num);
query(k << 1 | 1, mid + 1, r, mid + 1, y, num);
}
}
int main() {
srand(53425);
scanf("%d", &T);
while(T--) {
memset(root, 0, sizeof(root));
size = 0;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) build(1, 1, n, i, a[i]);
for(int i = 1; i <= m; i++) {
char s[3];
int x, y, z;
scanf("%s", s);
if(s[0] == 'C') {
scanf("%d%d", &x, &y);
change(1, 1, n, x, y, a[x]);
a[x] = y;
}
else {
scanf("%d%d%d", &x, &y, &z);
int l = 0, r = 1000000000;
while(l <= r) {
int mid = (l + r) >> 1;
tmp = 0;
query(1, 1, n, x, y, mid);
if(tmp >= z) r = mid - 1;
else l = mid + 1;
}
printf("%d\n", l);
}
}
}
return 0;
}
代码解释因为在线段树中将一个区间分割成多个小区间后, 导致无法直接定位第k小的数值, 所以我们采用二分查找的方法来确定其位置。
由于采用了二分法这一技术手段, 使得程序执行查询操作的时间复杂度达到了Θ(log1e9 × logN × logN), 而每次修改操作的时间复杂度则为Θ((logN)^2)。
实现起来非常便捷。
注：事实上, 此题还可以用其他数据结构（如主席树）求解, 请感兴趣的同学自行查阅资料。
它并不是一个孤立存在的数据结构,而是建立在多种基本数据结构之上的复合体.其中较为容易实现的是线段_tree与线段_tree的嵌套以及线段_tree与平衡二叉搜索_tree的嵌套.对于一些较为复杂的问题而言,可能会涉及更为复杂的组合方式.要熟练掌握这种复杂的数据模型,则需要先深入理解各种基本数据结构,并在实践中不断积累经验.对于各类不同的题目,在解决时应迅速判断并选择最适合的方法.