1. 引言

首先标下文语读音：整（zhěng）体（tchǐ）二（èr）分（fēn）

具体解决哪类问题呢？

我们先来看道例题：

Kth number

题目链接：

HDU – 2665: 传送门=￣ω￣=

题意：

给出一个序列，有 M 个询问，每次询问区间 $[l,r]$中排名第 $k$（小）的值是多少。

数据在 $10^5$级别的范围内。数字大小。。。大概挺大的，不过 int 存的下。

有多组数据。

2. 整体二分

就这题来说，显然我们可以用线段树/主席树/分块… 做，但。。。。

我们就是不喜欢上面那些做法╭(╯^╰)╮

于是我们很自然地想到了离线，想到了二分，想到了枣树。

假如我们现在只有 1 个询问，那么很显然，我们可以对它进行二分答案！

比如对于数据：

10 1
1 4 2 3 5 6 7 8 9 0 
1 3 2 

即对于长度为 10 的序列：
$$1,4,2,3,5,6,7,8,9,0$$

我们询问区间 $[1,3]$内排名为 $2$的数字是多少。

显然答案为 $2$，即序列第 $3$个数字。

如果要用二分答案，首先我们需要：

离线 QvQ！

我们先把一开始的输入序列转为一堆的插入操作！

我们可以用一个二元组 $(x,y)$表示每个插入操作，$x$表示插入的位置，$y$表示插入的值

比如对于这个数据的话，我们可以用这些插入操作表示这个序列：

$(1,1)$
$(2,4)$
$(3,2)$
$(4,3)$
$(5,5)$
$(6,6)$
$(7,7)$
$(8,8)$
$(9,9)$
$(10,0)$

为什么我们要这样离线呢？

回想一下二分答案的过程：每次二分一个答案，然后在大概 $O(N)$的复杂度内判断答案所在区间是在 $[l,mid]$还是 $[mid+1,r]$中。就能以 $O(Nlog_2N)$的复杂度求解。

而这题的答案是询问的区间内排名为 $k$的值。

所以我们二分这个答案（别忘了我们目前还在假设只有一个修改）。

因为我们已经将数列离线成了一堆插入操作，所以对于我们当前二分出来的答案 $mid=\frac{L+R}{2}$（$[L,R]$为答案所在区间），我们可以把所有插入的值小于等于 $mid$的修改执行，然后用树状数组维护原数组的每个区间内插入了多少个数字。

为什么呢？

我们可以性感，呸，感性地想一想——比如我们要看 $mid$在区间 $[l,r]$内的排名，就可以去树状数组里查一下 $[l,r]$的区间和，求出来的数字 $tot$就是小于等于 $mid$的数字的个数。

然后比如我们是询问区间 $[l,r]$内排名第 $k$的数字，那么我们就判断：如果 $k<=tot$，就说明这个询问的答案是属于 $[L,mid]$的，否则说明它的答案属于 $[mid+1,R]$。

至此我们确定了答案属于的区间，我们可以继续向下二分答案了。

这时候记得清空树状数组。。。

就拿上面那个数据举例：

第 1 步

答案下界：$0$
答案上界：$9$
$mid=4$

查询：$[1,3]$内排名第 $2$的数字

插入的值 $\leq mid$的操作：

$(1,1)$
$(2,4)$
$(3,2)$
$(4,3)$
$(10,0)$

应用这些操作，树状数组维护的数组长这样：
$1,1,1,1,0,0,0,0,0,1$

（即在 $1,2,3,4,10$处分别有 $1$个数字比 $mid$小（或等于））

对于询问 $[1,3]$内排名第 $2$的数字，我们到树状数组中查询 $[1,3]$的区间和，发现是 $3$。

因为 $3\geq 2$，所以询问的答案属于区间 $[0,mid]$即 $[0,4]$。

第 2 步

答案下界：$0$
答案上界：$4$
$mid=2$

查询：$[1,3]$内排名第 $2$的数字

插入的值 $\leq mid$的操作：

