查询可以直接线段树维护，修改呢，考虑一颗替罪羊，每个点代表一段区间，他的$val$就是区间中值，线段树记录对应节点的$id$，再开一个数组记录即时的权值，因为重建时$val$可能会变。这好像是重量平衡树的应用，然而究竟什么是重量平衡树呢？

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #define inf 0x3fffffffffffffff  7 #define alp 0.75  8 #define N 500050  9 using namespace std; 10 double a[500050]; 11 int tot; 12 struct Node{ 13     Node *ch[2]; 14     double l,r; 15     int size,cover,ex,k1,k2,id; 16     void pushup(){ 17         size=ch[0]->size+ch[1]->size+ex; 18         cover=ch[0]->cover+ch[1]->cover+1; 19     } 20     bool bad(){ 21         return ch[0]->cover>=cover*alp+5||ch[1]->cover>=cover*alp+5; 22     } 23     Node(double x,double y,int z,int w,int k); 24 }*null=new Node(0,0,0,0,0),*root,*sta[N]; 25 int len; 26 Node:: Node(double x,double y,int z,int w,int k){ 27     l=x;r=y;k1=z;k2=w;id=k; 28     a[k]=(l+r)/2.0; 29     size=cover=ex=1; 30     ch[0]=ch[1]=null; 31 } 32 void init(){ 33     null->ch[0]=null->ch[1]=null; 34     null->l=null->r=null->k1=null->k2=null->id=0; 35     null->size=null->cover=null->ex=0; 36     a[0]=-5000000000000000000; 37     root=new Node(-inf,inf,0,0,++tot); 38 } 39 Node **insert(Node *&rt,double l,double r,int k1,int k2){ 40     if(rt==null){ 41         rt=new Node(l,r,k1,k2,++tot); 42         return &null; 43     } 44     rt->size++;rt->cover++; 45     Node **ret; 46     if(a[rt->k1]
           
            k1]==a[k1]&&a[rt->k2]
            
             ch[1],(rt->l+rt->r)/2.0,rt->r,k1,k2); 47 else ret=insert(rt->ch[0],rt->l,(rt->l+rt->r)/2.0,k1,k2); 48 if(rt->bad())ret=&rt; 49 return ret; 50 } 51 void travel(Node *rt){ 52 if(rt==null)return; 53 travel(rt->ch[0]); 54 if(rt->ex){ 55 sta[++len]=rt; 56 travel(rt->ch[1]); 57 } 58 else{ 59 travel(rt->ch[1]); 60 delete rt; 61 } 62 } 63 Node * divide(int l,int r,double L,double R){ 64 if(l>r)return null; 65 int mid=(l+r)>>1; 66 sta[mid]->l=L;sta[mid]->r=R;a[sta[mid]->id]=(L+R)/2.0; 67 sta[mid]->ch[0]=divide(l,mid-1,L,(L+R)/2.0); 68 sta[mid]->ch[1]=divide(mid+1,r,(L+R)/2.0,R); 69 sta[mid]->pushup(); 70 return sta[mid]; 71 } 72 void rebuild(Node *&rt){ 73 double L=rt->l,R=rt->r; 74 len=0;travel(rt); 75 rt=divide(1,len,L,R); 76 } 77 void insert(int k1,int k2){ 78 Node **p=insert(root,-inf,inf,k1,k2); 79 if(*p!=null)rebuild(*p); 80 } 81 Node *find(Node *rt,int k1,int k2){ 82 if(rt==null)return rt; 83 if(rt->ex&&a[rt->k1]==a[k1]&&a[rt->k2]==a[k2])return rt; 84 if(a[rt->k1]
             
              k1]==a[k1]&&a[rt->k2]
              
               ch[1],k1,k2); 85 else return find(rt->ch[0],k1,k2); 86 } 87 88 int w[N],maxn[N],maxpos[N]; 89 void pushup(int rt){ 90 if(a[maxn[rt<<1]]>=a[maxn[rt<<1|1]]) 91 maxn[rt]=maxn[rt<<1], 92 maxpos[rt]=maxpos[rt<<1]; 93 else maxn[rt]=maxn[rt<<1|1], 94 maxpos[rt]=maxpos[rt<<1|1]; 95 } 96 void build(int rt,int l,int r){ 97 if(l==r){maxn[rt]=w[l];maxpos[rt]=l;return ;} 98 int mid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r); 99 pushup(rt);100 }101 void update(int rt,int l,int r,int x,int y){102 if(l==r){maxn[rt]=y;maxpos[rt]=l;return ;}103 int mid=(l+r)>>1;104 if(x<=mid)update(rt<<1,l,mid,x,y);105 else update(rt<<1|1,mid+1,r,x,y);106 pushup(rt);107 }108 int MX,POS;109 void query(int rt,int l,int r,int x,int y){110 if(x<=l&&r<=y){111 if(a[MX]
               
                >1;116 if(x<=mid)query(rt<<1,l,mid,x,y);117 if(y>mid)query(rt<<1|1,mid+1,r,x,y);118 }119 120 int n,m;121 int main(){122 init();123 scanf("%d%d",&n,&m);124 for(int i=1;i<=n;i++)w[i]=1;125 build(1,1,n);126 char ch[2];127 int x,y,z,l,r;128 while(m--){129 scanf("%s",ch);130 if(ch[0]=='C'){131 scanf("%d%d%d",&x,&y,&z);132 Node *now=find(root,w[x],w[y]);133 if(now!=null)w[z]=now->id;134 else{insert(w[x],w[y]);w[z]=tot;}135 update(1,1,n,z,w[z]);136 }137 if(ch[0]=='Q'){138 scanf("%d%d",&l,&r);139 MX=POS=0;query(1,1,n,l,r);140 printf("%d\n",POS);141 }142 }143 return 0;144 }