整体二分类似于线段树上二分，在讲这个算法前，先引入几个问题。

解决题型

整体二分一般解决的是如下的问题：

给你一个【集合/序列/矩阵/树】，要求【静态/动态】维护所有【元素/区间/子矩阵/链/子树】中的第 $k$【可能每次给定】大元素，【可能强制在线】。

下面是一堆例题。

例题1 动态查询集合第k大（可离线）

题意

让你维护一个初始为空的多重集合 $s$，并支持 $q$ 次操作，操作都是下面三种之一：

  • 添加一个数 $x$ 到集合 $s$ 中。
  • 在集合 $s$ 中删除一个数 $x$（保证元素存在）。
  • 查询集合第 $k$ 大（保证第 $k$ 大存在）。

数据范围

  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq x \leq 10^9$

题解

维护一个权值线段树（权值线段树其实就是一个维护值域的线段树），维护一段值域里有多少个数，每次询问在线段树上二分即可。

具体地，对于线段树上某个节点对应的区间 $[l,r]$，这个节点上的值为集合中，值在 $[l,r]$ 的数的个数有多少。

在询问时，我们要记录当前节点编号 $x$，$x$ 维护区间 $[l,r]$，以及要查询值在 $[l,r]$ 内的所有数的第 $k$ 大。

当递归到某个状态后，我们看这个节点的左子树 $\text{lc}$ 内有多少个值，如果大于等于 $k$，则递归到左子树；否则递归到右子树，且 $k$ 减去(左子树内数的个数)。

由于值域较大，权值线段树可能会爆，所以要先把所有询问离线下来，做个离散化，然后就可以把 $x$ 控制到 $q$ 级别，就不会爆了。

修改操作就是典中典了，此处不再赘述。

时间复杂度：$O(q \log q)$

例题2 动态查询集合第k大（强制在线）

题意

同上，不过加了个强制在线的限制。

数据范围

同上。

题解

此时就不能离线，然后离散化了。

此时有四种做法：

  1. 动态开点线段树，时间复杂度：$O(q \log^2 q)$
  2. PBDS（笔记），时间复杂度：$O(q \log q)$
  3. 平衡树，时间复杂度：$O(q \log q)$
  4. 对顶堆，时间复杂度：$O(q \log q)$

    有人一看“对顶堆”就感觉很难，但其实很好理解。

    （注：使用该做法的前提是 $k$ 是一个定值）

    我们维护一个小根堆 $h_1$ 和一个大根堆 $h_2$。

    $h_1$ 里维护的是前 $k$ 大，$h_2$ 里则是维护的其他值。

    由于涉及删除（查找），所以要用set，而不是priority_queue。

    每次添加操作，先加入到 $h_1$ 里，如果说 $h_1$ 的大小大于 $k$（显然只可能是 $k+1$），那么弹出 $h_1$ 内的最小元素，并加入到 $h_2$。

    每次删除操作，如果 $h_2$ 里有删除的元素，直接在 $h_2$ 里删；否则在 $h_1$ 里删，如果说 $h_1$ 的大小小于 $k$（显然只可能是 $k-1$），那么弹出 $h_2$ 内的最大元素，并加入到 $h_1$。

    每次查询操作，直接弹出 $h_1$ 内的最小值即可。

    上面做法里只涉及几种操作：

    • 添加元素（multiset.insert(LL)，复杂度为 $O(\log n)$）
    • 找到元素出现位置/判断元素是否存在（multiset.find(LL)，复杂度为 $O(\log n)$）

      注意，这里不能使用multiset.count(LL)，因为这个函数的复杂度其实是 $O(\log n+\text{cnt})$，其中 $\text{cnt}$ 为返回值。

      而这样的复杂度显然会被特殊数据卡到 $\text{cnt}=n$，也就炸了。

    • 删除元素（multiset.erase(multiset::iterator)，复杂度均摊常数）

      有人问为啥不能直接用multiset.erase(LL)？有两个原因：

      1. multiset.erase(LL)会直接删除这个multiset中所有与传参相同的位置，但题目说的是只删除一个，所以会WA。
      2. 直接用multiset.erase(multiset::iterator)复杂度是均摊常数的（如果要加上multiset.find(LL)的复杂度，也只是 $O(\log n)$ 而已），但multiset.erase(LL)的复杂度是 $O(\log n+\text{cnt})$，会TLE。

    所以总复杂度为 $O(q \log q)$。

