整体二分

《浅谈数据结构题的几个非经典解法》中的介绍：

所谓整体二分，需要数据结构题满足以下性质：

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

询问的答案有可二分性质显然是前提，我们发现，因为修改对判定标准的贡献相对独立，且贡献的值（如果有的话）与判定标准无关，所以如果我们已经计算过某一些修改对询问的贡献，那么这个贡献永远不会改变，我们没有必要当判定标准改变时再次计算这部分修改的贡献，只要记录下当前的总贡献，再进一步二分时，直接加上新的贡献即可

这样的话，我们发现，处理的复杂度可以不再与序列总长度直接相关了，而可能只与当前待处理序列的长度相关

---

举个栗子：POJ 2104 K-th Number 询问第$k$k小或第$k$k大

首先答案具有二分性。假设询问$(l,r,k)$(l,r,k)表示$[l,r]$[l,r]的第$k$k小数。二分答案，设答案区间为$[l,r]$[l,r]，$mid=(l+r)/2$mid=(l+r)/2，循环询问区间$[L,R]$[L,R]，若$val[x] \le mid，x \in [L,R]$val[x]≤mid，x∈[L,R]，则赋$cnt[x]=1$cnt[x]=1。统计询问区间内$sum=\sum _{i=L} ^{R} cnt[i]$sum=∑i=LR​cnt[i]，若$sum \lt k$sum<k，$l=mid+1$l=mid+1；否则$r = mid$r=mid。

对于单次询问的复杂度是$O(nlogn)$O(nlogn)，$m$m次询问总复杂度$O(mnlogn)$O(mnlogn)

整体二分

将所有的操作(修改、查询)一起二分。设当前的分治区间$solve (l, r, L, R)$solve(l,r,L,R)表示询问答案区间是$[l,r]$[l,r]，操作区间$[L,R]$[L,R]的数值在$[l,r]$[l,r]。

若$l=r$l=r，则将操作区间$[L,R]$[L,R]中的询问操作的答案标记为$l$l。

否则设$mid=(l+r)/2$mid=(l+r)/2。

如果当前是修改操作，若修改的权值$x \le mid$x≤mid，则把该修改操作放到左操作区间中，并实行修改；若$x \gt mid$x>mid，则把该修改操作放到右操作区间中。

如果是询问操作，若询问对应答案在$[l,mid]$[l,mid]，则把该询问操作放到左操作区间中；若询问对应答案在$[mid+1,r]$[mid+1,r]中，则把该询问操作放到右操作区间中，并加上左区间的贡献。

最后$solve (l, mid, L, MID)$solve(l,mid,L,MID)，$solve (mid + 1, r, MID+1,R)$solve(mid+1,r,MID+1,R)。其中$MID$MID为左右操作区间的分界线。

---

POJ 2104 K-th Number

#include<cstdio>
#include<iostream>
using namespace std;
inline int read() {
    int x = 0, f = 1; char c; c = getchar() ;
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar() ;
    return x * f ;
}
const int maxn = 1e5 + 10, INF = 0x3f3f3f3f ;
int n, m, cnt ;
int ans[maxn], sum[maxn] ;
struct query {
    int l, r, pos, val ;
    bool flag ;
    query () {}
    query (int a, int b, int c, int d, bool e) {l = a, r = b, pos = c, val = d, flag = e;}
}q[2 * maxn], q1[2 * maxn], q2[2 * maxn] ;
inline int lowbit (int x) {return x & (-x);}
inline void add (int pos, int val) {
    while (pos <= n) {
        sum[pos] += val ;
        pos += lowbit (pos) ;
    }
}
inline int cal (int pos) {
    int res = 0 ;
    while (pos) {
        res += sum[pos] ;
        pos -= lowbit (pos) ;
    }
    return res ;
}
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].flag) ans[q[i].pos] = l ;
        return ;
    }
    int m = (l + r) >> 1, cnt1 = 0, cnt2 = 0 ;
    for (int i = L; i <= R; i ++) {
        if (q[i].flag) {
            int val = cal (q[i].r) - cal (q[i].l - 1) ;
            if (val >= q[i].val) q1[++ cnt1] = q[i] ;
            else q[i].val -= val, q2[++ cnt2] = q[i] ;
        } else {
            if (q[i].val <= m) q1[++ cnt1] = q[i], add (q[i].pos, 1) ;
            else q2[++ cnt2] = q[i] ;
        }
    }
    for (int i = 1; i <= cnt1; i ++)
        if (!q1[i].flag) add (q1[i].pos, -1) ;
    for (int i = 1; i <= cnt1; i ++) q[L + i - 1] = q1[i] ;
    for (int i = 1; i <= cnt2; i ++) q[L + cnt1 + i - 1] = q2[i] ;
    solve (l, m, L, L + cnt1 - 1); solve (m + 1, r, L + cnt1, R) ;
}
int main() {
    n = read(); m = read() ;
    for (int i = 1; i <= n; i ++) {
        int x = read() ;
        q[++ cnt] = query (0, 0, i, x, 0) ;
    }
    for (int i = 1; i <= m; i ++) {
        int l = read(), r = read(), k = read() ;
        q[++ cnt] = query (l, r, i, k, 1) ;
    }
    solve (-INF, INF, 1, cnt) ;
    for (int i = 1; i <= m; i ++) printf("%d\n", ans[i]) ;
    return 0 ;
}