$(1,1)$
$(3,2)$

应用这些操作，树状数组维护的数组长这样：
$1,0,1,0,0,0,0,0,0,0$

（即在 $1,3$处分别有 $1$个数字比 $mid$小（或等于））

对于询问 $[1,3]$内排名第 $2$的数字，我们到树状数组中查询 $[1,3]$的区间和，发现是 $2$。

因为 $2\geq 2$，所以询问的答案属于区间 $[0,mid]$即 $[0,2]$。

第 3 步

答案下界：$0$
答案上界：$2$
$mid=1$

查询：$[1,3]$内排名第 $2$的数字

插入的值 $\leq mid$的操作：

$(1,1)$

应用这些操作，树状数组维护的数组长这样：
$1,0,0,0,0,0,0,0,0,0$

（即在 $1$处有 $1$个数字比 $mid$小（或等于））

对于询问 $[1,3]$内排名第 $2$的数字，我们到树状数组中查询 $[1,3]$的区间和，发现是 $1$。

因为 $1 < 2$，所以询问的答案属于区间 $[mid+1,2]$即 $[2,2]$。

至此，我们得到了答案 2！

这就是二分答案的全过程，写了这么多 QvQ

“可是你丫不是来讲整体二分的吗？”

好吧好吧我错惹 QvQ

基于上面那个想法，如果我们对于每个询问都二分答案，显然是可行的。

。。。

可是你丫会超时啊！

这样的复杂度我们算算。

$M$个询问，序列长度为 $N$，答案上下界差值为 $D$，那么。。。

• 单个询问复杂度：$O(Nlog_2Dlog_2N)$
• $M$个询问复杂度：$O(MNlog_2Dlog_2N)$

这是稳妥妥の爆炸啊！

QvQ 因此我们就要用上整体二分了啊！

整体二分就是二分的一种优化

我是这么理解的。

一般我们优化一种算法，就是看它重复计算了哪些部分，也就是进行了哪些无意义的计算。

比如上面那组数据，我们稍作修改：

10 10
1 4 2 3 5 6 7 8 9 0 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 
1 3 2 

你可能会说：MMP 你傻啊，这么多相同询问你不晓得输出同一个答案啊。

确实，计算姬真的不知道=。=

我们经过仔细观察发现：

我们主要的复杂度耗费在了对每个询问都执行了相同答案区间的二分过程。

比如答案区间 $[0,9]$我们毫无意义地对 $10$个询问都执行了一遍二分过程。

但其实我们只要执行一次二分过程，就能计算出所有询问的答案所属区间！

但其实我们只要执行一次二分过程，就能计算出所有询问的答案所属区间！

但其实我们只要执行一次二分过程，就能计算出所有询问的答案所属区间！

重要的事情说三遍！

所以其实我们只要把二分算法稍加改进即可。

我们只要先把这些询问按输入顺序排成一排（乖乖站好♂）

然后一开始像二分答案一样，二分，然后树状数组维护。

这时候，我们开始对询问分类！

分为两类：

1. 答案属于区间 $[L,mid]$的
2. 答案属于区间 $[mid+1,R]$的

怎么分类呢？

，，，

很显然啊，就像对于只有一个询问一样，查询区间和 $tot$，判断 $tot$与 $k$的关系即可。

这样能把所有询问分成两类。

再分别按询问顺序排成两个序列，然后分别二分答案。

第一个序列的答案属于区间 $[L,mid]$
第二个序列的答案属于区间 $[mid+1,R]$

依次类推，直到某个序列对应的答案区间变为了 $[L,R],L=R$

那么这个序列内所有答案都为 $L$。

等于是把整个询问序列整体划分，整体二分答案

很明显，这样做这题复杂度是 $O(Nlog_2Dlog_2N)$，和之前单个询问的复杂度相同！

没错就是这样。

因此代码长这样（仔细看哦，还是很有帮助的）：

