编译器能过luogu过不了。

#include <bits/stdc++.h>

using namespace std;

const int N=5e6+110;
int n,m;

struct IO{
    enum {B=1<<20};
    char b[B],*p=b,*e=b+B;

    IO(){r();}
    void r(){e=b+fread(b,1,B,stdin);p=b;}
    void r(int &x){
        int s=1;x=0;
        while(*p<48&&*p!='-')if(++p==e)r();
        if(*p=='-')s=-1,p=b;
        while(*p>=48&&*p<=57){
            x=x*10+(*p++&15);
            if(p==e)r();
        }
        x*=s;
    }
	void r(char &c){
		do{
			if(p==e)r();
			c=*p++;
		}while(c==' '||c=='\0'||c=='\n');
	}
}fio;

struct node{
	int l,r;
	int val,key;
	int sz;
}t[N];

int idx,root[N];
mt19937 rnd;

int newnode(int x){
	t[++idx].val=x;
	t[idx].key=rnd();
	t[idx].sz=1;
	return idx;
}
void push(int p){
	t[p].sz=t[t[p].l].sz+t[t[p].r].sz+1;
}

void split(int p,int x,int &A,int &B){
	if(!p){
		A=B=0;
		return ;
	}
	if(t[p].val<=x)A=p,split(t[p].r,x,t[p].r,B);
	else B=p,split(t[p].l,x,A,t[p].l);
	push(p);
}
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(t[x].key<t[y].key){
		t[x].r=merge(t[x].r,y);
		push(x);
		return x;
	}
	else{
		t[y].l=merge(x,t[y].l);
		push(y);
		return y;
	}
}

struct LineTree{
	int l,r;
}a[N]; 
int bas[N];

void add(int p,int x){
	int a,b,c;
	split(root[p],x,a,b);
	c=newnode(x);
	root[p]=merge(merge(a,c),b);
} 
void del(int p,int x){
	int a,b,c;
	split(root[p],x,a,b);
	split(a,x-1,a,c);
	c=merge(t[c].l,t[c].r);
	root[p]=merge(merge(a,c),b);
}
int kso(int p,int x){
	int a,b;
	split(root[p],x-1,a,b);
	int kk=t[a].sz+1;
	root[p]=merge(a,b);
	return kk; 
}

void buildtree(int p,int l,int r){
	a[p].l=l;
	a[p].r=r;
	for(int i=l;i<=r;i++){
		add(p,bas[i]);
	}
	if(l==r)return ;
	buildtree(p<<1,l,(l+r)>>1);
	buildtree(p<<1|1,((l+r)>>1)+1,r);
}
int kso_(int p,int l,int r,int x){
	if(a[p].l>=l&&a[p].r<=r){
		return kso(p,x)-1;
	}
	int kk=0;
	if((a[p].l+a[p].r)>>1>=l)kk+=kso_(p<<1,l,r,x);
	if(((a[p].l+a[p].r)>>1)+1<=r)kk+=kso_(p<<1|1,l,r,x);
	return kk;
}
int kth_(int l,int r,int x){
	int L=0,R=1e8;
	int ans=0;
	while(L<R){
		int mid=(L+R+1)>>1;
		if(kso_(1,l,r,mid)+1<=x){
			L=mid;
		}
		else R=mid-1;
	}
	return L;
}
void add_(int p,int l,int x){
	del(p,bas[l]);
	add(p,x);
	if(a[p].l==a[p].r)return ;
    (a[p].l+a[p].r)>>1>=l?add_(p<<1,l,x):add_(p<<1|1,l,x);
}

int main(){
    
	srand(time(NULL));
	rnd.seed(rand()^time(NULL));

	fio.r(n);fio.r(m);
	for(int i=1;i<=n;i++){
		fio.r(bas[i]);
	}
	buildtree(1,1,n);
	
	while(m--){
        char c;
		int opt,l,r,x;
		fio.r(c);fio.r(l),fio.r(r);
        c=='Q'?opt=2:opt=3;
		if(opt==2){
			fio.r(x);
			printf("%d\n",kth_(l,r,x));
		}
		if(opt==3){
			add_(1,l,r);
			bas[l]=r; 
		}
	}
	return 0;
}