例题3 静态查询区间第k小（可离线）

题意

给你一个长度为 $n$ 的数组 $a$，你要回答 $q$ 次询问，每次询问会给定 $l$、$r$、$k$，问你 $a_l \sim a_r$ 内第 $k$ 小的数是多少。

数据范围

  • $1 \leq n \leq 2 \times 10^5$
  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq a_i \leq n$

题解

一看这道题，再看例题1的解法，有些人就想到了主席树（可持久化线段树），然后直接开干，$O((n+q) \log n)$ 的复杂度，稳过。

上面这种做法比下面要讲的整体二分还要少一个 $\log$，不过缺点是，这个代码忒长了。

下面讲一下整体二分。

概览

整体二分，顾名思义就是「对整体做线段树上二分」，而具体怎么个思路呢？见下。

整体二分本质还是一个分治。

设计分治函数

看到「（权值）线段树上二分」，那么分治里必须有值域。

再看例题1的做法，在例题1里，整体来看，每当递归到一个节点，我们就是把问题分为了两类：一类去了左儿子，一类则是去了右儿子。

这里也一样，于是我们就得到了一个分治函数：$\text{solve}(l,r,q_l,q_r)$，代表已经确定了第 $q_l$ 个询问到第 $q_r$ 个询问（我们已经把所有询问都存到了一个数组，且这个数组可能会随时变化）的答案在 $[l,r]$ 内。

就像本题，初始的状态就是 $\text{solve}(1,n,1,q)$。

询问分类

接下来考虑把这些询问分成两类：一类答案在 $[l,\text{mid}]$ 内，另一类答案在 $[\text{mid}+1,r]$ 内，其中 $\text{mid}$ 为区间 $[l,r]$ 的中点下标。

对于一个询问 $(c_l,c_r,c_k)$，分类看的其实就是 $a_{c_l} \sim a_{c_r}$ 内有多少值在 $[l,\text{mid}]$ 内的下标，是否大于等于 $c_k$。

上面说的值域 $[l,\text{mid}]$ 是固定的，所以我们考虑维护一个树状数组。

在初始时，对于所有值在 $[l,\text{mid}]$ 内的下标 $x$ 都加 $1$。

有人感觉描述有点模糊，此处用数学方式表达一下。

我们把所有满足 $a_x \in [l,\text{mid}]$ 的 $x$（$1 \leq x \leq n$）全部加入一个集合 $s$，然后对于 $s$ 中的所有值 $v$，在树状数组的 $v$ 下标上加 $1$（add(v,1)）。

但直接实现会TLE，我们考虑在初始时，就记录一个vector数组 $\text{pos}$，$\text{pos}_i$ 为一个vector，存储满足 $a_x=i$ 的 $x$ 集合。

然后，直接遍历 $i \in [l,\text{mid}]$，并对于每个 $i$，循环所有 $x \in \text{pos}_i$，并在树状数组的 $x$ 位置上加 $1$ 即可。

所以就可以很快分类了，我们直接看树状数组的下标 $c_l \sim c_r$ 上的值的和 $\text{sum}$，如果 $\text{sum} \geq c_k$，则该询问 $(c_l,c_r,c_k)$ 分到“左子树类”，否则分到“右子树类”。

由于要分类，所以需要记录一个临时数组防止WA。

到最后，我们就讲这个问题变成了两个子问题：一个 $\text{solve}(l,\text{mid},左子树类下标区间)$，另一个 $\text{solve}(\text{mid}+1,r,右子树类下标区间)$。

边界情况

最后是一些边界。