#include <bits/stdc++.h>
#define NS (100005)
#define MS (100005)
#define lowbit(a) (a&-a)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int l,r,k,id,type;}Q[NS+MS],Q1[NS+MS],Q2[NS+MS];
//询问/修改的结构体，Q1 为第一个分类（小于等于二分出来的答案的），Q2 为第二个分类
int T,n,m,ans[MS],t[NS];//依次是数据组数，n，m，答案数组，树状数组
void add(int pos,int d){for(;pos<=n;pos+=lowbit(pos))t[pos]+=d;}//树状数组增减 pos 位置的值
int get_sum(int pos)//获取前 pos 个位置的值的和
{
    int tmp=0;
    for(;pos;pos-=lowbit(pos))tmp+=t[pos];
    return tmp;
}
void binary(int QL,int QR,int l,int r)//整体二分
{
    if(QL>QR)return;
    if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type)ans[Q[i].id]=l;return;}//二分到了精确地答案
    int mid=(l+r)>>1,x1=0,x2=0;
    //mid 是二分出来的答案，x1 是统计第一个分类的询问/修改个数，x2 是统计第二个分类的个数
    for(int i=QL,tmp;i<=QR;i++)
        if(Q[i].type)//如果是询问
        {
            tmp=get_sum(Q[i].r)-get_sum(Q[i].l-1);//看它对应的区间内小于等于 mid 的值有多少个
            if(Q[i].k<=tmp)Q1[++x1]=Q[i];//该询问答案是小于等于 mid 的，分到第一类
            else Q2[++x2]=Q[i],Q2[x2].k-=tmp;//分到第二类，记得询问的 k 要改变，类似于主席树
        }
        else if(Q[i].k<=mid)add(Q[i].id,1),Q1[++x1]=Q[i];//发现是小于等于 mid 的修改
        else Q2[++x2]=Q[i];//大于 mid 的修改
    for(int i=1;i<=x1;i++)if(!Q1[i].type)add(Q1[i].id,-1);//清空刚刚的修改免得影响后面的在整体二分
    for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);//继续二分
}
int main()
{
    IN(T);
    while(T--)
    {
        IN(n),IN(m),memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++)IN(Q[i].k),Q[i].id=i,Q[i].type=0;//将序列转化为修改操作
        for(int i=1+n;i<=m+n;i++)
            IN(Q[i].l),IN(Q[i].r),IN(Q[i].k),Q[i].id=i-n,Q[i].type=1;//询问操作输入
        binary(1,m+n,INT_MIN,INT_MAX);//求答
        for(int i=1;i<=m;i++)printf("%d\n",ans[i]);//输出答案
    }
    return 0;
}

3. 例题

1. Dynamic Rankings

题解：传送门=￣ω￣=

此题把上面那个静态区间第 $k$小问题稍作修改即可。把每个修改操作变为一个删除操作和一个添加操作。

代码：

