RT

提交记录

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

const int N=100010,INF=INT_MAX,inf=INT_MIN+1;
int n,m;
struct Splay{
	int s[2],p,v,size;
	void init(int _v,int _p){
		v=_v;
		p=_p;
		size=1;
	}
}tr[N<<7];
struct Segment_Tree{
	int l,r,t;
}seg[N<<7];
int idx,w[N<<7];

void push_up(int x){
	tr[x].size=tr[tr[x].s[0]].size+tr[tr[x].s[1]].size+1;
}

void rotate(int x){
	int y=tr[x].p,z=tr[y].p;
	int k=tr[y].s[1]==x;
	tr[z].s[tr[z].s[1]==y]=x;
	tr[x].p=z;
	tr[y].s[k]=tr[x].s[k^1];
	tr[tr[x].s[k^1]].p=y;
	tr[x].s[k^1]=y;
	tr[y].p=x;
	push_up(y);
	push_up(x);
}

void splay(int &root,int x,int k){
	while(tr[x].p!=k){
		int y=tr[x].p,z=tr[y].p;
		if(z!=k){
			if((tr[y].s[1]==x)^(tr[z].s[1]==y)){
				rotate(x);
			}else{
				rotate(y);
			}
		}
		rotate(x);
	}
	if(!k){
		root=x;
	}
}

void insert(int &root,int v){
	int u=root,p=0;
	while(u){
		p=u;
		u=tr[u].s[v>tr[u].v];
	}
	u=++idx;
	if(p){
		tr[p].s[v>tr[p].v]=u;
	}
	tr[u].init(v,p);
	splay(root,u,0);
}

int get_k(int root,int v){
	int u=root,res=0;
	while(u){
		if(tr[u].v<v){
			res+=tr[tr[u].s[0]].size+1;
			u=tr[u].s[1];
		}else{
			u=tr[u].s[0];
		}
	}
	return res;
}

void update(int &root,int x,int y){
	int u=root;
	while(u){
		if(tr[u].v==x){
			break;
		}else if(tr[u].v<x){
			u=tr[u].s[1];
		}else{
			u=tr[u].s[0];
		}
	}
	splay(root,u,0);
	int l=tr[u].s[0],r=tr[u].s[1];
	while(tr[l].s[1]){
		l=tr[l].s[1];
	}
	while(tr[r].s[0]){
		r=tr[r].s[0];
	}
	splay(root,l,0);
	splay(root,r,l);
	tr[r].s[0]=0;
	push_up(r);
	push_up(l);
	insert(root,y);
}

int get_pre(int root,int v){
	int u=root,res=inf;
	while(u){
		if(tr[u].v<v){
			res=max(res,tr[u].v);
			u=tr[u].s[1];
		}else{
			u=tr[u].s[0];
		}
	}
	return res;
}

int get_suc(int root,int v){
	int u=root,res=INF;
	while(u){
		if(tr[u].v>v){
			res=min(res,tr[u].v);
			u=tr[u].s[0];
		}else{
			u=tr[u].s[1];
		}
	}
	return res;
}

void build(int u,int l,int r){
	seg[u].l=l;
	seg[u].r=r;
	insert(seg[u].t,inf);
	insert(seg[u].t,INF);
	for(int i=l;i<=r;++i){
		insert(seg[u].t,w[i]);
	}
	if(l==r){
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
}

int query(int u,int a,int b,int x){
	if(seg[u].l>=a&&seg[u].r<=b){
		return get_k(seg[u].t,x)-1;
	}
	int mid=seg[u].l+seg[u].r>>1,res=0;
	if(a<=mid){
		res+=query(u<<1,a,b,x);
	}
	if(b>mid){
		res+=query(u<<1|1,a,b,x);
	}
	return res;
}

void change(int u,int p,int x){
	update(seg[u].t,w[p],x);
	if(seg[u].l==seg[u].r){
		return;
	}
	int mid=seg[u].l+seg[u].r>>1;
	if(p<=mid){
		change(u<<1,p,x);
	}else{
		change(u<<1|1,p,x);
	}
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>w[i];
	}
	build(1,1,n);
	while(m--){
		char op;
		int a,b,x;
		cin>>op;
		if(op=='Q'){
			cin>>a>>b>>x;
			int l=0,r=1e8;
			while(l<=r){
				int mid=l+r>>1ll;
				if(query(1,a,b,mid)>=x){
					r=mid-1;
				}else{
					l=mid+1;
				}
			}
			cout<<r<<endl;
		}else{
			cin>>a>>x;
			change(1,a,x);
			w[a]=x;
		}
	}
	return 0;
}