题目链接：Luogu 2617

给定一个含有 $n$ 个数的序列 $a_i$，接下来有 $m$ 个询问，询问分为以下 $2$ 种：

• Q i j k：询问区间 $[i,j]$ 排序后的第 $k$ 个数。
• C i t：将 $a_i$ 修改为 $t$。

数据范围：$1\le n, m \le 10 ^ 5$，$0 \le a_i \le 10^9$。

Solution

整体二分

由于本题不强制在线，可以考虑整体二分。修改操作可以变成：删去 $a_i$，加入 $t$ 这两个操作。

树套树

使用树状数组套权值线段树。外面为树状数组维护前缀和，内部为权值线段树。之前主席树的前缀和任务交给了更擅长的树状数组维护。

修改时，我们修改 $\mathcal O(\log n)$ 棵权值线段树；查询时，统计的也是 $\mathcal O(\log n)$ 棵树，当然也要这 $\mathcal O(\log n)$ 个根节点一起跳左儿子或右儿子。

时间复杂度：两种算法均为 $\mathcal O(n\log^2 n)$，但是树套树常数很大。

空间复杂度：整体二分为 $\mathcal O(n)$，而树套树需要 $\mathcal O(n\log^2 n)$。

Code

整体二分

#include <cstdio>
#include <algorithm>

const int N = 3e5 + 5;
const int INF = 0x3f3f3f3f;

int n, m, a[N], ans[N];

struct Data {
    int opt, x, y, k, idx;
    Data(int _opt = 0, int _x = 0, int _y = 0, int _k = 0, int _idx = 0) {
        opt = _opt, x = _x, y = _y, k = _k, idx = _idx;
    }
} q[N], q1[N], q2[N];

struct BIT {
    int b[N];
    void modify(int x, int v) {
        for (; x <= n; x += x & -x) b[x] += v;
    }
    int query(int x) {
        int ans = 0;
        for (; x; x ^= x & -x) ans += b[x];
        return ans;
    }
} bit;

void solve(int l, int r, int L, int R) {
    if (l > r || L > R) {
        return;
    }
    if (l == r) {
        for (int i = L; i <= R; i++) {
            if (q[i].opt == 2) ans[q[i].idx] = l;
        }
        return;
    }
    int mid = (l + r) >> 1, t1 = 0, t2 = 0;
    for (int i = L; i <= R; i++) {
        if (q[i].opt == 1) {
            if (q[i].x <= mid) {
                q1[++t1] = q[i];
                bit.modify(q[i].idx, q[i].k);
            } else {
                q2[++t2] = q[i];
            }
        } else {
            int sum = bit.query(q[i].y) - bit.query(q[i].x - 1);
            if (sum >= q[i].k) {
                q1[++t1] = q[i];
            } else {
                q[i].k -= sum;
                q2[++t2] = q[i];
            }
        }
    }
    for (int i = 1; i <= t1; i++) {
        if (q1[i].opt == 1) bit.modify(q1[i].idx, -q1[i].k);
    }
    std::copy(q1 + 1, q1 + t1 + 1, q + L);
    std::copy(q2 + 1, q2 + t2 + 1, q + L + t1);
    solve(l, mid, L, L + t1 - 1);
    solve(mid + 1, r, L + t1, R);
}
int main() {
    scanf("%d%d", &n, &m);
    int tot = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        q[++tot] = Data(1, a[i], 0, 1, i);
    }
    int cnt = 0;
    for (int i = 1; i <= m; i++) {
        char s[5];
        scanf("%s", s);
        if (s[0] == 'Q') {
            int l, r, k;
            scanf("%d%d%d", &l, &r, &k);
            q[++tot] = Data(2, l, r, k, ++cnt);
        } else {
            int x, k;
            scanf("%d%d", &x, &k);
            q[++tot] = Data(1, a[x], 0, -1, x);
            a[x] = k;
            q[++tot] = Data(1, a[x], 0, 1, x);
        }
    }
    solve(-INF, INF, 1, tot);
    for (int i = 1; i <= cnt; i++) {
        printf("%d\n", ans[i]);
    }
    return 0;
}

树套树

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 2e5 + 5;

int n, m, sz, a[N], b[N];

struct Data {
    int opt, x, y, k;
} q[N];

struct Chairman {
    static const int M = 200 * N;
    int idx, rt[N], sum[M], ls[M], rs[M];
    void modify(int &p, int l, int r, int u, int x, int v) {
        p = ++idx, ls[p] = ls[u], rs[p] = rs[u], sum[p] = sum[u] + v;
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if (x <= mid) {
            modify(ls[p], l, mid, ls[u], x, v);
        } else {
            modify(rs[p], mid + 1, r, rs[u], x, v);
        }
    }
    int query(int l, int r, std::vector<int> L, std::vector<int> R, int k) {
        if (l == r) {
            return l;
        }
        int mid = (l + r) >> 1;
        int lsz = 0;
        for (int x: L) lsz -= sum[ls[x]];
        for (int x: R) lsz += sum[ls[x]];
        if (k <= lsz) {
            for (int &x: L) x = ls[x];
            for (int &x: R) x = ls[x];
            return query(l, mid, L, R, k);
        } else {
            for (int &x: L) x = rs[x];
            for (int &x: R) x = rs[x];
            return query(mid + 1, r, L, R, k - lsz);
        }
    }
} cha;

struct Bit {
    void modify(int x, int pos, int v) {
        for (; x <= n; x += x & -x) {
            cha.modify(cha.rt[x], 1, sz, cha.rt[x], pos, v);
        }
    }
    std::vector<int> getRoot(int x) {
        std::vector<int> ans;
        for (; x; x ^= x & -x) ans.push_back(cha.rt[x]);
        return ans;
    }
} bit;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        b[++sz] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        char s[5];
        scanf("%s", s);
        if (s[0] == 'Q') {
            scanf("%d%d%d", &q[i].x, &q[i].y, &q[i].k);
            q[i].opt = 1;
        } else {
            scanf("%d%d", &q[i].x, &q[i].k);
            q[i].opt = 2;
            b[++sz] = q[i].k;
        }
    }
    std::sort(b + 1, b + sz + 1);
    sz = std::unique(b + 1, b + sz + 1) - (b + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = std::lower_bound(b + 1, b + sz + 1, a[i]) - b;
    }
    for (int i = 1; i <= m; i++) {
        if (q[i].opt == 2) {
            q[i].k = std::lower_bound(b + 1, b + sz + 1, q[i].k) - b;
        }
    }
    for (int i = 1; i <= n; i++) {
        bit.modify(i, a[i], 1);
    }
    for (int i = 1; i <= m; i++) {
        if (q[i].opt == 1) {
            std::vector<int> L = bit.getRoot(q[i].x - 1);
            std::vector<int> R = bit.getRoot(q[i].y);
            printf("%d\n", b[cha.query(1, sz, L, R, q[i].k)]);
        } else {
            bit.modify(q[i].x, a[q[i].x], -1);
            a[q[i].x] = q[i].k;
            bit.modify(q[i].x, a[q[i].x], 1);
        }
    }
    return 0;
}