如果我们发现 $q_l>q_r$，那么就说明考虑范围为空，return。

如果 $l=r$，就说明询问 $q_l \sim q_r$ 的答案唯一，都是 $l$，直接赋值即可，return。

时间复杂度：$O((n+q) \log^2 n)$

代码

const LL N = 2e5 + 10, Q = 2e5 + 10;

LL n, qc;
LL a[N];
LL l, r, k;

bs<LL> pos[N];

struct Query{ LL l, r, k, id; };
Query q[Q];
Query b[Q];

#define lowbit(x) ((x) & (-(x)))
LL c[N];
void add(LL x, LL v){ for(LL i = x;i <= n;i += lowbit(i)) c[i] += v; }
LL query(LL x){ LL ret = 0; for(LL i = x;i;i -= lowbit(i)) ret += c[i]; return ret; }

LL ans[Q];

void work(LL l, LL r, LL ql, LL qr){
    if(l > r || ql > qr) return;
    if(l == r){
        rep(i, ql, qr) ans[q[i].id] = l;
        return;
    }
    
    LL mid = l + (r - l) / 2;
    rep(i, l, mid)
        for(auto x : pos[i])
            add(x, 1);
    
    LL pa = ql, pb = qr;
    rep(i, ql, qr){
        LL l = q[i].l, r = q[i].r, k = q[i].k;
        LL s = query(r) - query(l - 1);
        if(s >= k) b[pa++] = q[i];
        else q[i].k -= s, b[pb--] = q[i];
    }
    
    rep(i, ql, qr) q[i] = b[i];
    
    rep(i, l, mid)
        for(auto x : pos[i])
            add(x, -1);
    
    work(l, mid, ql, pa - 1), work(mid + 1, r, pb + 1, qr);
}

void solve(){
    rd(n), rd(qc);
    rep(i, 1, n) rd(a[i]), pos[a[i]] += i;
    rep(i, 1, qc) rd(l), rd(r), rd(k), q[i] = {l, r, k, i};
    
    work(1, n, 1, qc);
    
    rep(i, 1, qc) printf("%lld\n", ans[i]);
}

例题4 静态查询区间第k小（强制在线）

题意

同上，不过加了个强制在线的限制。

数据范围

同上。

题解

本题可用树状数组套主席树以 $O((n+q) \log^2 n)$ 的复杂度解决。

例题5 动态查询区间第k小（可离线）

题意

给你一个长度为 $n$ 的数组 $a$，你要处理 $q$ 次操作，每次操作分两种：

  • 操作：给定 $x$、$v$，将 $a_x$ 的值更改为 $v$。
  • 询问：给定 $l$、$r$、$k$，问你 $a_l \sim a_r$ 内第 $k$ 小的数是多少。

数据范围

  • $1 \leq n \leq 2 \times 10^5$
  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq a_i \leq 10^9$

题解

一看这道题，再看例题1的解法，有些人就想到了树状数组套主席树，然后直接开干，$O((n+q) \log^2 n)$ 的复杂度，稳过。

上面这种做法比下面要讲的带修整体二分复杂度一样，不过缺点是，这个代码忒长了。

下面讲一下带修整体二分。

概览

带修整体二分其实就是「带修改的整体二分」。

带修整体二分和普通整体二分代码差别很大，但思想一致。

注意：和CDQ分治一样，$\text{solve}(l,r,q_l,q_r)$ 代表的是，只考虑 $q_l \sim q_r$ 内的修改，去更新 $q_l \sim q_r$ 内的查询。

变化修改操作

看见这个修改操作，也是最难搞的一个操作。

但修改操作本身难搞，并不代表转化后难搞。

我们把一次修改操作 $(x,v)$ 变化成两部分：

  • 第一步：$a_x$ 减去 $a_x$
  • 第二步：$a_x$ 加上 $v$

这样变化后，我们就可以继续设计新的分治思路了。

变化分治函数

还是一样的思路，我们要把第 $q_l$ 到第 $q_r$ 个询问分类。

