[OI] 整体二分

整体二分可以理解成普通二分改版，其实并没有改多少，并且一般对 check() 函数的复杂度要求更宽松

先来看一道经典题目：求区间排名

给一个数列，若干组询问 \((l,r,k)\)，求 \([l,r]\) 内第 \(k\) 大，询问次数较大

注意到询问次数较大，因此需要整体二分来解决

首先考虑普通二分，很容易想到一个比较暴力的想法：对值域二分，每次暴力遍历一遍 \([l,r]\)，把大于 \(mid\) 的都挑出来，假如个数比 \(k\) 多则二分左区间，否则二分右区间

这是一种比较无脑的 \(n\log n\) 二分方法，现在我们来尝试把它改造成整体二分：

首先定义一个求解范围 \([L,R]\)，表示我们现在正在求解编号 \([L,R]\) 范围内的询问，初始的时候令这个范围为 \([1,q]\)

然后，我们进行正常二分，此时应该枚举 \(mid=\frac{n}{2}\)

还是按照上面的办法，暴力遍历一遍 \([l,r]\)，把大于 \(mid\) 的都挑出来

然后我们可以确定出每一个询问区间里大于 \(mid\) 的数有多少个，对于此题来说，只需要求一遍前缀和即可进行维护

此时会发现询问分为了两类：一类是区间内大于 \(mid\) 的数比询问的 \(k\) 更多，另一类反之

因此我们可以直接给询问重新排序，将它们分成两拨，一类都在左边，一类都在右边

容易发现，左边的询问只需要二分 \([l,mid]\) 即可，而右边的询问仅需要二分 \([mid+1,r]\) 即可，这样便可以缩减复杂度

void check(int l,int r,int L,int R){
    //[l,r] 为值域区间, [L,R] 为询问区间
    if(l==r){
        //二分结束，统计答案
        for(int i=L;i<=R;++i){
            ans[q[i].id]=l;
        }
        return;
    }
    int mid=(l+r)/2;
    for(int i=1;i<=n;++i){
        sum[i]=sum[i-1]+(a[i]<=mid);
    }
    int cnt1=0,cnt2=0;
    //lst1,lst2 分别统计两类询问的编号，cnt1/2 是给这两个数组计数用的
    //注意这两个 cnt1/2 一定要开成局部变量！！！否则会因为递归修改了值导致直接炸掉
    for(int i=1;i<=Q;++i){
        int res=sum[q[i].r]-sum[q[i].l-1];
        if(res<=q[i].k){
            lst1[++cnt1]=i;
        }
        else{
            lst2[++cnt2]=i;
        }
    }
    //按顺序合并询问
    int now=L-1;
    for(int i=1;i<=cnt1;++i){
        id[++now]=lst1[i];
    }
    for(int i=1;i<=cnt2;++i){
        id[++now]=lst2[i];
    }
    //继续二分
    check(l,mid,L,L+cnt1-1);
    check(mid+1,r,L+cnt1,R);
}

相似的问题可以去看 P1527，是一道二维的区间排名问题，因此处理的时候不能再只使用前缀和了

以及 P3527，这是一道一维的带修问题，不过它求的不是排名，所以也异曲同工了

一维带修排名问题也可以整体二分，详见 P3332