#include <bits/stdc++.h>
#define NS (50005)
#define MS (10005)
#define lowbit(a) (a&-a)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{int l,r,k,id,type;}Q[NS+(MS<<1)],Q1[NS+(MS<<1)],Q2[NS+(MS<<1)];
int T,n,m,cnt,data[NS],qcnt,ans[MS],t[NS];
char opt[5];
void add(int pos,int d){for(;pos<=n;pos+=lowbit(pos))t[pos]+=d;}
int sum(int pos){int tmp=0;for(;pos;pos-=lowbit(pos))tmp+=t[pos];return tmp;}
void binary(int QL,int QR,int l,int r)
{
    if(QL>QR)return;
    if(l==r){for(int i=QL;i<=QR;i++)if(Q[i].type==2)ans[Q[i].id]=l;return;}
    int mid=(l+r)>>1,x1=0,x2=0;
    for(int i=QL,tmp;i<=QR;i++)
        if(!Q[i].type)
        {
            if(Q[i].k<=mid)add(Q[i].id,1),Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i];
        }
        else if(Q[i].type==1)
        {
            if(Q[i].k<=mid)add(Q[i].id,-1),Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i];
        }
        else
        {
            tmp=sum(Q[i].r)-sum(Q[i].l-1);
            if(Q[i].k<=tmp)Q1[++x1]=Q[i];
            else Q2[++x2]=Q[i],Q2[x2].k-=tmp;
        }
    for(int i=1;i<=x1;i++)
        if(!Q1[i].type)add(Q1[i].id,-1);
        else if(Q1[i].type==1)add(Q1[i].id,1);
    for(int i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(int i=1;i<=x2;i++)Q[QL+x1+i-1]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
    IN(T);
    while(T--)
    {
        IN(n),IN(m),memset(t,0,sizeof(t)),cnt=qcnt=0;
        for(int i=1;i<=n;i++)IN(data[i]),Q[++cnt]=(query){0,0,data[i],i,0};
        for(int i=1,a,b,c;i<=m;i++)
            if(scanf("%s",opt),IN(a),IN(b),opt[0]=='C')
                Q[++cnt]=(query){0,0,data[a],a,1},Q[++cnt]=(query){0,0,b,a,0},data[a]=b;
            else IN(c),Q[++cnt]=(query){a,b,c,++qcnt,2};
        binary(1,cnt,INT_MIN,INT_MAX);
        for(int i=1;i<=qcnt;i++)printf("%d\n",ans[i]);
    }
    return 0;
}

2. [Poi2011]Meteors

题解：传送门=￣ω￣=

。。。具体看上面的题解传送门里讲的。

代码：

#include <bits/stdc++.h>
#define NS (300005)
#define lowbit(a) (a&-a)
using namespace std;
typedef long long LL;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
struct query{LL id,w;}Q[NS],Q1[NS],Q2[NS];
LL n,m,k,cl[NS],cr[NS],cnum[NS],ans[NS],t[NS];
vector<LL> g[NS];
void update(LL a,LL d){while(a<=m)t[a]+=d,a+=lowbit(a);}
LL query(LL a){LL tot=0;while(a)tot+=t[a],a-=lowbit(a);return tot;}
void add(LL l,LL r,LL d)
{
    if(l<=r)update(l,d),update(r+1,-d);
    else update(l,d),update(1,d),update(r+1,-d);
}
void binary(LL QL,LL QR,LL l,LL r)
{
    if(QL>QR)return;
    if(l==r){for(LL i=QL;i<=QR;i++)ans[Q[i].id]=l;return;}
    LL mid=(l+r)>>1,x1=0,x2=0;
    for(LL i=l;i<=mid;i++)add(cl[i],cr[i],cnum[i]);
    for(LL i=QL,tot;i<=QR;i++)
    {
        tot=0;
        for(LL j=0;j<g[Q[i].id].size();j++)
            if(tot+=query(g[Q[i].id][j]),tot>=Q[i].w)break;
        if(tot>=Q[i].w)Q1[++x1]=Q[i];
        else Q2[++x2]=Q[i],Q2[x2].w-=tot;
    }
    for(LL i=l;i<=mid;i++)add(cl[i],cr[i],-cnum[i]);
    for(LL i=1;i<=x1;i++)Q[QL+i-1]=Q1[i];
    for(LL i=1;i<=x2;i++)Q[QL+x1-1+i]=Q2[i];
    binary(QL,QL+x1-1,l,mid),binary(QL+x1,QR,mid+1,r);
}
int main()
{
    IN(n),IN(m);
    for(LL i=1,j;i<=m;i++)IN(j),g[j].push_back(i);
    for(LL i=1;i<=n;i++)IN(Q[i].w),Q[i].id=i;
    IN(k);
    for(LL i=1;i<=k;i++)IN(cl[i]),IN(cr[i]),IN(cnum[i]);
    k++,cl[k]=1,cr[k]=m,cnum[k]=1e9;
    binary(1,n,1,k);
    for(LL i=1;i<=n;i++)
        if(ans[i]<k)printf("%lld\n",ans[i]);
        else puts("NIE");
    return 0;
}