Luogu2617 Dynamic Rankings

Link

把一次修改操作拆成两个操作：

减去原位置的值（相当于加它的负数

加上新的值

就没了

#include <bits/stdc++.h>
using namespace std;

// 把a[x]修改为y相当于先把[0,x]所有数-a[x],再加y

const int SIZE = 4e5 + 5;
const int inf = 1e9;

int n, m, cnt, num;
int ans[SIZE], tree[SIZE], a[SIZE];

struct question {
    int l, r, val, opt;
} q[SIZE], lq[SIZE], rq[SIZE];

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline int lowbit(int x) { return x & (-x); }

inline int query(int pos) 
{
    int ans = 0;
    for ( ; pos; pos -= lowbit(pos)) ans += tree[pos];
    return ans;
}

inline void modify(int pos, int val)
{
    for ( ; pos <= n; pos += lowbit(pos)) tree[pos] += val;
}

inline void solve(int lval, int rval, int st, int ed)
{
    // printf("%d\n", ++ num);
    if (st > ed) return;
    if (lval == rval) {
        for (int i = st; i <= ed; ++ i) {
            if (q[i].opt > 0) ans[q[i].opt] = lval;
        }
        return;
    }
    int mid = (lval + rval) >> 1;
    int ltot = 0, rtot = 0;
    for (int i = st; i <= ed; ++ i) {
        if (q[i].opt == -1) {
            if (q[i].r <= mid) modify(q[i].l, -1), lq[++ ltot] = q[i];
            else rq[++ rtot] = q[i];
        }
        if (q[i].opt == 0) {
            if (q[i].r <= mid) modify(q[i].l, 1), lq[++ ltot] = q[i];
            else rq[++ rtot] = q[i];
        }
        if (q[i].opt > 0) {
            int tot = query(q[i].r) - query(q[i].l - 1);
            if (tot >= q[i].val) lq[++ ltot] = q[i];
            else q[i].val -= tot, rq[++ rtot] = q[i];
        }
    }
    for (int i = ed; i >= st; -- i) {
        if (q[i].r > mid) continue;
        if (q[i].opt == -1) modify(q[i].l, 1);
        if (q[i].opt == 0) modify(q[i].l, -1);
    }
    for (int i = 1; i <= ltot; ++ i) q[st + i - 1] = lq[i];
    for (int i = 1; i <= rtot; ++ i) q[st + ltot + i - 1] = rq[i];
    solve(lval, mid, st, st + ltot - 1);
    solve(mid + 1, rval, st + ltot, ed);
}

int main()
{
    n = read(), m = read();
    for (int i = 1; i <= n; ++ i) {
        a[i] = read();
        q[++ cnt].opt = 0, q[cnt].l = i, q[cnt].r = a[i];
    }
    int tim = 0;
    for (int i = 1; i <= m; ++ i) {
        char ch;
        std::cin >> ch;
        if (ch == 'Q') {
            q[++ cnt].opt = ++ tim, q[cnt].l = read(), q[cnt].r = read(), q[cnt].val = read();
        }
        if (ch == 'C') {
            int pos = read(), val = read();
            q[++ cnt].opt = -1, q[cnt].l = pos, q[cnt].r = a[pos];
            a[pos] = val;
            q[++ cnt].opt = 0, q[cnt].l = pos, q[cnt].r = a[pos];
        }
    }
    solve(-inf, inf, 1, cnt);
    for (int i = 1; i <= tim; ++ i) printf("%d\n", ans[i]);
    return 0;
}