1. 题目

• BZOJ – 1901（要权限号）：传送门=￣ω￣=
• LUOGU – 2617：传送门=￣ω￣=
• ZOJ – 2112（数据范围扩大&多组数据）：传送门=￣ω￣=

2. 题解

以前写过一个树套树的题解 QvQ：传送门=￣ω￣=

这次用整体二分做，快得飞起啊 23333～

有先决科技点：整体二分解决静态区间 kth 问题：传送门=￣ω￣=

看懂上面的那个问题了的话这个问题就很好办了。

把每个修改操作拆成一个删除操作和一个添加操作即可，别的和上面那个问题一模一样。

代码：

#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;
}