为什么我没有copy题面呢？看到题面你就懂了....hh
题意：
定义一个二元组(二元组的两个元素可以是二元组)
如(x,y)，其中x可以是(a,(b,c))之类的
定义二元组的比较方式：先比较左边，左边相同再比较右边。
递归比较可以用随便哪颗平衡树维护,70分
考虑对于每个 二元组，对他定义一个实数的映射来表示它的大小，想象我们在将它插入平衡树时,一路比较,按照比较结果判断是插入左子树还是右子树,那实际上它最终的位置就是他的映射,70分做法即为如此，缺陷在于比较是log的，可是，我们既然已经知道他所在最终位置(映射出的实数)，且映射的大小关系等价于它本身的大小关系，那为何不用映射出的实数去构造新的二元组呢？这样比较就变成O(1)的了。
可是，映射显然只是一种相对的位置关系，常用的平衡树均有旋转操作，那就意味着映射大小改变，将不断的重新计算映射，得不偿失。可是，非旋转treap和替罪羊树并无旋转操作啊！
代码：
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<climits>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define N 500020
using namespace std;
inline int read()
{int x=0,f=1;char ch;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
int n,m;
double a[N];
int ts[N],tot;
int R,rt,pos[N],mx[N];
struct data
{int l,r;friend bool operator < (data x,data y){if(a[x.l]<a[y.l])return 1;if(a[x.l]==a[y.l]&&a[x.r]<a[y.r])return 1;return 0;} friend bool operator == (data x,data y){if(a[x.l]!=a[y.l]||a[x.r]!=a[y.r])return 0;return 1;}
};
struct sctree
{int cnt,size[N],ls[N],rs[N];data v[N];void dfs(int k){if(!k)return ;dfs(ls[k]);ts[++tot]=k;dfs(rs[k]);}void build(int &u,int l,int r,double lv,double rv){if(l>r){u=0;return;}double mv=(lv+rv)/2.0;int mid=(l+r)>>1;u=ts[mid];a[u]=mv;build(ls[u],l,mid-1,lv,mv);build(rs[u],mid+1,r,mv,rv);size[u]=size[ls[u]]+size[rs[u]]+1;}void rebuild(int &u,double lv,double rv){tot=0;dfs(u);build(u,1,tot,lv,rv);}int insert(int &u,double lv,double rv,data val){double mv=(lv+rv)/2.0;if(!u){u=++cnt;v[u]=val;a[u]=mv;size[u]=1;return u;}int p;if(val==v[u])return u;else{size[u]++;if(val<v[u])p=insert(ls[u],lv,mv,val);else p=insert(rs[u],mv,rv,val);}if(size[u]*0.75>max(size[ls[u]],size[rs[u]])){if(R){if(ls[u]==R)rebuild(ls[u],lv,mv);else rebuild(rs[u],mv,rv);R=0;}}else R=u;return p;}
}sc;
void add(int u,int l,int r,int v)
{if(l==r){mx[u]=v;return;}int mid=(l+r)>>1;if(v<=mid)add(u<<1,l,mid,v);else add(u<<1|1,mid+1,r,v);int x=mx[u<<1],y=mx[u<<1|1];if(a[pos[x]]<a[pos[y]])mx[u]=y;else mx[u]=x;
}int query(int u,int l,int r,int x,int y)
{if(x==l&&y==r)return mx[u];int mid=(l+r)>>1;int ret=0;if(y<=mid)return query(u<<1,l,mid,x,y);else if(x>mid)return query(u<<1|1,mid+1,r,x,y);else{int s=query(u<<1,l,mid,x,mid);int t=query(u<<1|1,mid+1,r,mid+1,y);if(a[pos[s]]>a[pos[ret]])ret=s;if(a[pos[t]]>a[pos[ret]])ret=t;}return ret;
}
int main()
{n=read(),m=read();char ch[10];a[0]=-1;sc.insert(rt,0,1,(data){0,0});for(int i=1;i<=n;i++)pos[i]=1;for(int i=1;i<=n;i++)add(1,1,n,i);for(int i=1;i<=m;i++){scanf("%s",ch);int l=read(),r=read();if(ch[0]=='C'){int k=read();pos[k]=sc.insert(rt,0,1,(data){pos[l],pos[r]});if(R)sc.rebuild(rt,0,1);R=0;add(1,1,n,k);}else printf("%d\n",query(1,1,n,l,r));}
}