学习心得 - 算法 - 整体二分

ExFish · 2025-03-22 09:15:42 · 算法·理论

主体思想

把多个查询一起解决。

适合解决区间 kth 问题。

全局第 k 小

1. 可以直接排序。
2. 二分值域，维护 \leq mid 数个数
3. 把所有询问放在一起二分 （整体二分）。

执行

计算 solve(l,r)，询问中的答案都在 [l,r] 内。

猜测答案 mid=\frac{l+r}{2}。

在序列 l\leq a_i\le mid 检验答案，分为询问 k\le cnt 和 k>cnt 分治求解。

具体来说：

把输入序列 a 当做在 i 位置插入 v。

对于 v\le mid 修改对答案并没有太大影响，在树状数组之中单点加。

否则分治。

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+10;
int tr[N<<2],n,m,qc;
int lowbit(int x){
    return x&-x;
}
void update(int x,int v){
    for(;x<=qc;x+=lowbit(x))tr[x]+=v;
}
int query(int x){
    int su=0;
    for(;x>=1;x-=lowbit(x))su+=tr[x];
    return su;
}
struct qry{
    int op,x,y,k,i;
}q[N],ql[N],qr[N];
int ans[N];
void solve(int l,int r,int nl,int nr){
    if(nl>nr)return;
    if(l==r){
        for(int i=nl;i<=nr;i++)
            ans[q[i].i]=l;
        return;
    }
    int mid=(l+r)>>1,cur1=0,cur2=0;
    for(int i=nl;i<=nr;i++){
        if(q[i].op==1){ // Insert
            if(q[i].y<=mid)
                ql[++cur1]=q[i],
                update(q[i].x,q[i].k);
            else qr[++cur2]=q[i];
        }else{
            int res=query(q[i].y)-query(q[i].x-1);
            if(q[i].k<=res)
                ql[++cur1]=q[i];
            else
                qr[++cur2]=q[i],qr[cur2].k-=res;
        }
    }
    for(int i=nl;i<=nr;i++)if(q[i].op==1&&q[i].y<=mid)
        update(q[i].x,-q[i].k);
    for(int i=1;i<=cur1;i++)q[i+nl-1]=ql[i]; // Copy Left
    for(int i=1;i<=cur2;i++)q[i+nl-1+cur1]=qr[i]; // Copy Right
    // Solve
    solve(l,mid,nl,nl+cur1-1);
    solve(mid+1,r,nl+cur1,nr);
}
char op;
int a[N],x,y,k,qs;
bool isq[N];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        cin>>a[i],q[++qc]={1,i,a[i],1,0};
    for(int i=1;i<=m;i++){
        cin>>op>>x>>y;
        if(op=='Q'){
            cin>>k;
            q[++qc]={2,x,y,k,++qs};
            isq[i]=1;
        }else q[++qc]={1,x,a[x],-1,0},q[++qc]={1,x,a[x]=y,1,0};
    }
    solve(-1e9,1e9,1,qc);
    for(int i=1;i<=qs;i++)
        cout<<ans[i]<<"\n";
    return 0;
}