洛谷P2617 Dynamic Rankings 题解

题意：

给定一个含有 \(n\) 个数的序列 \(a_1,a_2 \dots a_n\)，需要支持两种操作：

Q l r k 表示查询下标在区间 \([l,r]\) 中的第 \(k\) 小的数。

C x y 表示将 \(a_x\) 改为 \(y\) 。

输入格式：

第一行两个正整数 \(n,m\)，表示序列长度与操作个数。

第二行 \(n\) 个整数，表示 \(a_1,a_2 \dots a_n\)。

接下来 \(m\) 行，每行表示一个操作，都为上述两种中的一个。

输出格式：

对于每一次询问，输出一行一个整数表示答案。

数据范围：

\(1\le n,m \le 10^5\)，\(1 \le l \le r \le n\)，\(1 \le k \le r-l+1\)，\(1\le x \le n\)，\(0 \le a_i,y \le 10^9\)。

请注意常数优化，但写法正常的整体二分和树套树都可以以大约 \(1000\text{ms}\) 每个点的时间通过。

朴素的可持久化权值线段树（主席树）只能静态查询 \(k\) 小值。

具体地，我们查询前 \(r\) 棵树的前缀和减去前 \(l-1\) 棵树的前缀和。

如果直接在上面做单点修改操作，需要修改 \(\mathcal{O}(n \log n)\) 棵树，显然超时。

单点修改？维护前缀和？树状数组！（提示：用树维护树就是树套树）

那么我们用树状数组维护权值线段树的前缀和和单点修改即可（这个也叫带修主席树）。

注意维护的是权值线段树不是可持久化权值线段树，带修和不带修类似于树状数组和前缀和数组的差异。

时间复杂度 \(\mathcal{O}(n \log^2 n)\) ，空间复杂度 \(\mathcal{O}(n \log^2 n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define ls(at) tr[at].ls
#define rs(at) tr[at].rs
#define N ((int)(1e5 + 15))

int n, len, tot, a[N], o[N * 2], rt[N], tmp[2][25], cnt[2];
struct node { int ls, rs, v; } tr[N * 400];
struct qry { int op, x, y, k; } q[N];
int lowbit(int x) { return x & (-x); }
void Modify(int &at, int l, int r, int x, int v)
{
    if(!at) at = ++tot;
    tr[at].v += v; if(l == r) return;
    int mid = (l + r) >> 1;
    if(x <= mid) Modify(ls(at), l, mid, x, v);
    else Modify(rs(at), mid + 1, r, x, v);
}
void pre_Modify(int x, int v)
{
    int p = lower_bound(o + 1, o + 1 + len, a[x]) - o;
    for(int i = x; i <= n; i += lowbit(i)) Modify(rt[i], 1, len, p, v);
}
int Query(int l, int r, int k)
{
    if(l == r) return l;
    int mid = (l + r) >> 1, sum = 0;
    for(int i = 1; i <= cnt[0]; i++) sum -= tr[ls(tmp[0][i])].v;
    for(int i = 1; i <= cnt[1]; i++) sum += tr[ls(tmp[1][i])].v;
    if(k <= sum)
    {
        for(int i = 1; i <= cnt[0]; i++) tmp[0][i] = ls(tmp[0][i]);
        for(int i = 1; i <= cnt[1]; i++) tmp[1][i] = ls(tmp[1][i]);
        return Query(l, mid, k);
    }else
    {
        for(int i = 1; i <= cnt[0]; i++) tmp[0][i] = rs(tmp[0][i]);
        for(int i = 1; i <= cnt[1]; i++) tmp[1][i] = rs(tmp[1][i]);
        return Query(mid + 1, r, k - sum);
    }
}
int pre_Query(int l, int r, int k)
{
    memset(tmp, 0, sizeof(tmp)); cnt[0] = cnt[1] = 0;
    for(int i = l - 1; i; i -= lowbit(i)) tmp[0][++cnt[0]] = rt[i];
    for(int i = r; i; i -= lowbit(i)) tmp[1][++cnt[1]] = rt[i];
    return Query(1, len, k);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int m; cin >> n >> m; char op;
    for(int i = 1; i <= n; i++) { cin >> a[i]; o[++len] = a[i]; }
    for(int i = 1; i <= m; i++)
    {
        cin >> op; q[i].op = (op == 'Q') + 1;
        if(q[i].op == 2) { cin >> q[i].x >> q[i].y >> q[i].k; }
        else { cin >> q[i].x >> q[i].y; o[++len] = q[i].y; } 
    }
    sort(o + 1, o + len + 1); len = unique(o + 1, o + len + 1) - o - 1;
    for(int i = 1; i <= n; i++) pre_Modify(i, 1);
    for(int i = 1; i <= m; i++)
    {
        if(q[i].op == 1)
        {
            pre_Modify(q[i].x, -1);
            a[q[i].x] = q[i].y; pre_Modify(q[i].x, 1);
        } else { cout << o[pre_Query(q[i].x, q[i].y, q[i].k)] << '\n'; }
    }
    return 0;
}