FHQTreap求调

#include<bits/stdc++.h>
using namespace std;
int n,op,x,root=0,cnt,lon;
struct le{
    int v,k,son[2],size,lz;
}tr[100100];
void clean(int id){
    tr[id].v=0;
    tr[id].k=0;
    tr[id].son[1]=tr[id].son[0]=0;
    tr[id].size=0;
}
void up(int id){
    tr[id].size=tr[tr[id].son[0]].size+tr[tr[id].son[1]].size+1;
}
void push_down(int id){
    swap(tr[id].son[0],tr[id].son[1]);
    tr[tr[id].son[0]].lz^=1;
    tr[tr[id].son[1]].lz^=1;
    tr[id].lz=0;
}
int merge(int u,int v){
    if(u==0||v==0)return u|v;
    if(tr[u].k>tr[v].k){
        if(tr[v].lz)push_down(v); 
        tr[v].son[0]=merge(u,tr[v].son[0]);
        up(v);
        return v;
    }else{
        if(tr[u].lz)push_down(u); 
        tr[u].son[1]=merge(tr[u].son[1],v);
        up(u);
        return u;
    }
}
void split_s(int id,int k,int &x,int &y){
    if(!id){
        x=y=0;
        return;
    }
    if(tr[id].lz){
        push_down(id);
    }
    if(tr[tr[id].son[0]].size<k){
        x=id;
        split_s(tr[id].son[1],k-tr[tr[id].son[0]].size-1,tr[id].son[1],y);
    }else{
        y=id;
        split_s(tr[id].son[0],k,x,tr[id].son[0]);
    }
    up(id);
}
void put(int x){
    int a,b,kkk;
    kkk=++cnt;
    tr[kkk].v=x;
    tr[kkk].size=1;
    tr[kkk].lz=0;
    tr[kkk].k=rand();
    root=merge(root,kkk);
}
void print(int id){
    if(!id)return;
    if(tr[id].lz)push_down(id);
    if(tr[id].son[0])print(tr[id].son[0]);
    cout<<tr[id].v<<" ";
    if(tr[id].son[1])print(tr[id].son[1]);
}
int main(){
    cin>>n>>x;
    for(int i=1;i<=n;i++){
        put(i);
    } 
    for(int i=1;i<=x;i++){
        int l,r;
        cin>>l>>r;
        int r1=0,r2=0,r3=0;
        split_s(root,r,r1,r2);
//      cout<<r1<<" "<<r2<<endl;
        split_s(r1,l-1,r1,r3);
        tr[r3].lz^=1;
        root=merge(merge(r1,r2),r3);
    }   
    print(root);
    return 0;
}