题解：
好像是什么替罪羊树
然后看了几个题解
然后就抄了一边
代码：
#include<bits/stdc++.h> using namespace std; const int N=1000005; int n,m,rt,R,mx[N],pos[N],id[N],top; double a[N]; char ch[5]; 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 (x.l!=y.l||x.r!=y.r)return 0; return 1; } }; struct sctree { data v[N]; int cnt,size[N],ls[N],rs[N]; void dfs(int k) { if(!k)return; dfs(ls[k]); id[++top]=k; dfs(rs[k]); } void build(int &k,int l,int r,double lv,double rv) { if(l>r){k=0;return;} double mv=(lv+rv)/2.0; int mid=(l+r)/2; k=id[mid];a[k]=mv; build(ls[k],l,mid-1,lv,mv); build(rs[k],mid+1,r,mv,rv); size[k]=size[ls[k]]+size[rs[k]]+1; } void rebuild(int &k,double lv,double rv) { top=0; dfs(k); build(k,1,top,lv,rv); } int insert(int &k,double lv,double rv,data val) { double mv=(lv+rv)/2.0; if (!k) { k=++cnt;a[k]=mv;v[k]=val;size[k]=1; return k; } int p; if (val==v[k])return k; else { size[k]++; if (val>v[k])p=insert(rs[k],mv,rv,val); else p=insert(ls[k],lv,mv,val); } if (size[k]*0.75>max(size[ls[k]],size[rs[k]])) { if (R) { if(ls[k]==R)rebuild(ls[k],lv,mv); else rebuild(rs[k],mv,rv); R=0; } } else R=k; return p; } }sc; void modify(int k,int l,int r,int v) { int mid=(l+r)>>1; if (l==r){mx[k]=l;return;} if (v<=mid)modify(k<<1,l,mid,v); else modify(k<<1|1,mid+1,r,v); int x=mx[k<<1],y=mx[k<<1|1]; if (a[pos[x]]>=a[pos[y]])mx[k]=x; else mx[k]=y; } int query(int k,int l,int r,int x,int y) { int mid=(l+r)>>1; if (l==x&&y==r)return mx[k]; int t=0,p=0; if (x<=mid) { p=query(k<<1,l,mid,x,min(mid,y)); if (a[pos[p]]>a[pos[t]])t=p; } if (y>mid) { p=query(k<<1|1,mid+1,r,max(x,mid+1),y); if(a[pos[p]]>a[pos[t]])t=p; } return t; } int main() { scanf("%d%d",&n,&m); 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++)modify(1,1,n,i); int l,r,K; for (int i=1;i<=m;i++) { scanf("%s%d%d",ch+1,&l,&r); if (ch[1]=='C') { scanf("%d",&K); pos[K]=sc.insert(rt,0,1,(data){pos[l],pos[r]}); if(R)sc.rebuild(rt,0,1);R=0; modify(1,1,n,K); } else printf("%d ",query(1,1,n,l,r)); } return 0; }