思路

我们把所有的修改和询问操作按照时间顺序排成一个序列，考虑二分答案的范围为 $[l,r]$，当前处理的操作序列为 $[L,R]$。我们把贡献在 $[l,mid]$ 的操作分为一类，贡献在 $(mid, r]$ 的操作分为一类（注意。很显然这两类是相互独立的，那么可以将这两类分别递归处理。递归边界为 $l=r$，即当前操作序列 $[L,R]$ 的答案均为 $l$（或者 $r$）。

所谓贡献在某个区间，其含义为：对于某个询问，它的答案在这个区间内；对于某个修改，它修改的值在这个区间内。

特点

我们在什么题目里可以使用整体二分呢？题目需要满足以下性质：

1. 询问的答案具有可二分性。
2. 修改对判定答案的贡献相互独立，修改之间互不影响结果。
3. 修改如果对判定答案有贡献，则贡献为一个确定的与判定标准无关的值。
4. 贡献满足交换律、结合律，具有可加性。
5. 题目允许离线算法。

代码

我们以「Luogu 2617」Dynamic Rankings 为例。

#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;
}

习题

• 「Luogu 2617」Dynamic Rankings
• 「ZJOI 2013」K 大数查询
• 「POI 2011」Meteors
• 「CTSC 2018」混合果汁