学步园

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstdio>
#define N 2200001
using namespace std;
int n,m,tot,top,sz;
struct data{  
    int l,r,sum;  
}node[N];  
int v[N],hash[N];
int A[N],B[N],K[N],root[N],sum[N],L[30],R[30],num[N],a,b,cnt;
bool flag[N];
int lowbit(int x)
{return x&(-x);}
char s[3];
int find(int x)
{
    int l=1,r=tot,mid;
    while(l<=r)
    {
         int mid=(l+r)>>1;
         if(hash[mid]<x)l=mid+1;
         else r=mid-1;
        } 
    return l;
}
inline int read(){
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
void update(int pre,int &k,int l,int r,int v,int x){  
    k=++cnt;  
    node[k].sum=node[pre].sum+x;  
    if(l==r)return;  
    node[k].l=node[pre].l;node[k].r=node[pre].r;  
    int mid=(l+r)>>1;  
    if(v<=mid)update(node[pre].l,node[k].l,l,mid,v,x);  
    else update(node[pre].r,node[k].r,mid+1,r,v,x);  
}  
int query(int l,int r,int k){
     if(l==r)  return l;
     int i,suml=0,sumr=0;
     for(i=1;i<=a;i++)  suml+=node[node[L[i]].l].sum;
     for(i=1;i<=b;i++)  sumr+=node[node[R[i]].l].sum;
     int mid=(l+r)>>1;
     if(sumr-suml>=k) 
     {
         for(i=1;i<=a;i++)  L[i]=node[L[i]].l;
         for(i=1;i<=b;i++)  R[i]=node[R[i]].l;
         return query(l,mid,k);
     }
     else
     {
         for(i=1;i<=a;i++)  L[i]=node[L[i]].r;
         for(i=1;i<=b;i++)  R[i]=node[R[i]].r;
         return query(mid+1,r,k-(sumr-suml));
     }
}
int main(){
	n=read();m=read();
	for(int i=1;i<=n;i++){
		v[i]=read();
		num[++top]=v[i];
	}
	for(int i=1;i<=m;i++){
		scanf("%s",s);
		A[i]=read();B[i]=read();
		if(s[0]=='Q')K[i]=read(),flag[i]=1;
		else num[++top]=B[i];
	}
	sort(num+1,num+top+1);
	hash[++tot]=num[1];
	for(int i=1;i<=top;i++)
		if(num[i]!=num[i-1])
			hash[++tot]=num[i];
	for(int i=1;i<=n;i++){
		int t=find(v[i]);
		for(int j=i;j<=n;j+=lowbit(j))
			update(root[j],root[j],1,tot,t,1);
	}
	for(int i=1;i<=m;i++)
		if(flag[i]){
			a=0;b=0;A[i]--;
			for(int j=A[i];j>0;j-=lowbit(j))
				L[++a]=root[j];
			for(int j=B[i];j>0;j-=lowbit(j))
				R[++b]=root[j];
			printf("%d\n",hash[query(1,tot,K[i])]);
		}
		else{
			int t=find(v[A[i]]);
			for(int j=A[i];j<=n;j+=lowbit(j))
				update(root[j],root[j],1,tot,t,-1);
			v[A[i]]=B[i];
			t=find(B[i]);
			for(int j=A[i];j<=n;j+=lowbit(j))
				update(root[j],root[j],1,tot,t,1);
		}
		return 0;
}