0.引述
来看这样一道题：
多次询问，查询静态区间k小，可离线。
相信很多人都想到了主席树，但我们发现题中可以离线，所以我们有了一种常数小，debug方便，码量小的方法:
。
1.引述
整体二分，是指将询问，修改等操作一起二分，基于值域。
传入的时候传四个参数：l,r,L,R。
表示值域在l到r内，操作在L到R内的操作答案。
处理的时候把操作分治，分到左右区间里。
同时，要使用树状数组，对左区间操作。
往下分治时，记住要撤销上次操作的影响，即清空树状数组。
整体二分还是很套路的，唯一不同的是树状数组中维护的内容。
inline 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(q[i].op==2) ans[q[i].id]=l;
//当区间缩小为1时，表示[L,R]内的查询答案都是当前的数，直接赋值就好
return;
}
int mid=(l+r)>>1,cnt1=0,cnt2=0;
for(int i=L;i<=R;i++)
{
if(q[i].op==1)
{
//修改操作，若当前的数小于左边界的最大值，则统计左区间个数时可以算上
if(q[i].l<=mid) q1[++cnt1]=q[i],add(q[i].id,q[i].r);
else q2[++cnt2]=q[i];
}
else
{
//查询操作，如果查询的k大于左区间的个数，就分到右边
int tmp=ask(q[i].r)-ask(q[i].l-1);//左区间个数
if(q[i].k<=tmp) q1[++cnt1]=q[i];
else q[i].k-=tmp,q2[++cnt2]=q[i];
}
}
for(int i=1;i<=cnt1;i++) if(q1[i].op==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(l,mid,L,L+cnt1-1);
solve(mid+1,r,L+cnt1,R);
}
2.例题
重要的还是例题~~。
模板题，树状数组为值域树状数组，查询可以直接仿照主席树的做法。
#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=2e5+9,INF=0x3f3f3f3f;
#define lowbit(x) (x&-x)
struct Query
{
int l,r,k,id,op;
} q[N*3],q1[N*3],q2[N*3];
int n,m,a[N],cnt,cntq,ans[N],tr[N];
char op[2];
inline void add(int x,int c){while(x<=n){tr[x]+=c,x+=lowbit(x);}}
inline int ask(int x){int res=0;while(x){res+=tr[x],x-=lowbit(x);}return res;}
inline 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(q[i].op==2) ans[q[i].id]=l;
//当区间缩小为1时，表示[L,R]内的查询答案都是当前的数，直接赋值就好
return;
}
int mid=(l+r)>>1,cnt1=0,cnt2=0;
for(int i=L;i<=R;i++)
{
if(q[i].op==1)
{
//修改操作，若当前的数小于左边界的最大值，则统计左区间个数时可以算上
if(q[i].l<=mid) q1[++cnt1]=q[i],add(q[i].id,q[i].r);
else q2[++cnt2]=q[i];
}
else
{
//查询操作，如果查询的k大于左区间的个数，就分到右边
int tmp=ask(q[i].r)-ask(q[i].l-1);//左区间个数
if(q[i].k<=tmp) q1[++cnt1]=q[i];
else q[i].k-=tmp,q2[++cnt2]=q[i];
}
}
for(int i=1;i<=cnt1;i++) if(q1[i].op==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(l,mid,L,L+cnt1-1);
solve(mid+1,r,L+cnt1,R);
}
int main()
{
scanf("%d%d",&n,&m);//初始序列视为修改
for(int i=1;i<=n;i++) scanf("%d",&a[i]),q[++cnt]=(Query){a[i],1,0,i,1};
for(int i=1;i<=m;i++)
{
int l,r,k;
scanf("%s",op);
scanf("%d%d",&l,&r);
if(op[0]=='Q')
scanf("%d",&k),q[++cnt]=(Query){l,r,k,++cntq,2};
else q[++cnt]=(Query){a[l],-1,0,l,1},q[++cnt]=(Query){r,1,0,l,1},a[l]=r;
}
solve(-INF,INF,1,cnt);
for(int i=1;i<=cntq;i++) printf("%d\n",ans[i]);
return 0;
}
这题就比较经典了。
操作为区间加，单点查到达某个值的时间。
这时候我们就要把区间加和单点查进行整体二分。
开始时，先把[l,mid]的区间加进行实现。
在查询时，如果当前国家的封地能量总合已经大于期望，那么证明达到满足它的期望的时间一定在[l,mid]的区间加内。
反正，则在右区间。
记得要保存每个国家的封地有哪些，可以用vector或者邻接表。
还注意破环成链，查询时记住把v和v+i的答案都算上。
记得撤销操作。
Warning：邻接表的表头要和查询打包到一个结构体里，否则在操作下放的时候无法把表头h传递下去，即q[i]=q1[...]时要传递表头。
代码我就放在这里🌶：