这份替罪羊树板子好像慢成 $O(n^2)$ 了，有大佬能看看哪里写挂了么

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;

namespace tree{
#define ls (son[u][0])
#define rs (son[u][1])
#define mid ((l+r)>>1)
    const int K=0.7;
    int tot,val[N*N*3],son[N*N*3][2],spa[N*N*3],siz[N*N*3],rt,tmp[N*N*3],siztmp;
    void pushup(int u){siz[u]=siz[ls]+siz[rs]+1;}
    bool legal(int u){return max(siz[ls],siz[rs])<=siz[u]*K;}
    void build(int l,int r,int &u){
        if(l>r) return u=0,void();
        u=tmp[mid],build(l,mid-1,ls),build(mid+1,r,rs),pushup(u);
    }
    void flatten(int u){
        if(!u) return;
        flatten(ls),tmp[++siztmp]=u,flatten(rs);
    }
    void rebuild(int &u){siztmp=0,flatten(u),build(1,siztmp,u);}
    int insert(int w,int &u=rt){
        if(!u) return u=++tot,val[u]=w,siz[u]=1,spa[u]=ls=rs=0,u;
        if(val[u]==w) return u;
        int ret=w>val[u]?insert(w,rs):insert(w,ls);
        if(!legal(ls)) rebuild(ls);
        if(!legal(rs)) rebuild(rs);
        pushup(u);
        return ret;
    }
}

signed main(){
    for(int i=1;i<=30000;++i) tree::insert(i);
    return 0;
}

//~kawaii~