https://www.luogu.org/problemnew/show/P2617
题意：给定长度为10万的数组，要求支持两种操作：
1.单点修改
2.查询区间第k小
思路：整体二分https://zhuanlan.zhihu.com/p/55322598

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define maxn (100000+100)
#define INF 0x3f3f3f3f

int a[maxn],n,m,cnt,qid,c[maxn],ans[maxn];
struct Query{
    int l,r,k,id,op;
}q[maxn*3],q1[maxn*3],q2[maxn*3];//注意这里开3倍，因为m次操作最差需要2*m，加上n。

int sum(int x)
{
    int ret=0;
    while(x)
    {
        ret+=c[x];
        x-=lowbit(x);
    }
    return ret;
}

void add(int x,int d)
{
    while(x<=n)//维护的是位置下标，故到n
    {
        c[x]+=d;
        x+=lowbit(x);
    }
}

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;
        return ; 
    }
    int mid=(l+r)>>1,cnt1=0,cnt2=0,x;
    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 {
            x=sum(q[i].r)-sum(q[i].l-1);
            if(q[i].k <= x) q1[++cnt1]=q[i];
            else q[i].k-=x,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+i+cnt1-1]=q2[i];
    solve(l,mid,L,L+cnt1-1);
    solve(mid+1,r,L+cnt1,R);
}

int main()
{
    //freopen("input.in","r",stdin);
    int x,y,z;
    char cmd[5];
    cin>>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++)
    {
        scanf("%s",cmd);
        if(cmd[0]=='Q')scanf("%d%d%d",&x,&y,&z),q[++cnt]=(Query){x,y,z,++qid,2};
        else scanf("%d%d",&x,&y),q[++cnt]=(Query){a[x],-1,0,x,1},q[++cnt]=(Query){a[x]=y,1,0,x,1};
    }
    solve(0,INF,1,cnt);
    for(int i=1;i<=qid;i++)printf("%d\n",ans[i]);
    return 0;
}