fhq treap 90pts TLE on #9

参考了讨论区所说的分裂时父节点清零的问题，可是改动之后仍然没有效果。

救救孩子

#include <cstdio>
#include <random>
#include <algorithm>
#define Reg register
#define lson(x) tr[x].ls
#define rson(x) tr[x].rs
#define fa(x) tr[x].fa
using namespace std;
const int maxn=101000;
int n,tot,root,Ider[maxn];
struct node{
    int id,val;
    bool operator <(const node &A) const{
        if(val==A.val) return id<A.id;
        return val<A.val;
    }
}a[maxn];
struct FHQ_Treap{
    int ls,rs,lz,siz,dat,fa,val;
}tr[maxn];
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }
    return s*w;
}
inline void dosth(int rt){
    if(!rt) return;
    tr[rt].lz^=1;
    swap(lson(rt),rson(rt));
}
inline void pushdown(int rt){
    if(tr[rt].lz){
        dosth(lson(rt)),dosth(rson(rt));
        tr[rt].lz=0;
    }
}
inline void pushup(int rt){
    tr[rt].siz=tr[lson(rt)].siz+tr[rson(rt)].siz+1;
    fa(lson(rt))=rt;
    fa(rson(rt))=rt;
}
inline void cleared(int rt){
    if(rt!=root) cleared(fa(rt));
    pushdown(rt);
}
inline int Findsiz(int rt){
    cleared(rt);
    int res=tr[lson(rt)].siz+1;
    while(rt!=root){
        if(rt==rson(fa(rt))) res+=tr[lson(fa(rt))].siz+1;
        rt=fa(rt);
    }
    return res;
}
inline void Split(int rt,int k,int &x,int &y){
    if(!rt) return x=0,y=0,void();
    pushdown(rt);
    if(k>tr[lson(rt)].siz) x=rt,Split(rson(rt),k-tr[lson(rt)].siz-1,rson(rt),y);
    else y=rt,Split(lson(rt),k,x,lson(rt));
    pushup(rt);
}
inline int Merge(int u,int v){
    if(!u|!v) return u|v;
    if(tr[u].dat<tr[v].dat){
        pushdown(u);
        rson(u)=Merge(rson(u),v);
        pushup(u);
        return u;
    }else{
        pushdown(v);
        lson(v)=Merge(u,lson(v));
        pushup(v);
        return v;
    }
}
inline void update(int l,int r){
    int x=0,y=0,z=0;
    Split(root,r,x,y);
    Split(x,l-1,x,z);
    fa(x)=fa(y)=fa(z)=0;
    dosth(z);
    x=Merge(x,z);
    root=Merge(x,y);
}
inline int build(int l,int r){
    if(l>r) return 0;
    int mid=(l+r)>>1,dir=++tot;
    tr[dir].dat=rand();
    Ider[mid]=dir;
    tr[dir].siz=1;
    tr[dir].val=a[mid].val;
    lson(dir)=build(l,mid-1);
    rson(dir)=build(mid+1,r);
    pushup(dir);
    return dir;
}
int main(){
    srand(time(0));
    n=read();
    for(Reg int i=1;i<=n;++i) a[i].val=read(),a[i].id=i;
    root=build(1,n);
    sort(a+1,a+1+n);
    for(Reg int i=1;i<=n;++i){
        int p=Findsiz(Ider[a[i].id]);
        printf("%d ",p);
        update(i,p);
    }
    printf("\n");
    return 0; 
}