P3391 文艺平衡树非旋treap 求调

如果我个人分析没问题的话，是在split后merge是彻底改变了树的形态

#include<bits/stdc++.h>
using namespace std;
int n,m,l,r;
struct FHQ_freap{
    random_device rd; 
    mt19937 ran;
    struct node{
        int val,sz,l,r;
        unsigned int key;
        bool f;
    }t[400500];int root,cnt;
    void pd(int u){swap(t[u].l,t[u].r);t[t[u].l].f^=1;t[t[u].r].f^=1;t[u].f=0;}
    void pu(int u){t[u].sz+=t[t[u].l].sz+t[t[u].r].sz+1;}
    FHQ_freap():ran(rd()),root(0),cnt(0){}
    int _new(int val){
        ++cnt;
        t[cnt]={val,1,0,0,ran(),0};
        return cnt;
    }
//  void split(int u,int s,int&l,int&r){
//      cout<<"in split "<<u<<' '<<s<<' '<<l<<' '<<r<<'\n';
//      if(!u){l=r=0;return;}
//      if(t[u].f)pd(u);
//      if(t[t[u].l].sz+1<=s){
//          l=u;
//          split(t[u].r,s-t[t[u].l].sz-1,t[u].r,r);
//      }else{
//          r=u;
//          split(t[u].l,s,l,t[u].l);
//      }
//      pu(u);
//  }
void split(int u,int x,int &l,int &r){
        cout<<"in split "<<u<<' '<<x<<' '<<l<<' '<<r<<'\n';
    if(!u){
        l=r=0;
        return ;
    }
    if(t[u].f)//处理当时的懒标记 
        pd(u);//下传懒标记 
    //按照区间分割 
    if(t[t[u].l].sz+1<=x){//确定左儿子 
        l=u;
        split(t[u].r,x-t[t[u].l].sz-1,t[u].r,r);//!注意右儿子的此时的size满足的值需要减去左儿子的个数  
    }
    else{//确定右儿子 
        r=u;
        split(t[u].l,x,l,t[u].l);//!注意左儿子此时的size不需要减去,理由建范浩强平衡树模板 
    }
    pu(u);//同模板一样,更新size的值 
}
//  int merge(int l,int r){
//      if(!l||!r)return l|r;
//      if(t[l].key<t[r].key){
//          if(t[l].f)pd(l);
//          t[l].r=merge(t[l].r,r);
//          pu(l);return l;
//      }else{
//          if(t[r].f)pd(r);
//          t[r].l=merge(l,t[r].l);
//          pu(r);return r;
//      }
//  }
int merge(int l,int r){//合并操作 
    if(!l || !r)
        return l+r;
    //按照键值维护一个小根堆 
    if(t[l].key<t[r].key){//l当父节点 
        if(t[l].f)//下传懒标记 
            pd(l);
        t[l].r=merge(t[l].r,r);//确定l的右儿子 
        pu(l);return l;
    }
    else{//r当父节点 
        if(t[r].f)//下传懒标记 
            pd(r);
        t[r].l=merge(l,t[r].l);//确定r的左儿子 
        pu(r);return r;
    }   
}

    void add(int val){
        root=merge(root,_new(val));
    }
//  int c;
    void print(int u){
//      c++;
        if(t[u].f)pd(u);
        if(t[u].l)print(t[u].l);
        cout<<t[u].val<<' ';
//      cerr<<c<<'\n';
        if(t[u].r)print(t[u].r);
//      c--;
    }
}fhq;
int main(){
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)fhq.add(i);
//  fhq.c=0;
    fhq.print(fhq.root);
    for(int i=1;i<=m;i++){
        cin>>l>>r;
        int t1,t2,t3;
        fhq.split(fhq.root,r,t1,t3);
        cerr<<"\n";
        fhq.split(t1,l-1,t1,t2);
        cerr<<'\n';
        fhq.t[t2].f^=1;
        cerr<<t1<<' '<<t2<<' '<<t3<<'\n';
        fhq.print(t1);cout<<'\n';
        fhq.print(t2);cout<<'\n';
        fhq.print(t3);cout<<'\n';
        fhq.root=fhq.merge(fhq.merge(t1,t2),t3);
        fhq.print(fhq.root);cout<<'\n';
    }fhq.print(fhq.root);
    return 0;
}