BZOJ1901/洛谷2617 Dynamic Rankings（带修主席树模板）（树套树）

题意

给定一个 $n$ 个数的序列 $a_1,a_2,....,a_n$ ，有 $m$ 次操作：

$Q~ l~ r~ k$ 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
$C~x~y$ 表示将 $a_x$ 改成 $y$

其中， $x,k,n,m\leq 10^5,a_i,y\leq10^9$

前言

这道题网上很多人说用的是树状数组 + 主席树。其实这种说法是不对的！！主席树是可持久化权值线段树，在这题中并没有可持久化的体现。这题的做法仅仅是树状数组 + 权值线段树！！！

分析

动态 $k$ 大和静态 $k$ 大核心想法差不多，就是为了得到区间 $[l,r]$ 的权值线段树。但是如果按主席树来写，改变 $a_i$ 的值，要修改 $[i,n]$ 的每棵树，复杂度是不可接受的。
但是主席树的思想是值得借鉴的，就是第 $i$ 棵线段树其实是 $[1,i]$ 的权值线段树，和前缀和是很相似的。

我们联想一下单点修改，查询区间和的~~普及组~~题。
朴素做法是暴力修改 $[i,n]$ 的前缀和。
更优秀的做法是用树状数组维护每个位置的值，每个位置维护的是 $lowbit$ 长度的和。

动态 $k$ 大朴素的做法是暴力修改 $[i,n]$ 的线段树。
于是我们~~容易想到~~更优秀的做法是用树状数组来维护每一颗权值线段树，每一颗权值线段树维护的是 $lowbit$ 长度的区间。（话说为什么其他 $blog$ 很少提到这个关键点QAQ

于是，当 $a_i$ 修改时，我们要更改 $i$ 所参与的权值线段树，也就是一直加 $lowbit$ 的过程，代码长这样：
在这里插入图片描述 $update$ 操作就是普通权值线段树的操作。
看起来是不是很简单！！！

下面我们讨论一下查询操作。
要得到 $[l,r]$ 的权值线段树，就像要得到 $[l,r]$ 的区间和，我们是不是只用将 $[1,r]$ 的权值线段树减去 $[1,l-1]$ 的权值线段树就好了啊！
设 $bit_i$ 为 $i$ 二进制中 $1$ 的个数。
那么根据树状数组， $[1,r]$ 的权值线段树的每个节点的值就是由 $bit_r$ 棵线段树的对应节点的值的和。同理， $[1,l-1]$ 的每个节点的值我们也可以用树状数组快速求出。
实现的时候，我们先将参与 $[1,r]$ 的线段树们都记下来，记为 $R_i$ 。再将参与 $[1,l-1]$ 的线段树们都记下来，记为 $L_i$ 。这样 $[l,r]$ 的权值线段树的某个节点 $a$ 的值，就是 $\sum R_{i,a}-\sum L_{i,a}$ 。
代码大概长这样：
在这里插入图片描述

于是就可以像普通权值线段树那样二分求第 $k$ 小了。

时空复杂度

树状数组复杂度是 $O(logn)$ 的，每次插入和查询单颗线段树的复杂度也是 $O(logn)$ 的，最终时间和空间复杂度是 $O(nlog^2n)$ 的。空间需求还是很大的。
虽然一般空间跑不满，但还是要尽量开大（不然RE了就gg了

代码如下（感觉代码还是很清晰的）

#include <bits/stdc++.h>
#define lson l, m, lch[rt]
#define rson m + 1, r, rch[rt]
#define N 100005
using namespace std;
int read(){
    int x, f = 1;
    char ch;
    while(ch = getchar(), ch < '0' || ch > '9') if(ch == '-') f = -1;
    x = ch - '0';
    while(ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - 48;
    return x * f;
}
char o[3];
int cnt, cur1, cur2, L[N], R[N], root[N], lch[N * 200], rch[N * 200], sum[N * 200], a[N], b[N * 2], flag[N], x[N], y[N], K[N];
void update(int l, int r, int &rt, int p, int c){
    if(!rt) rt = ++cnt;
    sum[rt] += c;
    if(l == r) return;
    int m = l + r >> 1;
    if(p <= m) update(lson, p, c);
    else update(rson, p, c);
}
int query(int l, int r, int k){
    if(l == r) return l;
    int i, m = l + r >> 1, siz = 0;
    for(i = 1; i <= cur1; i++) siz -= sum[lch[L[i]]];
    for(i = 1; i <= cur2; i++) siz += sum[lch[R[i]]];
    if(siz >= k){
        for(i = 1; i <= cur1; i++) L[i] = lch[L[i]];
        for(i = 1; i <= cur2; i++) R[i] = lch[R[i]];
        return query(l, m, k);
    }
    else{
        for(i = 1; i <= cur1; i++) L[i] = rch[L[i]];
        for(i = 1; i <= cur2; i++) R[i] = rch[R[i]];
        return query(m + 1, r, k - siz);
    }//就想普通权值线段树那样二分 
}
int main(){
    int i, j, n, m, T, tot;
    n = read(); m = read();
    for(i = 1; i <= n; i++) a[i] = read(), b[++tot] = a[i];
    for(i = 1; i <= m; i++){
        scanf("%s", o);
        if(o[0] == 'Q') flag[i] = 1, x[i] = read(), y[i] = read(), K[i] = read();
        else x[i] = read(), y[i] = read(), b[++tot] = y[i];
    }//由于要离散化，所以要先把询问读入 
    sort(b + 1, b + tot + 1);
    tot = unique(b + 1, b + tot + 1) - b - 1;
    for(i = 1; i <= n; i++){
        a[i] = lower_bound(b + 1, b + tot + 1, a[i]) - b;
        for(j = i; j <= n; j += j & -j) update(1, tot, root[j], a[i], 1);
    } 
    for(i = 1; i <= m; i++){
        if(flag[i]){
            x[i]--; cur1 = cur2 = 0;
            for(j = x[i]; j > 0; j -= j & -j) L[++cur1] = root[j]; 
            for(j = y[i]; j > 0; j -= j & -j) R[++cur2] = root[j];//先得到参与的线段树们 
            printf("%d\n", b[query(1, tot, K[i])]);
        }
        else{
            y[i] = lower_bound(b + 1, b + tot + 1, y[i]) - b;
            for(j = x[i]; j <= n; j += j & -j) update(1, tot, root[j], a[x[i]], -1), update(1, tot, root[j], y[i], 1);
            a[x[i]] = y[i];
        }
    }
    return 0;
}