但这里带上了修改操作，不太好处理。

但也不是不能处理，我们直接去遍历 $i=q_l \sim q_r$：

  • 如果说第 $i$ 个操作是修改，我们假设是 $a_x$ 加上 $v \times \text{mul}$（$\text{mul} \in { -1,1 }$）的操作：
    • 那么，由于 $v$ 不是修改前 $a_x$ 的值，就是修改后 $a_x$ 的值，所以通过 $v$ 即可得到修改前/后的值。
    • 所以：
      • 如果我们发现 $v \leq \text{mid}$，那么，就需要在树状数组上做修改：在位置 $x$ 上加上值 $\text{mul}$，很容易理解，此处略。
        • 同时，即使当前操作是修改，也要加入到第一类操作中。
      • 否则，加入到第二类操作中，而不改变树状数组。
  • 如果第 $i$ 个操作是询问 $(l,r,k)$：
    • 那么我们找到树状数组第 $l$ 到 $r$ 个位置上数的和 $\text{cnt}$。
    • 然后就是一样的处理了：
      • 如果 $\text{cnt} \geq k$，则加入到第一类操作中。
      • 否则，将 $k$ 减去 $\text{cnt}$ 并加入到第二类操作中。

（很好理解，此处略）

时间复杂度：$O((n+q) \log^2 n)$

代码

const LL N = 1e5 + 10, Q = 3e5 + 10;

LL n, qc;
LL a[N];
char opt[2];
LL x, v;
LL l, r, k;

LL ma;

struct Query{
    //opt=1：修改操作，a[x]+=v*mul
    //opt=2：查询操作，查询a[l]~a[r]内的第k大，并将答案存入ans[qid]
    LL opt;
    LL x, v, mul;
    LL l, r, k;
    LL qid;
};

Query q[Q];
LL qi;

Query b[Q];

#define lowbit(x) ((x) & (-(x)))
LL c[N];
void add(LL x, LL v){ for(LL i = x;i <= n;i += lowbit(i)) c[i] += v; }
LL query(LL x){ LL ret = 0; for(LL i = x;i;i -= lowbit(i)) ret += c[i]; return ret; }

LL ans[Q];

void work(LL l, LL r, LL ql, LL qr){
    if(l > r || ql > qr) return;
    if(l == r){
        rep(i, ql, qr) if(q[i].opt == 2) ans[q[i].qid] = l;
        return;
    }
    
    LL mid = l + (r - l) / 2;
    LL pa = ql, pb = qr;
    rep(i, ql, qr)
        if(q[i].opt == 1){
            if(q[i].v <= mid) add(q[i].x, q[i].mul), b[pa++] = q[i];
            else b[pb--] = q[i];
        }else{
            LL cnt = query(q[i].r) - query(q[i].l - 1);
            if(cnt >= q[i].k) b[pa++] = q[i];
            else q[i].k -= cnt, b[pb--] = q[i];
        }
    
    rep(i, ql, qr) if(q[i].opt == 1 && q[i].v <= mid) add(q[i].x, -q[i].mul);
    
    rep(i, ql, qr) q[i] = b[i];
    //q[pb+1]~q[qr]在上面是倒序赋值的，所以此处要把q[pb+1]~q[qr]翻转一下
    reverse(q + pb + 1, q + qr + 1);
    work(l, mid, ql, pa - 1), work(mid + 1, r, pb + 1, qr);
}

void solve(){
    rd(n), rd(qc);
    rep(i, 1, n){
        rd(a[i]);
        
        //初始值处理
        q[++qi] = {1, i, a[i], 1};
        ma = max(ma, a[i]);
    }
    LL qryc = 0;
    rep(i, 1, qc){
        scanf("%s", opt);
        if((*opt) == 'C'){
            rd(x), rd(v);
            
            q[++qi] = {1, x, a[x], -1};
            q[++qi] = {1, x, v, 1};
            a[x] = v;
            //最大值更新要带上修改操作
            ma = max(ma, v);
        }else if((*opt) == 'Q'){
            rd(l), rd(r), rd(k);
            
            q[++qi] = {2, 0, 0, 0, l, r, k, ++qryc};
        }
    }
    
    work(0, ma, 1, qi);
    
    rep(i, 1, qryc) printf("%lld\n", ans[i]);
}

