整体二分是将所有操作离线下来，对多组询问同时进行二分。
将所有操作按照时间顺序存入数组，设[st,ed]为答案的定义域，即询问的区间，[l,r]为答案的值域。
二分答案的值域，对于每个询问去比较和mid的关系，据此判断是递归进入值域[l,mid]还是值域[mid+1,r]，当l=r时找到答案。
设q1为需要进入[l,mid]的询问，q2为需要进入[mid+1,r]的操作，将[st,ed]分为两部分，左面为q1，右面为q2，之后递归[st,st+c1-1,l,mid]和[st+c1,ed,mid+1,r].
对于存在修改操作，可以按照时间顺序将修改和查询插入数组中，在分治时分别判断时修改操作还是查询操作即可，同时对于修改操作也要和mid比较并判断进入值域[l,mid]还是[mid+1,r]。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)if(q[i].type)ans[l]++;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].type){
int re=bit.ask(q[i].l,q[i].r);
if(re>=q[i].x)q1[++c1]=q[i];
else q[i].x-=re,q2[++c2]=q[i];
}
else{
if(q[i].id<=mid){
bit.add(q[i].l,1);
q1[++c1]=q[i];
}
else q2[++c2]=q[i];
}
}
for(int i=1;i<=c1;i++)if(q1[i].type==0)bit.add(q1[i].l,-1);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
若所有修改都在查询之前，那么可以不将修改操作插入数组，而是在分治扫描每个询问前后，分别对修改的操作进行处理。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
ans[l]+=ed-st+1;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=l;i<=mid;i++)bit.add(pos[i],1);
for(int i=st;i<=ed;i++){
int re=bit.ask(q[i].l,q[i].r);
if(re>=q[i].x)q1[++c1]=q[i];
else q[i].x-=re,q2[++c2]=q[i];
}
for(int i=l;i<=mid;i++)bit.add(pos[i],-1);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
查询矩阵第k小。对于每个询问和当前二分的mid，设子矩阵中<=mid的数由cnt个，若cnt>=k，则该询问的答案在[l,mid]之中，否则在[mid+1,r]之中。对于计算cnt，可以使用二维树状数组前缀和，由于在最初读入时是先修改操作后查询操作，所以直接按照这个顺序枚举操作也不会有错。
void solve(int st,int ed,int l,int r){
if(st>ed)return;/*已经没有操作*/
if(l==r){/*找到答案*/
for(int i=st;i<=ed;i++)ans[q[i].id]=l;/*对于操作的id=0*/
return;
}
int mid=l+r>>1/*二分值域*/,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].id){/*询问*/
int re=bit.ask(q[i].x,q[i].y,q[i].a,q[i].b);/*计算答案进行比较*/
if(q[i].k<=re)q1[++c1]=q[i];/*递归[l,mid]*/
else{
q[i].k-=re;/*更新第k小*/
q2[++c2]=q[i];/*递归[mid+1,r]*/
}
}
else{
if(q[i].k<=mid){/*修改*/
bit.add(q[i].x,q[i].y,1);
q1[++c1]=q[i];
}
else q2[++c2]=q[i];
}
}
for(int i=1;i<=c1;i++)if(q1[i].id==0)bit.add(q1[i].x,q1[i].y,-1);/*q1当中的一定都是修改过的，需要复原*/
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
询问静态区间第k小。注意树状数组中的下标是原数组的下标，这样才能够通过1的前缀和来统计个数。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)ans[q[i].id]=l;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].id){
int re=bit.ask(q[i].l,q[i].r);
if(q[i].k<=re)q1[++c1]=q[i];
else{
q[i].k-=re;
q2[++c2]=q[i];
}
}
else{
if(q[i].k<=mid){
bit.add(q[i].l,1);
q1[++c1]=q[i];
}
else q2[++c2]=q[i];
}
}
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
for(int i=st;i<=st+c1-1;i++)if(q[i].id==0)bit.add(q[i].l,-1);
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
动态区间第k小，修改操作看作先删除再插入。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)ans[q[i].id]=l;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].id){
int re=bit.ask(q[i].l,q[i].r);
if(q[i].k<=re)q1[++c1]=q[i];
else q[i].k-=re,q2[++c2]=q[i];
}
else{
if(q[i].k<=mid)bit.add(q[i].l,q[i].r),q1[++c1]=q[i];
else q2[++c2]=q[i];
}
}
for(int i=1;i<=c1;i++)if(q1[i].id==0)bit.add(q1[i].l,-q1[i].r);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
维护n个可重集，由两种操作，在编号[l,r]的可重集内加入x，查询编号[l,r]的可重集中的第x大的数。维护一颗线段树，若该操作是修改操作且x>mid，则在[l,r]内区间加1，并准备递归进入值域[mid+1,r]，表示该区间内大于mid的数的个数。若该操作是查询操作，求出[l,r]内>mid的数的个数cnt，若cnt>=x，则说明答案应该在[mid+1,r]，否则答案在[l,mid]，并更行x的值，每次分治前线段树要清空，可以使用懒惰删除标记。
struct SegmentTree{
struct tree{
int l,r,sum,add;
bool del;
}t[N<<2];
#define lc (p<<1)
#define rc (p<<1|1)
#define l(p) (t[p].l)
#define r(p) (t[p].r)
#define s(p) (t[p].sum)
#define a(p) (t[p].add)
#define d(p) (t[p].del)
inline void pushup(int p){
s(p)=s(lc)+s(rc);
}
inline void pushdown(int p){
if(d(p)){
d(p)=a(lc)=a(rc)=s(lc)=s(rc)=0;
d(lc)=d(rc)=1;
}
if(a(p)){
s(lc)+=a(p)*(r(lc)-l(lc)+1);
s(rc)+=a(p)*(r(rc)-l(rc)+1);
a(lc)+=a(p);
a(rc)+=a(p);
a(p)=0;
}
}
inline void clear(){
d(1)=1;
a(1)=s(1)=0;
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(lc,l,mid);
build(rc,mid+1,r);
}
void modify(int p,int l,int r,int x){
if(l<=l(p)&&r(p)<=r){
a(p)+=x;
s(p)+=x*(r(p)-l(p)+1);
return;
}
pushdown(p);
int mid=l(p)+r(p)>>1;
if(l<=mid)modify(lc,l,r,x);
if(mid<r)modify(rc,l,r,x);
pushup(p);
}
int query(int p,int l,int r){
if(l<=l(p)&&r(p)<=r)return s(p);
pushdown(p);
int mid=l(p)+r(p)>>1,re=0;
if(l<=mid)re+=query(lc,l,r);
if(mid<r)re+=query(rc,l,r);
return re;
}
}seg;
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)ans[q[i].id]=l;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].id){
int re=seg.query(1,q[i].l,q[i].r);
if(re>=q[i].x)q2[++c2]=q[i];
else q[i].x-=re,q1[++c1]=q[i];
}
else{
if(q[i].x>mid)seg.modify(1,q[i].l,q[i].r,1),q2[++c2]=q[i];
else q1[++c1]=q[i];
}
}
seg.clear();
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
一个长m的环，其中有n个国家的基地，有k场流星雨会降落在[l,r]内切每个单位长度带来x的陨石，每个国家有希望收集的陨石数量，求每个国家最早在第几场流星雨后能够达成目标。断环成链，每个国家连边其基地对应的位置，二分第mid场流星雨，树状数组区间加是的1到mid场流星雨全部落下，之后单点查询判断对于枚举到的每个国家是否能够达成目标。注意，查询时要查pos和pos+m的答案，当然也可在连边是就直接连边i和i+m，主函数中二分流星雨区间是[1,k+1]，当ans=k+1时说明无法满足要求，链式前向星的表头要和询问放在一起，这样操作下传时才不会出错。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)ans[q[i].id]=l;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=l;i<=mid;i++)bit.add(a[i].l,a[i].r,a[i].x);
for(int i=st;i<=ed;i++){
int re=0;
for(int j=q[i].head;j&&re<=q[i].x;j=e[j].next){
int y=e[j].to;
re+=bit.query(y)+bit.query(y+m);
}
if(re>=q[i].x)q1[++c1]=q[i];
else q[i].x-=re,q2[++c2]=q[i];
}
for(int i=l;i<=mid;i++)bit.add(a[i].l,a[i].r,-a[i].x);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
笛卡尔坐标系有一水平的木板，x正半轴有一些子弹从左到右依次发射，每个木板被贯穿x次后破裂，求每个子弹可以击碎多少个木板。考虑对每个木板进行二分找到第x次击穿该木板的子弹的编号，对于每个子弹可以树状数组单点修改，每个模板区间查询，为了防止木板不会被击穿的情况发生，子弹应该多一个虚拟子弹。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
for(int i=st;i<=ed;i++)if(q[i].type)ans[l]++;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=st;i<=ed;i++){
if(q[i].type){
int re=bit.ask(q[i].l,q[i].r);
if(re>=q[i].x)q1[++c1]=q[i];
else q[i].x-=re,q2[++c2]=q[i];
}
else{
if(q[i].id<=mid){
bit.add(q[i].l,1);
q1[++c1]=q[i];
}
else q2[++c2]=q[i];
}
}
for(int i=1;i<=c1;i++)if(q1[i].type==0)bit.add(q1[i].l,-1);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}
也可以不将修改操作放到同一个数组里面。
void solve(int st,int ed,int l,int r){
if(st>ed)return;
if(l==r){
ans[l]+=ed-st+1;
return;
}
int mid=l+r>>1,c1=0,c2=0;
for(int i=l;i<=mid;i++)bit.add(pos[i],1);
for(int i=st;i<=ed;i++){
int re=bit.ask(q[i].l,q[i].r);
if(re>=q[i].x)q1[++c1]=q[i];
else q[i].x-=re,q2[++c2]=q[i];
}
for(int i=l;i<=mid;i++)bit.add(pos[i],-1);
for(int i=1;i<=c1;i++)q[st+i-1]=q1[i];
for(int i=1;i<=c2;i++)q[st+c1+i-1]=q2[i];
solve(st,st+c1-1,l,mid);
solve(st+c1,ed,mid+1,r);
}