思想
对于某些难以直接求解的问题，二分答案显然是个不错的想法
但是对于某些多次询问的问题，二分答案的复杂度可以会达到(O(q*n*logn))
但是如果我们用某种玄学方法，把所有询问一起二分答案，复杂度就会玄学地降低
不过在整体二分的过程中，我们需要用到分治的思想，这也是为什么很多博客把(cdq)分治和整体二分放在一起
操作
一般来说，我们有函数(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
",ret[i]);
}
}
signed main()
{
red::main();
return 0;
}
复杂度
考虑对值域进行分治，那么复杂度显然是一个(logV)
注意到尽管每次我们对操作的分配并不均匀，但是由于每个深度的操作数之和都是(O(nlogn))，所以我们的复杂度是(O(nlognlogV))的
当然如果我们提前离散化的话，复杂度可以降低了(O(nlognlogn))但我懒没这么做
例题
本菜鸡目前见到的整体二分都不穿衣服，所以只能放一件稍微穿了点衣服的
有推荐题目欢迎留言