整体二分

整体二分用来解决一种有多次操作可离线的问题，操作中的询问是可以通过二分答案解决

对操作和答案都进行分割，对答案二分出一个\(mid\)，满足和不满足\(mid\)这个答案的操作分别进行处理，两部分加入不同的答案区间

Dynamic Rankings：带修区间第\(k\)小

二分值域，权值树状数组维护

\(code:\)

void solve(int L,int R,int l,int r)
{
    if(L>R) return;
    if(l==r)
    {
        for(int i=L;i<=R;++i)
            if(p[i].l)
                ans[p[i].id]=l;
        return;
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0;
    for(int i=L;i<=R;++i)
    {
        if(p[i].l)
        {
            int v=query(p[i].r)-query(p[i].l-1);
            if(p[i].k<=v) q1[++cnt1]=p[i];
            else p[i].k-=v,q2[++cnt2]=p[i];
        }
        else
        {
            if(p[i].k<=mid) q1[++cnt1]=p[i],update(p[i].pos,p[i].id);
            else q2[++cnt2]=p[i];
        }
    }
    for(int i=1;i<=cnt1;++i) p[L+i-1]=q1[i];
    for(int i=1;i<=cnt2;++i) p[L+cnt1+i-1]=q2[i];
    for(int i=1;i<=cnt1;++i)
        if(q1[i].pos)
            update(q1[i].pos,-q1[i].id);
    solve(L,L+cnt1-1,l,mid),solve(L+cnt1,R,mid+1,r);
}

整体二分

原文：https://www.cnblogs.com/lhm-/p/12639438.html