整体二分

主要思想：把多个询问一起解决（一次二分同时处理多个询问，确实顾名思义）

记 \([l,r]\) 为答案的值域，\([L,R]\) 为答案的定义域，\(mid=(l+r)/2\)。（也就是说求答案时仅考虑下标在 \([L,R]\) 内的操作和询问，这其中询问 的答案在 \([l,r]\) 内）

• 我们首先把所有操作 按时间顺序 存入数组中，然后开始分治。
• 在每一层分治中，利用数据结构（常见的是树状数组）统计 当前查询（即 \([L..R]\) 内的所有查询）的答案 和 \(mid\) 之间的关系。
• 我们已经通过这个数据结构知道了 当前所有 \([L..R]\) 内的查询 的答案 与 \(mid\) 之间的大小关系，然后我们根据 \([L..R]\) 内查询 的答案小于等于 \(mid\) 和大于 \(mid\) 两种关系，把查询分成 \(q1\) 和 \(q2\) 两份，并分别递归处理。（这样保证了问题量确实在缩小）
• 当 \(l=r\) 时，找到答案，记录答案并返回即可。

需要注意的是，在整体二分过程中，若当前处理的答案值域为 \([l,r]\)，则此时最终答案范围不在 \([l,r]\) 的询问会在其他时候处理

时间复杂度：

首先若不考虑有若干个询问，则分治复杂度只与答案值域 或 答案可能的取值集合大小 \(V\) 有关，最多递归 \(\log V\) 层；每层一共处理 \(m\) 个询问，故复杂度 \(\mathcal O(n\log V)\).

若内部用了额外复杂度 \(\mathcal O(m)\) 的数据结构，则总复杂度 \(\mathcal O(nm\log V)\).

适用范围：

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

多次询问区间第 k 小

把 \(a\) 数组排序得到 \(b\) 数组，同时记录 \(b\) 在 \(a\) 中的原编号

这样 \(V\) 缩小到了 \(n\) 级别，\(l,r,mid\) 变成了代表 \(b_l,b_r,b_{mid}\)

如何判定 \([L..R]\) 的询问的答案 与 答案 \(b_{mid}\) 的大小关系？

把 \(b_l..b_{mid}\) 按下标加入到树状数组中，对于询问 \([l_i,r_i,k_i]\)，树状数组可以回答下标 \([l_i..r_i]\) 中有多少 小于等于 \(b_{mid}\) 的数，这样就解决了问题

静态区间第 k 小的代码解释

王队的代码：

#include<bits/stdc++.h>

using namespace std;

inline int read(){
    int x=0; char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) x=x*10+c-'0',c=getchar();
    return x;
}

const int N=5e5+5;
int n,m,a[N];
struct Ques{int l,r,k,id;};
int tr[N],ans[N];
void add(int x,int v){
    for(;x<=n;x+=x&-x) tr[x]+=v;
}
int qry(int x){
    int res=0;
    for(;x;x-=x&-x) res+=tr[x];
    return res;
}

Ques lq[N*2],tql[N*2],tqr[N*2];
void dac(int ql,int qr,int l,int r){
    if(ql>qr) return ;
    if(l==r){
        for(int i=ql;i<=qr;++i){
            Ques q=lq[i];
            ans[q.id]=l;
        }
        return ;
    }
    int cl=0,cr=0;
    int mid=(l+r)>>1;
    for(int i=ql;i<=qr;++i){
        Ques q=lq[i];
        if(!q.id){
            if(q.k<=mid) add(q.l,1),tql[++cl]=q;
            else tqr[++cr]=q;
        }else{
            int num=qry(q.r)-qry(q.l-1);
            if(q.k<=num) tql[++cl]=q;
            else q.k-=num,tqr[++cr]=q;
        }
    }
    for(int i=ql;i<=qr;++i){
        Ques q=lq[i];
        if(!q.id){
            if(q.k<=mid) add(q.l,-1);
        }else break;
    }
    for(int i=1;i<=cl;++i) lq[ql+i-1]=tql[i];
    for(int i=1;i<=cr;++i) lq[ql+cl+i-1]=tqr[i];
    dac(ql,ql+cl-1,l,mid),dac(ql+cl,qr,mid+1,r);
}

int main(){
    n=read(),m=read();
    for(int i=1;i<=n;++i) lq[i]={i,i,read(),0};
    for(int i=1;i<=m;++i){
        int l=read(),r=read(),k=read();
        lq[i+n]={l,r,k,i};
    }
    dac(1,n+m,1,n);
    for(int i=1;i<=m;++i) printf("%d\n",ans[i]);
    return 0;
}

解释：

把读入 \(a_i\) 当作在时间 \(i\) 进行插入操作，则一共 \(n+m\) 个操作和询问，对他们整体二分

则 \([L..R]\) 表示处理时间 \([L..R]\) 的操作和询问，由于题目保证 \(1\le a_i\le n\)，故 \([l..r]\) 直接表示的是答案区间

对于插入操作，我们只处理 插入值 \(\le k\) 的操作（加到树状数组上），同时按插入值把插入操作分类

对于询问，同样的分类

为什么在还原树状数组时可以 else break 呢？因为操作从始至终都在询问之前

带修

把修改看成删除（树状数组上该位置 \(-1\)）再插入（\(+1\)）

对于答案 \(mid\)：

• 修改：分类；若修改值 \(\le mid\)，在树状数组上同步修改
• 询问：查出 \([l..r]\) 内 \(\le mid\) 的数量，类似的分类

一个 idea

每次二分，calc(x) 的时候 \(x\) 的变化量每次减半，若每次重新 calc 一遍就太浪费了

我们按变化量一个一个的看他对 calc 值的改变

变化量加起来是 \(\mathcal O(V)\) 的