树套树求卡常

#include<bits/stdc++.h>

using namespace std;

const int N=100005,INF=2147483647;

mt19937_64 rnd(time(0));

int n,m;
int input[N];

struct Node {
	int l,r;
	int key,val;
	int size;
}tre[40*N];

#define lson tre[now].l
#define rson tre[now].r

int root[4*N],idx;
int x,y,z;

inline int gnode(int key) {
	tre[++idx].key=key;
	tre[idx].val=rnd();
	tre[idx].size=1;
	return idx;
}

inline void maintain(int now) {tre[now].size=tre[lson].size+tre[rson].size+1;}
inline void split(int now,int key,int& x,int& y) {
	if(!now) x=y=0;
	else {
		if(tre[now].key<=key) {
			x=now;
			split(rson,key,rson,y);
		}else {
			y=now;
			split(lson,key,x,lson);
		}
		maintain(now);
	}
}

inline int merge(int x,int y) {
	if(!x || !y) return x+y;
	if(tre[x].val>=tre[y].val) {
		tre[x].r=merge(tre[x].r,y);
		maintain(x);
		return x;
	}else {
		tre[y].l=merge(x,tre[y].l);
		maintain(y);
		return y;
	}
}

inline void insert(int& root,int num) {
	split(root,num-1,x,y);
	x=merge(x,gnode(num));
	root=merge(x,y);
}

inline void del(int& root,int num) {
	split(root,num,x,y);
	split(x,num-1,x,z);
	z=merge(tre[z].l,tre[z].r);
	root=merge(x,merge(z,y));
}

inline int lst(int& root,int k) {
	split(root,k-1,x,y);
	if(x==0) return -INF;
	int now=x,ans;
	while(rson) now=rson;
	ans=tre[now].key;
	merge(x,y);
	return ans;
}

inline int nxt(int& root,int k) {
	split(root,k,x,y);
	if(y==0) return INF;
	int now=y,ans;
	while(lson) now=lson;
	ans=tre[now].key;
	merge(x,y);
	return ans;
}

inline int grnk(int& root,int k) { // 查询值 k 的排名，k 可能不存在 
	split(root,k-1,x,y);
	int ans=tre[x].size;
	merge(x,y);
	return ans;
}

// 线段树 
struct Tnode {
	int l,r;
}Tre[4*N];

#define mid (Tre[now].l+Tre[now].r>>1)
#define Lson (now*2)
#define Rson (now*2+1)

inline int gsiz(int now) {return Tre[now].r-Tre[now].l+1;}

inline void build(int now,int l,int r) {
	Tre[now].l=l,Tre[now].r=r;
	for(int i=Tre[now].l;i<=Tre[now].r;++i) insert(root[now],input[i]);
	if(l==r) return;
	build(Lson,l,mid);build(Rson,mid+1,r);
}

inline void change(int now,int p,int k) {
	if(Tre[now].l>p || Tre[now].r<p) return;
	del(root[now],input[p]);
	insert(root[now],k);
	if(Tre[now].l==Tre[now].r) return;
	change(Lson,p,k);change(Rson,p,k);
}

inline int query_k(int now,int l,int r,int k) {
	if(Tre[now].l>r || Tre[now].r<l) return 0;
	if(Tre[now].l>=l && Tre[now].r<=r) return grnk(root[now],k);
	return query_k(Lson,l,r,k)+query_k(Rson,l,r,k);
}

inline int query_lst(int now,int l,int r,int k) {
	if(Tre[now].l>r || Tre[now].r<l) return -INF;
	if(Tre[now].l>=l && Tre[now].r<=r) return lst(root[now],k);
	return max(query_lst(Lson,l,r,k),query_lst(Rson,l,r,k));
}

inline int query_nxt(int now,int l,int r,int k) {
	if(Tre[now].l>r || Tre[now].r<l) return INF;
	if(Tre[now].l>=l && Tre[now].r<=r) return nxt(root[now],k);
	return min(query_nxt(Lson,l,r,k),query_nxt(Rson,l,r,k));
}

int query_rnk(int l,int r,int k) {
	int L=0,R=1e9,Mid,ans=0;
	while(L<=R) {
		Mid=L+R>>1;
		if(query_k(1,l,r,Mid)+1<=k) L=Mid+1,ans=Mid;
		else R=Mid-1;
	}
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	
	cin >> n >> m;
	for(int i=1;i<=n;++i) cin >> input[i];
	
	build(1,1,n);
	
	int l,r,k,ans;char op;
	for(int i=1;i<=m;++i) {
		cin >> op;
		if(op=='Q') {
			cin >> l >> r >> k;
			cout << query_rnk(l,r,k) << '\n';
		}else {
			cin >> l >> k;
			change(1,l,k);
			input[l]=k;
		}
	}
	
	return 0;
}