例题6 动态查询区间第k小（强制在线）

题意

同上，不过加了个强制在线的限制。

数据范围

同上。

题解

本题可用树状数组套主席树以 $O((n+q) \log^2 n)$ 的复杂度解决。

例题7 静态查询子矩阵第k小（可离线）

题意

给你一个大小为 $n \times m$ 的矩阵 $a$，你要处理 $q$ 次询问，每次询问给定 $x_1$、$y_1$、$x_2$、$y_2$、$k$，问你以 $(x_1,y_1)$ 为左上角、以 $(x_2,y_2)$ 为右下角的子矩阵的第 $k$ 小的数是多少。

数据范围

  • $1 \leq n,m \leq 2 \times 10^3$
  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq a_i \leq 10^9$

题解

这题和例题3几乎没有什么区别，只不过平面维度变成了二维。

所以，我们就需要用到二维树状数组。

这里简单说一下原理。

一维树状数组里，$c_x$ 维护的是区间 $(x-\text{lowbit}(x),x]$ 的某个值。

同理，在二维树状数组里，$c_{x,y}$ 就代表X坐标在 $(x-\text{lowbit}(x),x]$ 内、Y坐标在 $(y-\text{lowbit}(y),y]$ 内的这个子矩阵的某个值。

所以，其实add和query函数也差不了多少，详情见代码，很好理解。

时间复杂度：$O((n+q) \log^3 n)$

代码

const LL N = 2010, A = 4e6 + 10, Q = 6e4 + 10;

LL n, qc;
LL a[N][N];
LL xa, ya, xb, yb, k;

bs<LL> alls;
#define find(x) (lower_bound(all(alls), x) - alls.begin() + 1)
LL nn;

vector<PII> pos[A];

struct Query{ LL xa, ya, xb, yb, k, id; };
Query q[Q];
Query b[Q];

#define lowbit(x) ((x) & (-(x)))
LL c[N][N];
void add(LL x, LL y, LL v){
    for(LL i = x;i <= n;i += lowbit(i))
        for(LL j = y;j <= n;j += lowbit(j))
            c[i][j] += v;
}
LL query(LL x, LL y){
    LL ret = 0;
    for(LL i = x;i;i -= lowbit(i))
        for(LL j = y;j;j -= lowbit(j))
            ret += c[i][j];
    return ret;
}
LL query_zi(LL xa, LL ya, LL xb, LL yb){
    return query(xb, yb) - query(xa - 1, yb) - query(xb, ya - 1) + query(xa - 1, ya - 1);
}

LL ans[Q];

void work(LL l, LL r, LL ql, LL qr){
    if(l > r || ql > qr) return;
    if(l == r){
        rep(i, ql, qr) ans[q[i].id] = l;
        return;
    }
    
    LL mid = l + (r - l) / 2;
    rep(i, l, mid)
        for(auto it : pos[i])
            add(it.fir, it.sec, 1);
    
    LL pa = ql, pb = qr;
    rep(i, ql, qr){
        LL xa = q[i].xa, ya = q[i].ya, xb = q[i].xb, yb = q[i].yb, k = q[i].k;
        LL s = query_zi(xa, ya, xb, yb);
        if(s >= k) b[pa++] = q[i];
        else q[i].k -= s, b[pb--] = q[i];
    }
    
    rep(i, ql, qr) q[i] = b[i];
    
    rep(i, l, mid)
        for(auto it : pos[i])
            add(it.fir, it.sec, -1);
    
    work(l, mid, ql, pa - 1), work(mid + 1, r, pb + 1, qr);
}

