整体二分

整体二分是针对check()函数复杂度过大，对每个询问单独二分答案会复杂度爆炸的问题而设计的算法。

由于二分时查询的mid是跳跃的，无序的，直接进行二分时每次check()都能跑满，复杂度非常的不正确。

首先引进一个非常有用的东西（大抵忘了名字）：

$$ f(x) = \begin{cases} 1 (x < k) \\ 0 (x \ge k) \end{cases} $$

这样我们就可以把计数问题转变为求和问题。

题目：区间查询第 $k$ 小值

给出 $q$ 组 $\{ l,r,k \}$，每次回答 $[l,r]$ 中第 $k$ 小值。

($n \le 2\times10^5,q \le 2\times 10^5,a_i \le V \le 10^9$)

如果每次二分答案mid，check()在$[l,r]$中有多少数小于mid，复杂度$O(n\log_2 V)$

总复杂度$O(q\cdot n\log_2 V)$

不满意。

正文

如果询问间完全独立，上述算法已经达到最优上限，考虑其他优化。

所以考虑一次check()的复杂度多处理一些询问。

比如我们对一堆询问同时二分一个mid，我们利用计数化求和的技巧，利用树状数组，可以同时算出在这个mid下check()每个询问是要返回true还是false。

我们发现此时算法的瓶颈在于树状数组的多次单点修改。

我们发现，随着递归的深入，我们每次树状数组实质要修改的点是不断减半的。

于是维护好必要修改的点，复杂度就非常正确了。

code

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int c[N];
#define lb (i&(-i))
int query(int x){int ret=0;for(int i=x;i;i-=lb)ret+=c[i];return ret;}
void modify(int x,int v){for(int i=x;i<N;i+=lb)c[i]+=v;}
int n,q;
int a[N],v[N],ans[N];
vector<int> pos[N];
struct nod{
    int l,r,k,id;
}Q[N];
queue<nod>q1,q2;

void solve(int l,int r,int ql,int qr){
    if(l==r){
        for(int i=ql;i<=qr;i++){
            ans[Q[i].id]=l;
        }
        return;
    }
    int mid = (l+r) >> 1;
    for(int i=l;i<=mid;i++){
        for(auto j:pos[i])modify(j,1);
    }
    // cout<<endl;

    for(int i=ql;i<=qr;i++){
        int t = query(Q[i].r)-query(Q[i].l-1);
        // cout<<l<<' '<<r<<' '<<t<<endl;
        if(query(Q[i].r)-query(Q[i].l-1) < Q[i].k){//这个mid下的不够k，l=mid+1
            Q[i].k-=t;
            q2.push(Q[i]);
        }else{
            q1.push(Q[i]);
        }
    }
    int p=ql;
    for(;q1.size();p++)Q[p]=q1.front(),q1.pop();
    int m=p-1;
    for(;q2.size();p++)Q[p]=q2.front(),q2.pop();

    for(int i=l;i<=mid;i++){
        for(auto j:pos[i])modify(j,-1);
    }
    solve(l,mid,ql,m),solve(mid+1,r,m+1,qr);
    return ;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i],v[i]=a[i];
    sort(v+1,v+1+n);
    int p=unique(v+1,v+1+n)-v-1;
    for(int i=1;i<=n;i++){
        a[i] = lower_bound(v+1,v+1+p,a[i])-v;
        pos[a[i]].push_back(i);
    }
    for(int i=1,l,r,k;i<=q;i++){
        cin>>l>>r>>k;
        Q[i]={l,r,k,i};
    }
    solve(1,p,1,n);
    for(int i=1;i<=n;i++){
        cout<<v[ans[i]]<<endl;
    }
    return 0;
}