【学习笔记】Dynamic Rankings
NCC79601
2019-03-16 03:17:21
题目[P2617](https://www.luogu.org/problemnew/solution/P2617)
顾名思义，$Dynamic$ $Rankings$是指一种可以**动态查询区间第$k$小**的数据结构。这里可以用树状数组$+$线段树$+$主席树来维护，具体为用树状数组来保存线段树历史版本的前缀和，然后用主席树思想查询区间第$k$小值。这差不多都能算作**树套树套树**了，如果可以很快打出来，代码能力会提高不少。
# 动态建树
这里由于需要将输入数据**离散化**，所以是先读入完了再建树。建线段树的过程当中也可以顺便把树状数组给更新了，比如这里就表示当前以$x$为根节点新建一个子树，作为线段树的一个历史版本，并用树状数组$C[i]$维护区间节点个数信息。由于树状数组维护前缀和非常方便，查询起来也非常快，所以这里选择用树状数组储存前缀和信息。
```cpp
inline void build_tree(int &x, int l, int r, int k, int d) {
if(!x)
x = ++cnt;
C[x] += d;
if(l == r)
return;
int mid = (l + r) >> 1;
if(k <= mid)
build_tree(tree[x].ls, l, mid, k, d);
else
build_tree(tree[x].rs, mid+1, r, k, d);
return;
}
```
# 修改+更新主席树
由于主席树特性，相邻历史版本之间只有一条链的差距，所以在进行更新版本的时候可以使用刚才的$build\_tree()$进行操作，操作的时候也要顾及树状数组特性，由$C[x]$向$C[n]$进行覆盖。
不过这里还有个玄学操作，那就是$lower\_bound()$居然还可以这样用！**通过$lower\_bound()$减去序列名，就可以直接得到下标**，这招学到了。这里$\_x$表示第一个需要修改的线段树/树状数组标号。
```cpp
inline void edit_tree(int x, int t) {
int _x = lower_bound(b+1, b+_n+1, a[x]) - b;
for(register int i = x; i <= n; i += lowbit(i))
build_tree(root[i], 1, _n, _x, t);
return;
}
```
# 查询第$k$小
这里利用的就是主席树的思想了，**用线段树在$r$节点的信息减去线段树在$l-1$节点的信息就可以得到$[l,r]$区间信息**。静态主席树可以直接$O(1)$跑出来，但是如果涉及到了修改，一般就只能用$O(n)$去跑。但是由于之前我们维护了一个树状数组$C[i]$，所以可以直接加速查询速度至$O(logn)$，相对地就可以跑得快一些了。
如果已经预处理出了所有需要查询到的树状数组下标，那么直接跑一次差分就完事了。这里$t1[i]$和$t2[i]$表示的就是需要查询到的树状数组的下标，所以$sum$先加上$C[tree[t2[i]].ls]$再减去$C[tree[t1[i]].ls]$，得到的就是两版本左子树不同节点的个数。如果$sum\ge k$，就说明左边节点数比查询的$k$要多，所以向左儿子跳去，即：把所有的$t1[i]$、$t2[i]$更新为对应线段树的左儿子，然后递归；否则向右儿子跳去，找右子树内第$k-sum$小即可。
```cpp
inline int QueryKth(int l, int r, int k) {
if(l == r)
return l;
int mid = (l + r) >> 1;
int sum = 0;
for(register int i = 1; i <= n2; i++)
sum += C[tree[t2[i]].ls];
for(register int i = 1; i <= n1; i++)
sum -= C[tree[t1[i]].ls];
if(sum >= k) {
for(register int i = 1; i <= n1; i++)
t1[i] = tree[t1[i]].ls;
for(register int i = 1; i <= n2; i++)
t2[i] = tree[t2[i]].ls;
return QueryKth(l, mid, k);
}
else {
for(register int i = 1; i <= n1; i++)
t1[i] = tree[t1[i]].rs;
for(register int i = 1; i <= n2; i++)
t2[i] = tree[t2[i]].rs;
return QueryKth(mid+1, r, k-sum);
}
}
```
# 查询的处理过程
查询$[l,r]$的第$k$小元素的时候，先预处理出所有待处理的树状数组的标号，然后直接从$[1,\_n]$开始查找即可（$\_n$是离散化之后的区间长度）。
```cpp
inline int QueryKth_Pre(int l, int r, int k) {
n1 = n2 = 0;
for(register int i = l - 1; i >= 1; i -= lowbit(i))
t1[++n1] = root[i];
for(register int i = r; i >= 1; i -= lowbit(i))
t2[++n2] = root[i];
return QueryKth(1, _n, k);
}
```
# 骚气的$\textbf{unique()}$离散化
离散化本身挺蛋疼，之前我还在用这种基础写法：
```cpp
inline void Discrete() {
sort(node+1, node+n+1);
a[node[1].id] = 1;
rev[1] = node[1].num;
for(register int i = 2; i <= n; i++) {
if(node[i].num != node[i-1].num)
id++;
a[node[i].id] = id;
rev[id] = node[i].num;
}
return;
}
```
虽然很蠢，却是最中用的。
不过，现在看来这个样子搞完全是没有必要了。又是一个强大的$STL$——
### $\textbf{STL}$大法好！上网搜索$\textbf{unique()}$有真相！
一种叫做$unique()$的$STL$可以**直接帮我们完成去重的操作**，并**返回离散化之后序列的$end()$迭代器**。上面也有提到，**迭代器减去序列名就可以直接得到下标**，所以这样两句话就可以完成排序$+$离散化操作：
```cpp
sort(b+1, b+1+_n);
_n = unique(b+1, b+1+_n) - b - 1;
```
其中$\_n$即为离散化之后的序列长度，上文有提到。这个$unique()$真是太好了哇！
$main()$函数也写得差不多就可以了。需要注意修改点权的时候，$edit\_tree(c[i],-1)$后要**先把$\textbf{a[c[i]]}$给更新为$\textbf{d[i]}$**，然后再$\textbf{edit\_tree(c[i],1)}$，这个样子就成功完成了修改。
```cpp
int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[++_n] = a[i];
}
for(register int i = 1; i <= m; i++) {
char ch = getchar();
while(ch != 'Q' &&ch != 'C')
ch = getchar();
if(ch == 'Q')
scanf("%d%d%d", &c[i], &d[i], &e[i]);
else {
scanf("%d%d", &c[i], &d[i]);
b[++_n] = d[i];
}
}
sort(b+1, b+1+_n);
_n = unique(b+1, b+1+_n) - b - 1;
for(register int i = 1; i <= n; i++)
edit_tree(i, 1);
for(register int i = 1; i <= m; i++) {
if(e[i])
printf("%d\n", b[QueryKth_Pre(c[i], d[i], e[i])]);
else {
edit_tree(c[i], -1);
a[c[i]] = d[i];
edit_tree(c[i], 1);
}
}
return 0;
}
```
---
完整代码
```cpp
//code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 500010;
int a[MAXN], b[MAXN], c[MAXN], d[MAXN], e[MAXN];
struct SEGTREE {
int ls, rs, v;
} tree[MAXN * 20];
int C[MAXN * 20];
int n1, n2, t1[MAXN], t2[MAXN];
int cnt = 0, root[MAXN];
int n, _n, m;
inline int lowbit(int x) {
return x & (-x);
}
inline void build_tree(int &x, int l, int r, int k, int d) {
if(!x)
x = ++cnt;
C[x] += d;
if(l == r)
return;
int mid = (l + r) >> 1;
if(k <= mid)
build_tree(tree[x].ls, l, mid, k, d);
else
build_tree(tree[x].rs, mid+1, r, k, d);
return;
}
inline void edit_tree(int x, int t) {
int _x = lower_bound(b+1, b+_n+1, a[x]) - b;
for(register int i = x; i <= n; i += lowbit(i))
build_tree(root[i], 1, _n, _x, t);
return;
}
inline int QueryKth(int l, int r, int k) {
if(l == r)
return l;
int mid = (l + r) >> 1;
int sum = 0;
for(register int i = 1; i <= n2; i++)
sum += C[tree[t2[i]].ls];
for(register int i = 1; i <= n1; i++)
sum -= C[tree[t1[i]].ls];
if(sum >= k) {
for(register int i = 1; i <= n1; i++)
t1[i] = tree[t1[i]].ls;
for(register int i = 1; i <= n2; i++)
t2[i] = tree[t2[i]].ls;
return QueryKth(l, mid, k);
}
else {
for(register int i = 1; i <= n1; i++)
t1[i] = tree[t1[i]].rs;
for(register int i = 1; i <= n2; i++)
t2[i] = tree[t2[i]].rs;
return QueryKth(mid+1, r, k-sum);
}
}
inline int QueryKth_Pre(int l, int r, int k) {
n1 = n2 = 0;
for(register int i = l - 1; i >= 1; i -= lowbit(i))
t1[++n1] = root[i];
for(register int i = r; i >= 1; i -= lowbit(i))
t2[++n2] = root[i];
return QueryKth(1, _n, k);
}
int main() {
scanf("%d%d", &n, &m);
for(register int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
b[++_n] = a[i];
}
for(register int i = 1; i <= m; i++) {
char ch = getchar();
while(ch != 'Q' &&ch != 'C')
ch = getchar();
if(ch == 'Q')
scanf("%d%d%d", &c[i], &d[i], &e[i]);
else {
scanf("%d%d", &c[i], &d[i]);
b[++_n] = d[i];
}
}
sort(b+1, b+1+_n);
_n = unique(b+1, b+1+_n) - b - 1;
for(register int i = 1; i <= n; i++)
edit_tree(i, 1);
for(register int i = 1; i <= m; i++) {
if(e[i])
printf("%d\n", b[QueryKth_Pre(c[i], d[i], e[i])]);
else {
edit_tree(c[i], -1);
a[c[i]] = d[i];
edit_tree(c[i], 1);
}
}
return 0;
}
```