题意：太难说了。。手动去看吧反正不是权限题。
膜拜VFK大爷的神题！
其实一开始思路挺清楚的，如果我们能做到用一个实数去代表“数”，这就是裸的动态区间最值查询。
关键是怎么用实数去表示。如果我们单纯的把两个数进行O（1）运算去得到一个实数，这样很轻松就会被卡掉，因为无论是longlong还是double都是有限度的。怎么做呢？
这里有一个技巧：我们维护一个重量平衡树，每个节点管辖一个区间，这个区间的中位数为这个点的权值，而它的左儿子管辖左半边，右儿子管辖右半边。
问题来了，这不是差不多吗？并不是这样。因为我们会重构，树高有保证，所以我们肯定能表示出每一个数，而且还是绰绰有余。
重量平衡树可以用不旋转的treap或替罪羊树。
（吐槽一句，第一次写替罪羊树，真的好TM难写啊还套了个线段树而且我常数大的飞起，写了一整天）
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define LL long long
inline LL read(){
LL x=,f=; char a=getchar();
while(a<'' || a>'') {if(a=='-') f=-; a=getchar();}
while(a>='' && a<='') x=x*+a-'',a=getchar();
return x*f;
}
int n,m; char st[];
LL MX;
#define SGT Scapegoat_Tree
#define ST Segment_Tree namespace Scapegoat_Tree{
#define eps 1e-12
const double alpha=0.75;
int ltst,wh,size=,tmp[N],root=,anew;
struct sgt{
LL l,r,mid; int fir,sec;
int son[],sz;
}tr[N];
inline int dcmp(int x,int y){
if(fabs((double)tr[x].sz*alpha-(double)tr[y].sz)<eps) return ;
else return (double)tr[x].sz*alpha>(double)tr[y].sz?:-;
}
inline void update(int x){
tr[x].sz=tr[tr[x].son[]].sz+tr[tr[x].son[]].sz+;
}
inline bool balance(int x){
return dcmp(x,tr[x].son[])>= && dcmp(x,tr[x].son[])>=;
}
void travel(int x){
if(!x) return;
travel(tr[x].son[]);
tmp[++tmp[]]=x;
travel(tr[x].son[]);
}
void rebuild(int &x,int l,int r,LL L,LL R){
if(l>r) {x=; return;}
int mid=(l+r)>>;
LL M=(L+R)/;
x=tmp[mid]; tr[x].l=L; tr[x].r=R; tr[x].mid=M;
if(l==r) {tr[x].sz=; tr[x].son[]=; tr[x].son[]=; return;}
rebuild(tr[x].son[],l,mid-,L,M); rebuild(tr[x].son[],mid+,r,M,R);
update(x);
}
void insert(int& x,LL L,LL R,int fir,int sec){
if(!x) {x=++size; anew=x;tr[x]=(sgt){L,R,(L+R)/,fir,sec,,,}; return;}
if(tr[tr[x].fir].mid==tr[fir].mid && tr[tr[x].sec].mid==tr[sec].mid) {anew=x; return;}
else if(tr[tr[x].fir].mid==tr[fir].mid){
if(tr[tr[x].sec].mid>tr[sec].mid) insert(tr[x].son[],tr[x].l,tr[x].mid,fir,sec);
else insert(tr[x].son[],tr[x].mid,tr[x].r,fir,sec);
}
else{
if(tr[tr[x].fir].mid>tr[fir].mid) insert(tr[x].son[],tr[x].l,tr[x].mid,fir,sec);
else insert(tr[x].son[],tr[x].mid,tr[x].r,fir,sec);
}
update(x);
if(tr[x].son[] && !balance(tr[x].son[])) ltst=x,wh=;
else if(tr[x].son[] && !balance(tr[x].son[])) ltst=x,wh=;
if(x==root && !balance(x)) tmp[]=,travel(root),rebuild(root,,tmp[],,MX);
}
}
namespace Segment_Tree{
int a[N];
struct seg{
int l,r,son[],mx_pos,num;
}tr[N];
inline void update(int x){
if(SGT::tr[tr[tr[tr[x].son[]].mx_pos].num].mid==SGT::tr[tr[tr[tr[x].son[]].mx_pos].num].mid){
int le=tr[tr[x].son[]].mx_pos,ri=tr[tr[x].son[]].mx_pos;
tr[x].mx_pos=tr[le].l<tr[ri].l?le:ri;
}
else if(SGT::tr[tr[tr[tr[x].son[]].mx_pos].num].mid>SGT::tr[tr[tr[tr[x].son[]].mx_pos].num].mid)
tr[x].mx_pos=tr[tr[x].son[]].mx_pos;
else tr[x].mx_pos=tr[tr[x].son[]].mx_pos;
}
void build(int x,int l,int r){
if(l==r) {tr[x]=(seg){l,r,,,x,};return;}
int mid=(l+r)>>; tr[x].l=l; tr[x].r=r;
tr[x].son[]=x<<; build(tr[x].son[],l,mid);
tr[x].son[]=x<<|; build(tr[x].son[],mid+,r);
update(x);
}
void modify(int x,int ai,int v){
int l=tr[x].l,r=tr[x].r;
if(l==r) {tr[x].num=v; return;}
int mid=(l+r)>>;
if(ai<=mid) modify(tr[x].son[],ai,v);
else modify(tr[x].son[],ai,v);
update(x);
}
int query(int x,int L,int R){
int l=tr[x].l,r=tr[x].r;
if(l==L && r==R) return tr[x].mx_pos;
int mid=(l+r)>>;
if(R<=mid) return query(tr[x].son[],L,R);
else if(mid<L) return query(tr[x].son[],L,R);
else{
int le=query(tr[x].son[],L,mid),ri=query(tr[x].son[],mid+,R);
if(SGT::tr[tr[le].num].mid==SGT::tr[tr[ri].num].mid) return tr[le].l<tr[ri].l?le:ri;
return SGT::tr[tr[le].num].mid>SGT::tr[tr[ri].num].mid?le:ri;
}
}
} int main(){
n=read(); m=read(); MX=;
for(int i=;i<=;i++) MX*=;
ST::build(,,n); SGT::tr[]=(SGT::sgt){,MX,(+MX)/,,,,,};
for(int i=;i<=n;i++) ST::a[i]=;
while(m--){
scanf("%s",st); int k,l=read(),r=read();
if(st[]=='C'){
k=read();
l=ST::a[l]; r=ST::a[r]; SGT::ltst=; SGT::insert(SGT::root,,MX,l,r);
if(SGT::ltst) {
SGT::tmp[]=; SGT::travel(SGT::tr[SGT::ltst].son[SGT::wh]);
LL L=SGT::tr[SGT::tr[SGT::ltst].son[SGT::wh]].l,R=SGT::tr[SGT::tr[SGT::ltst].son[SGT::wh]].r;
SGT::rebuild(SGT::tr[SGT::ltst].son[SGT::wh],,SGT::tmp[],L,R);
}
ST::modify(,k,SGT::anew),ST::a[k]=SGT::anew;
}else{
int ans=ST::query(,l,r);
ans=ST::tr[ans].l;
printf("%d\n",ans);
}
}
return ;
}