---

bzoj3110 Zjoi2013 K大数查询

题意：两种操作：在第$l$l个位置到第$r$r个位置，每个位置加入一个数$c$c；询问第$l$l个位置到第$r$r个位置第$k$k大的数。

题解：整体二分。求第$k$k大，把$c$c变为$n-c+1$n−c+1后求第$k$k小，最后输出$n-ans+1$n−ans+1即可。本题要求区间插入数，则在整体二分中若$c \le mid$c≤mid，则对$[q[i].l, q[i].r]+1$[q[i].l,q[i].r]+1。将区间第$k$k小中的树状数组改为线段树：支持区间加，区间求和即可。

#include <bits/stdc++.h>
#define lson l, m, rt * 2
#define rson m + 1, r, rt * 2 + 1
typedef long long ll ;
using namespace std;
inline ll read() {
    ll x = 0, f = 1; char c; c = getchar() ;
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar() ;
    return x * f ;
}
const int maxn = 5e4 + 10, INF = 0x3f3f3f3f ;
int n, m, qcnt ;
ll ans[maxn] ;
ll sum[maxn * 4], tag[maxn * 4] ;
struct query {
    int l, r, id ;
    ll val ;
    bool flag ;
}q[maxn], q1[maxn], q2[maxn] ;
void pushup (int rt) {
    sum[rt] = sum[rt * 2] + sum[rt * 2 + 1] ;
}
void pushdown (int rt, int l, int r) {
    if (tag[rt]) {
        tag[rt * 2] += tag[rt]; tag[rt * 2 + 1] += tag[rt] ;
        int m = (l + r) >> 1 ;
        sum[rt * 2] += tag[rt] * (m - l + 1) ;
        sum[rt * 2 + 1] += tag[rt] * (r - m) ;
        tag[rt] = 0 ;
    }
}
void update (int L, int R, ll val, int l, int r, int rt) {
    if (L <= l && R >= r) {
        sum[rt] += 1ll * (r - l + 1) * val ;
        tag[rt] += val ;
        return ;
    }
    pushdown (rt, l, r) ;
    int m = (l + r) >> 1 ;
    if (L <= m) update (L, R, val, lson) ;
    if (R > m) update (L, R, val, rson) ;
    pushup (rt) ;
}
ll query (int L, int R, int l, int r, int rt) {
    if (L <= l && R >= r) return sum[rt] ;
    pushdown (rt, l, r) ;
    int m = (l + r) >> 1; ll res = 0 ;
    if (L <= m) res += query (L, R, lson) ;
    if (R > m) res += query (L, R, rson) ;
    return res ;
}
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].flag) ans[q[i].id] = n - l + 1 ;
        return ;
    }
    int mid = (l + r) >> 1, cnt1 = 0, cnt2 = 0 ;
    for (int i = L; i <= R; i ++) {
        if (q[i].flag) {
            ll val = query (q[i].l, q[i].r, 1, n, 1) ;
            if (val >= q[i].val) q1[++ cnt1] = q[i] ;
            else q[i].val -= val, q2[++ cnt2] = q[i] ;
        } else {
            if (q[i].val <= mid) update (q[i].l, q[i].r, 1, 1, n, 1), q1[++ cnt1] = q[i] ;
            else q2[++ cnt2] = q[i] ;
        }
    }
    for (int i = 1; i <= cnt1; i ++)
        if (!q1[i].flag) update (q1[i].l, q1[i].r, -1, 1, n, 1) ;
    for (int i = 1; i <= cnt1; i ++) q[L + i - 1] = q1[i] ;
    for (int i = 1; i <= cnt2; i ++) q[L + cnt1 + i - 1] = q2[i] ;
    solve (l, mid, L, L + cnt1 - 1); solve (mid + 1, r, L + cnt1, R) ;
}
int main() {
    n = read(); m = read() ;
    for (int i = 1; i <= m; i ++) {
        int op = read(); ll x ;
        q[i].l = read(); q[i].r = read();
        x = read () ;
        if (op == 1) q[i].val = n - x + 1 ;
        else q[i].val = x ;
        if (op == 2) q[i].id = ++ qcnt ;
        else q[i].id = i ;
        q[i].flag = (op == 2) ;
    }
    solve (-n, n, 1, m) ;
    for (int i = 1; i <= qcnt; i ++) printf("%lld\n", ans[i]) ;
    return 0 ;
}