FHQ Treap 复杂度假吗

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2000005;
int n,rt=0,cnt=0;
mt19937 rnd(114514u);
struct Treap{
    int l,r,p,sz;
    bool x,tag1,tag2;
    // tag1下标，tag2值
}t[MAXN];
inline void pushup(int x){
    t[x].sz=t[t[x].l].sz+t[t[x].r].sz+1;
}
inline void pushdown(int x){
    if(t[x].tag1){
        swap(t[x].l,t[x].r);
        t[t[x].l].tag1^=1;
        t[t[x].r].tag1^=1;
        t[x].tag1=0;
    }
    if(t[x].tag2){
        t[x].x^=1;
        t[t[x].l].tag2^=1;
        t[t[x].r].tag2^=1;
        t[x].tag2=0;
    }
}
inline void newnode(int x){
    t[++cnt].x=x;
    t[cnt].p=rnd();
    t[cnt].l=t[cnt].r=0;
    t[cnt].sz=1;
    t[cnt].tag1=t[cnt].tag2=0;
}
inline void split(int x,int w,int &l,int &r){
    if(!x)
        return (void)(l=r=0);
    pushdown(x);
    if(t[t[x].l].sz+1<=w)
        l=x,split(t[x].r,w-t[t[x].l].sz-1,t[x].r,r);
    else
        r=x,split(t[x].l,w,l,t[x].l);
    pushup(x);
}
inline int merge(int l,int r){
    if(!l||!r)
        return l|r;
    if(t[l].p>t[r].p){
        pushdown(l);
        t[l].r=merge(t[l].r,r);
        pushup(l);
        return l;
    }else{
        pushdown(r);
        t[r].l=merge(l,t[r].l);
        pushup(r);
        return r;
    }
}
inline void output(int x){
    if(!x)
        return ;
    pushdown(x);
    output(t[x].l);
    printf("%d ",t[x].x);
    output(t[x].r);
}
signed main(){
    scanf("%d",&n);
    for(int i=1,k;i<=n;++i){
        scanf("%d",&k);
        newnode(k);
        rt=merge(rt,cnt);
    }
    // output(rt);
    // printf("\n");
    for(int i=1,l,r;i<=n;++i){
        split(rt,i,l,r);
        t[l].tag1^=1;
        t[l].tag2^=1;
        rt=merge(l,r);
    }
    output(rt);
    return 0;
}