awdec's Blog

整体二分是一种优秀的离线算法。对于可二分答案的问题，我们可以采用整体二分的方法处理多组询问。整体二分的思想非常巧妙，能够替代很多复杂的数据结构，代码也十分好写，是考场上的一大利器。

整体二分一般用于多次询问的问题。并且每次的询问都可以用二分答案的方式求解。

整体二分简单来说就是直接对于所有询问整体上二分一个答案。然后把询问按照是大于还是小于等于当前二分的答案划分到两个集合里去就行了。最后到二分答案的边界时，属于当前集合的询问的答案就是这个边界。

优化时间复杂度的关键不是笼统地说“多组询问共用一次 check”，而是同一递归层的所有事件只被整体扫描一次。设：

$E$ 是事件总数，包括询问以及参与判定的修改、加入等事件；
$V$ 是离散化后的候选答案数量，或整数答案区间 $[L, R]$ 的长度；
$F (N)$ 是处理一个事件时，对题目所用数据结构进行一次加入、撤销或查询的时间复杂度。

在递归的同一深度，各节点持有的事件集合互不相交，因此这一层扫描、划分的事件总数为 $O (E)$ ，而不是每个询问各做一次完整 check。答案值域每次减半，共有 $O (\log V)$ 层，所以单纯扫描和稳定划分的总成本为 $O (E \log V)$ 。

若每个事件还需要 $O (F (N))$ 的数据结构操作，则总时间复杂度为

O (E \log V F (N)) .

例如底层使用树状数组时，单次操作为 $O (\log N)$ ，整体二分部分通常为 $O (E \log V \log N)$ ；若事件可以 $O (1)$ 维护，则为 $O (E \log V)$ 。排序、离散化以及每层额外的清空或回滚成本应另外计入；事件数、答案值域和单次维护代价必须使用不同变量，不能混在一个含义不明的表达式中。

若递归划分时复用缓冲区，存放事件通常需要 $O (E)$ 空间，递归栈为 $O (\log V)$ ；题目数据结构自身的空间另计。

点击展开代码

cpp

void solve(int ql, int qr, int L, int R, int al, int ar) {
    if (ql > qr){
        for (int i = al; i <= ar; i++) // 加上 [L, R] 的贡献
        return;
    }
    if (al > ar)
        return;
    if (L == R) {
        for (int i = ql; i <= qr; i++)
            ans[Q[i].id] = L;
        for (int i = al; i <= ar; i++) // 加上 [L, R] 的贡献
        return;
    }
    int mid = L + R >> 1, cnt1 = 0, cnt2 = 0, ret1 = 0, ret2 = 0;

    for (int i = al; i <= ar; i++) {
        if (/* a[i] 信息 <= mid */) {
            update(a[i].id, 1);
        }
        if (/* a[i] 信息 <= mid */) {
            a1[++ret1] = a[i];
        } else {
            a2[++ret2] = a[i];
        }
    }
    for (int i = ql; i <= qr; i++) {
        if (/* Q[i] 的答案在 [l, mid] */) {
            Q1[++cnt1] = Q[i];
        } else {
            Q2[++cnt2] = Q[i];
        }
    }

    for (int i = al; i <= ar; i++)
        if (/* a[i] 信息 <= mid */)
            update(a[i].id, -1); // 把 [l, mid] 的贡献删去


    for (int i = 1; i <= cnt1; i++)
        Q[ql + i - 1] = Q1[i];
    for (int i = 1; i <= cnt2; i++)
        Q[ql + i - 1 + cnt1] = Q2[i];
    for (int i = 1; i <= ret1; i++)
        a[al + i - 1] = a1[i];
    for (int i = 1; i <= ret2; i++)
        a[al + i - 1 + ret1] = a2[i];

    solve(ql, ql + cnt1 - 1, L, mid, al, al + ret1 - 1);
    // 保证递归 [mid+1, R] 时 [l, mid] 的贡献都算了一遍
    solve(ql + cnt1, qr, mid + 1, R, al + ret1, ar);
}

扩展

有一种情况是，如果询问中同时带修，那么部分情况下，整体二分需要能够把修改的贡献在询问中减掉，然后递归。

例如带修的区间第 $k$ 大。

扩展 ​

扩展