FHQ-Treap Wa 0分 求调

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,INF=1145141919;
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

//-------------FHQ-Treap-------------

int n,m,root,ncnt,dl,dr,dx;

struct node{
    int l,r,rnd,v,root,siz,tag;
}tr[N];

int get_node(int x){
    ncnt++;
    tr[ncnt].v=x;
    tr[ncnt].rnd=rand();
    tr[ncnt].siz=1;
    return ncnt;
}

void updata(int k){
    tr[k].siz=tr[tr[k].l].siz+tr[tr[k].r].siz+1;
}

void pushdown(int k){
    if(!tr[k].tag)return;
    swap(tr[k].l,tr[k].r);
    tr[k].tag=0;
    tr[tr[k].l].tag^=1;
    tr[tr[k].r].tag^=1;
}

void split(int k,int x,int &l,int &r){//k 为 FHQ-Treap 的根，l 和 r 为分裂出来左右两个树的根
    if(!k){//空树
        l=r=0;
        return;
    }
    pushdown(k);
    if(tr[tr[k].l].siz+1<=x){//小了往右走
        l=k;
        split(tr[k].r,x-tr[tr[k].l].siz-1,tr[k].r,r);
    }else{//大了往左走
        r=k;
        split(tr[k].l,x,l,tr[k].l);
    }
    updata(k); 
}

int merge(int l,int r){
    if(!l||!r)return l+r;//空树
    if(tr[l].rnd<=tr[r].rnd){//右树分进左树右儿子
        pushdown(l);
        tr[l].r=merge(tr[l].r,r);
        updata(l);
        return l;
    }else{//左树分进右树左儿子
        pushdown(r);
        tr[r].l=merge(l,tr[r].l);
        updata(r);
        return r;
    }
}

void rev(int l,int r){
    split(root,l-1,dl,dr);
    split(dr,r,dx,dr);
    tr[dx].tag^=1;
    root=merge(merge(dl,dx),dr);
}

void print(int k){
    pushdown(k);
    if(tr[k].l)print(tr[k].l);
    printf("%d ",tr[k].v);
    if(tr[k].r)print(tr[k].r);
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)root=merge(root,get_node(i));
    print(root);
    for(int i=1,l,r;i<=m;i++){
        l=read(),r=read();
        rev(l,r);
        print(root);
    }
    print(root);
}