思想

对于某些难以直接求解的问题，二分答案显然是个不错的想法

但是对于某些多次询问的问题，二分答案的复杂度可以会达到\(O(q*n*logn)\)

但是如果我们用某种玄学方法，把所有询问一起二分答案，复杂度就会玄学地降低

不过在整体二分的过程中，我们需要用到分治的思想，这也是为什么很多博客把\(cdq\)分治和整体二分放在一起

操作

拿静态区间\(k\)小值来举个例子

一般来说，我们有函数\(solve(tl,tr,l,r)\)，表示值域在\([tl,tr]\)之间包含操作\([l,r]\)

我们先把所有操作和询问放在一起，构造函数\(solve(-inf,inf,1,n+m)\)表示在值域\([-inf,inf]\)之间，包含操作\([1,n+m]\)，操作包括插入数字和询问\(k\)大值

我们考虑在值域上二分答案，二分出一个\(mid=(tl+tr)>>1\)，然后我们把所有插入数字小于等于\(mid\)的操作先插入树状数组中，然后放入一个数组\(q1\)中，大于\(mid\)的操作直接放入数组\(q2\)中

再考虑\(check\)询问，查询树状数组内每个询问对应的\([l_i,r_i]\)，如果数字个数\(sum\)大于等于\(k_i\)，就将询问放入\(q1\)，否则将\(k_i\)减去\(sum\)再放入\(q2\)

然后我们将\(q1\)中的操作放回原数组中的前\(cnt1\)个位置，\(q2\)中的操作放入后面的位置

每次处理完之后向下分治的时候，分治为\(solve(tl,mid,l,l+cnt1-1)\)和\(solve(mid+1,tr,l+cnt1,r)\)

我们分治的边界是\(l>r\)表示当前值域内无操作，或者\(tl==tr\)表示求出了答案

配合代码食用就很好理解呢～

#include<bits/stdc++.h>
using namespace std;
namespace red{
#define lowbit(x) ((x)&(-x))
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=2e5+10,inf=1e9;
    int n,m,tot;
    struct point
    {
        int l,r,k,opt,id;
    }q[N<<1],q1[N<<1],q2[N<<1];
    int a[N],ret[N];
    int tr[N];
    inline void add(int x,int k)
    {
        for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=k;
    }
    inline int query(int y)
    {
        int ret=0;
        for(int i=y;i;i-=lowbit(i)) ret+=tr[i];
        return ret;
    }
    inline void solve(int tl,int tr,int l,int r)
    {
        if(l>r) return;//当前区间内无操作
        if(tl==tr)//求出了答案
        {
            for(int i=l;i<=r;++i)
                if(q[i].opt==2) ret[q[i].id]=tl;//统计答案
            return;
        }
        int mid=(tl+tr)>>1,cnt1=0,cnt2=0,tmp;
        for(int i=l;i<=r;++i)
        {
            if(q[i].opt==1)//插入
            {
                if(q[i].l<=mid) add(q[i].id,q[i].r),q1[++cnt1]=q[i];//小于mid插入树状数组
                else q2[++cnt2]=q[i];
            }
            else
            {
                tmp=query(q[i].r)-query(q[i].l-1);//查询当前树状数组内有多少数字
                if(q[i].k<=tmp) q1[++cnt1]=q[i];//大于等于k
                else q[i].k-=tmp,q2[++cnt2]=q[i];//小于k
            }
        }
        for(int i=1;i<=cnt1;++i)
            if(q1[i].opt==1) add(q1[i].id,-q1[i].r);//消除影响
        for(int i=1;i<=cnt1;++i) q[l+i-1]=q1[i];//放回原操作数组
        for(int i=1;i<=cnt2;++i) q[l+cnt1+i-1]=q2[i];
        solve(tl,mid,l,l+cnt1-1);//分治
        solve(mid+1,tr,l+cnt1,r);
    }
    inline void main()
    {
        n=read(),m=read();
        for(int i=1;i<=n;++i)
        {
            a[i]=read();
            q[++tot]=(point){a[i],1,0,1,i};//保证了插入数字在前面，不用分开处理了
        }
        for(int l,r,k,i=1;i<=m;++i)
        {
            l=read(),r=read(),k=read();
            q[++tot]=(point){l,r,k,2,i};
        }
        solve(-inf,inf,1,tot);
        for(int i=1;i<=m;++i) printf("%d\n",ret[i]);
    }
}
signed main()
{
    red::main();
    return 0;
}

复杂度

考虑对值域进行分治，那么复杂度显然是一个\(logV\)

注意到尽管每次我们对操作的分配并不均匀，但是由于每个深度的操作数之和都是\(O(nlogn)\)，所以我们的复杂度是\(O(nlognlogV)\)的

当然如果我们提前离散化的话，复杂度可以降低了\(O(nlognlogn)\)但我懒没这么做