void solve(){
    rd(n), rd(qc);
    rep(i, 1, n) rep(j, 1, n) rd(a[i][j]), alls += a[i][j];
    
    sort(all(alls));
    alls.erase(unique(all(alls)), alls.end());
    nn = alls.size();
    
    rep(i, 1, n) rep(j, 1, n) a[i][j] = find(a[i][j]), pos[a[i][j]].pb({i, j});
    
    rep(i, 1, qc) rd(xa), rd(ya), rd(xb), rd(yb), rd(k), q[i] = {xa, ya, xb, yb, k, i};
    
    work(1, nn, 1, qc);
    
    rep(i, 1, qc) printf("%lld\n", alls[ans[i] - 1]);
}

例题8 动态查询子矩阵第k小（可离线）

题意

给你一个大小为 $n \times m$ 的矩阵 $a$，你要处理 $q$ 次操作，每次操作分两种：

  • 操作：给定 $x$、$y$、$v$，将 $a_{x,y}$ 的值更改为 $v$。
  • 询问：给定 $x_1$、$y_1$、$x_2$、$y_2$、$k$，问你以 $(x_1,y_1)$ 为左上角、以 $(x_2,y_2)$ 为右下角的子矩阵的第 $k$ 小的数是多少。

数据范围

  • $1 \leq n,m \leq 2 \times 10^3$
  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq a_i \leq 10^9$

题解

这题和例题4很像，改成二维和例题7是一样的方式，此处略。

时间复杂度：$O((n+q) \log^3 n)$

例题9 动态查询区间第k小（强制在线）

题意

同上，不过加了个强制在线的限制。

数据范围

同上。

题解

本题可用权值线段树套KD Tree解决。

例题10 动态查询树上第k小（可离线）

题意

给你一颗 $n$ 个节点的树，你要处理 $q$ 次操作，每次操作分两种：

  • 操作：给定 $x$、$v$，将 $x$ 点的权值更改为 $v$。
  • 询问：给你 $x$，问你 $x$ 及其子树内权值第 $k$ 小的节点的权值是多少。

数据范围

  • $1 \leq n \leq 2 \times 10^5$
  • $1 \leq q \leq 2 \times 10^5$
  • $0 \leq a_i \leq 10^9$

题解

根据给这个笔记写的经验，我们可以直接求出每个节点的欧拉序，然后把节点编号直接重新赋值为其欧拉序。

于是乎，对单点的权值修改就变成了序列单点修改，对子树的权值第 $k$ 小查询就变成了序列区间求第 $k$ 小。

于是就转化为了例题5。

时间复杂度：$O((n+q) \log^2 n)$

例题11 动态查询树上第k小（强制在线）

题意

同上，不过加了个强制在线的限制。

数据范围

同上。

题解

本题可用树状数组套主席树解决。

总结

题型1 普通整体二分

上面说的，其实都是整体二分优化线段树上二分过程的例题。

实际上，整体二分可以解决所有形如一下的问题：

给你一些信息，让你维护 $q$ 次询问。

但这 $q$ 次询问要满足一些要求，查询可以通过一次二分/线段树上二分来解决，但直接每次二分会TLE。

这种情况下，我们就可以把所有询问离线下来，然后定义如上的分治函数。

前面对边界的处理一样，然后先跑一遍调用二分 $\text{check}(\text{mid})$ 函数时做的修改操作。

然后，对所有 $[q_l,q_r]$ 内的询问，都跑一遍调用二分 $\text{check}(\text{mid})$ 函数时做的判断过程。

利用上面的结果，把这以内的所有询问分成两部分，一部分是答案在 $[l,\text{mid}]$ 内的询问，另一部分则是答案在 $[\text{mid}+1,r]$ 内的询问。

说完上面部分，你应该也想到了，其实整体二分是有模板的，所有题的代码都差不多，只不过要在那些差别部分多加思考。

题型2 带修整体二分

那如果说题目里存在修改操作呢？其实也一样，只不过加一个对修改的处理即可。

带修整体二分比普通整体二分肯定要复杂一些，我们要在这些复杂的地方多加思考才能搞定题目。