来自FallDream的博客，未经允许，请勿转载，谢谢。

---

 

 

 

考虑用一个实数来表示大小关系。维护两个平衡树，一棵splay来维护区间，然后一个替罪羊来维护每个数的标号。

插入一种数的时候，可以取它的前驱后继的平均值。然后替罪羊重建的时候正好吧数字重新标号即可。

#include
     
      #include
      
       #define MN 500000#define ld long double#define INF (ld)1e99using namespace std;inline int read(){    int x = 0 , f = 1; char ch = getchar();    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;}namespace SGT{    ld s[MN+5];int A[MN+5],B[MN+5],rt,fa[MN+5],cnt=0,c[MN+5][2],mark=0,q[MN+5],size[MN+5],top;    int GetID(int&x,int a,int b,ld lt,ld rt,int last=0)    {        if(!x){            x=++cnt;A[x]=a;B[x]=b;            s[x]=(lt+rt)/2.0;fa[x]=last;size[x]=1;            return cnt;        }        if(x!=2&&A[x]==a&&B[x]==b) return x;        int res;        if(x==2||((s[A[x]]==s[a]&&s[B[x]]
       
        
         0.75*size[x]) mark=x;        return res;    }        void ins(int&x,int a,int b,ld ci,int last=0)    {        if(!x){            x=++cnt;s[x]=ci;            A[x]=a;B[x]=b;fa[x]=last;            return;        }            if((s[A[x]]==s[a]&&s[B[x]]
         
          
           r){x=0;return;} int mid=l+r>>1;x=q[mid];s[x]=(lt+rt)/2.0;fa[x]=last; build(c[x][0],l,mid-1,lt,s[x],x); build(c[x][1],mid+1,r,s[x],rt,x); size[x]=size[c[x][0]]+size[c[x][1]]+1; } void rebuild() { top=0;Dfs(mark);int y=fa[mark]; if(!y) build(rt,1,top,s[q[1]],s[q[top]],0); else build(c[y][c[y][1]==mark],1,top,s[q[1]],s[q[top]],y); mark=0; }} struct Data{ int x,from; friend Data operator+(Data a,Data b) { if(SGT::s[a.x]==SGT::s[b.x]) return (Data){a.x,min(a.from,b.from)}; if(SGT::s[a.x]>SGT::s[b.x]) return a; else return b; }}s[MN+5];struct data{ld a,b,x; bool operator <(const data&y)const{ return a==y.a?b
           
            
             x],k); update(x); }void build(int&x,int l,int r,int last){ if(l>r){x=0;return;} int mid=l+r>>1;x=mid;fa[x]=last; build(c[x][0],l,mid-1,x); build(c[x][1],mid+1,r,x); update(x);}char op[10];int main(){ n=read();m=read(); SGT::cnt=1;SGT::s[0]=-1;SGT::s[1]=INF; SGT::ins(SGT::rt,0,0,0);SGT::ins(SGT::rt,1,1,INF); for(int i=1;i<=n+2;++i) num[i]=0; build(rt,1,n+2,0); for(int i=1;i<=m;++i) { scanf("%s",op+1); if(op[1]=='C') { int a=read(),b=read(),k=read(); num[k]=SGT::GetID(SGT::rt,num[a],num[b],0,INF); if(SGT::mark) SGT::rebuild(); Modify(rt,k+1);splay(k+1,rt); } else { int l=read(),r=read(); int x=Split(l,r); printf("%d\n",s[x].from); } } return 0;}