这道题目是一道整体二分的好题
想必做这道题目的人都知道二分答案，而整体二分相当于一次性二分所有答案，很显然可以发现，对于这一道题目而言，时间复杂度是m log 1e9，是可以接受的
对于每一次修改，我们可以考虑：减去原来的值，加上修改成的值，包括读入原先序列ai也可以是如此。
还有一个要点是统计mb的排名。最暴力的方式是开一个计数表去一个个数过来，但是我们可以想一下，比如mb=50，前面有两个数，一个a1=4，一个a2=49，那么这两个数的值是有必要考虑的吗？显然没有必要，因为它们都比50小，因此我们可以把它们都当成两个值是1的标记，接下来统计排名只要计算前缀和就可以了。因此这道题目可以用树状数组或者线段树进行维护。
还有一个小要点，就是对于脏数据的处理。脏数据也就是会对计算结果产生影响的数据。对于本题而言，值大于等于mb的操作在[lb,mb)中是没有影响的，但是在[mb,ub)的操作中，值小于mb的操作会产生影响，但是显然如果减去一个k，那么就可以消除这个影响。
其实这个程序有很有趣的一点。这道题的原题是zoj2112，在大学OJ里面是有多组数据的。这个程序几乎可以不用初始化直接提交过去，原因就是每一组数据整体二分之后，所有参与的数组的值全部都空了。具体可以自己证明一下
代码如下：
```cpp
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
struct op
{
int type;
//type==0 Change i means position; j means ispositive; k means the number after change
//type==1 Query i means left; r means right; k means kth-number
int i,j,k;
int id;
};
int n,m,a[10050],ans[10050],f[50050];
vector <op> q;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int k)
{
while (x<=n)
{
f[x]+=k;
x+=lowbit(x);
}
}
int query(int k)
{
int ans=0;
while (k>0)
{
ans+=f[k];
k-=lowbit(k);
}
return ans;
}
void solve(int lb,int ub,vector <op> &q)
{
vector <op> Left;
vector <op> Right;
int mb=(lb+ub)>>1;
//cout << lb << " " << mb << " " << ub << endl;
if (ub-lb==1)
{
for (int i=0;i<q.size();i++)
{
if (q[i].type==1)
ans[q[i].id]=lb;
}
return;
}
else if (q.empty())
return;
for (int i=0;i<q.size();i++)
{
op tmp=q[i];
if (tmp.type==0)
{
if (tmp.k<mb)
{
add(tmp.i,tmp.j);//i:pos j:num
Left.push_back(tmp);
}
else
Right.push_back(tmp);
}
else
{
int kth=query(tmp.j)-query(tmp.i-1);
if (kth>=tmp.k)
Left.push_back(tmp);
else
{
tmp.k-=kth;
Right.push_back(tmp);
}
}
}
for (int x=0;x<Left.size();x++)
if(Left[x].type==0)
add(Left[x].i,-Left[x].j);
solve(lb,mb,Left);
solve(mb,ub,Right);
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
op tmp={0,i,1,a[i]};
q.push_back(tmp);
}
for (int x=0;x<m;x++)
{
char cmd;
int i;
scanf("%s%d",&cmd,&i);
if (cmd=='C')
{
int t;
scanf("%d",&t);
op tmp={0,i,-1,a[i],0};
q.push_back(tmp);
a[i]=t;
tmp={0,i,1,t,0};
q.push_back(tmp);
}
else
{
int j,k;
scanf("%d%d",&j,&k);
op tmp={1,i,j,k,x};
q.push_back(tmp);
}
}
for (int i=0;i<m;i++)
ans[i]=-1;
solve(0,1e9,q);
for (int i=0;i<m;i++)
if (ans[i]!=-1)
printf("%d\n",ans[i]);
return 0;
}
```
然而整体二分还是比树套树慢，但是整体二分的优势就是好写。~~特别对于我这种弱省蒟蒻而言。~~