P3920 [WC2014] 紫荊花之戀

sol

首先如果不帶修的話就是點分治板子，帶修的話就是動態點分樹板子。

由于寫過一篇動態點分樹的博客，這里就對動態點分樹部分不詳細講解了，主要講一下信息維護吧。不會的話可以點進去先看一下。

理論上來說，應當使用平衡樹，可以使得全局復雜度為 \(O(n\log^3n)\)，但平衡樹又難寫常數又大，因此考慮根號數據結構。

式子推一下就是一維偏序條件，那么這個數據結構必須實現插入并查詢排名的功能。考慮大小鏈，大鏈有序，小鏈無序，每次大鏈二分小鏈遍歷。如果小鏈大小超過閾值直接和大鏈歸并排序即可，閾值設做 \(\sqrt n\) 可以做到 \(O(n\sqrt n)\) 的復雜度。整體復雜度是 \(O(n\sqrt n\log^2 n)\)，實際上跑得特別快。

然后就沒什么了，就是個動態點分樹板子。

code

const int N=1e5+5,V=1e9,B=320;
const flt A=0.8;

int n;
struct sq{
    vec<ll> big,sml,t;
    inline void ins(ll x){
        sml.pub(x);
        if(sml.size()>B){
            int a=0,b=0;
            t.clear();
            sort(sml.begin(),sml.end());
            while(a<big.size()&&b<sml.size())t.pub(big[a]<sml[b]?big[a++]:sml[b++]);
            while(a<big.size())t.pub(big[a++]);
            while(b<sml.size())t.pub(sml[b++]);
            sml.clear();big=t;
        }
    }
    inline ll query(ll v){
        int res=upper_bound(big.begin(),big.end(),v)-big.begin();
        for(auto i:sml)if(i<=v)++res;
        return res;
    }
    inline void clear(){
        big.clear(),sml.clear();
    }
}dat[N],daf[N];

int Fa[N];
vec<pil> g[N];
ll r[N];
vec<int> son[N],grd[N],grl[N];

bool don[N];

int siz,sz[N];
void gsiz(int x,int f){
    sz[x]=1;
    for(auto e:g[x]){
        int y=e.fir;
        if(!don[y]&&y!=f)gsiz(y,x),sz[x]+=sz[y];
    }
}
int rot,mx[N];
void grot(int x,int f){
    mx[x]=siz-sz[x];
    for(auto e:g[x]){
        int y=e.fir;
        if(!don[y]&&y!=f)grot(y,x),chmax(mx[x],sz[y]);
    }
    if(mx[x]<mx[rot])rot=x;
}
void dfs(int x,int f,int z,int dp){
    dat[z].ins(dp-r[x]);if(Fa[z])daf[z].ins(grl[x].back()-r[x]);
    grd[x].pub(z),grl[x].pub(dp);son[z].pub(x);
    for(auto e:g[x]){
        int y=e.fir;
        if(!don[y]&&y!=f)dfs(y,x,z,dp+e.sec);
    }
}
void calc(int x,int fa){
    gsiz(x,x);siz=sz[x];
    mx[rot=0]=inf;grot(x,x);
    x=rot;Fa[x]=fa;
    for(auto e:g[x]){
        int y=e.fir;
        if(!don[y])dfs(y,x,x,e.sec);
    }
    dat[x].ins(-r[x]);
    if(fa)daf[x].ins(grl[x].back()-r[x]);
    don[x]=1;
    for(auto e:g[x]){
        int y=e.fir;
        if(!don[y])calc(y,x);
    }
}

inline void Main(){
    int T;cin>>T>>n;
    ll ans=0;
    rep(i,1,n){
        int a,c;cin>>a>>c>>r[i];
        a^=ans%V;
        if(!a){
            dat[1].ins(-r[i]);
        }else{
            g[a].pub({i,c}),g[i].pub({a,c});
            Fa[i]=a;
            grd[i]=grd[a],grl[i]=grl[a];
            grd[i].pub(a),grl[i].pub(0);
            for(auto &j:grl[i])j+=c;
            repl(j,0,grd[i].size()){
                int x=grd[i][j];
                ans+=dat[x].query(r[i]-grl[i][j]);
                if(j)ans-=daf[x].query(r[i]-grl[i][j-1]);
                son[x].pub(i);
                dat[x].ins(grl[i][j]-r[i]);
                if(j)daf[x].ins(grl[i][j-1]-r[i]);
            }
            dat[i].ins(-r[i]);
            daf[i].ins(c-r[i]);
            repl(j,1,grd[i].size())if(son[grd[i][j-1]].size()*A<son[grd[i][j]].size()){
                int x=grd[i][j-1],f=Fa[x];
                don[f]=1;
                for(auto y:son[x]){
                    while(1){
                        int t=grd[y].back();
                        grd[y].pob(),grl[y].pob();
                        if(t==x)break;
                    }
                    son[y].clear();don[y]=0;
                    dat[y].clear(),daf[y].clear();
                }
                son[x].clear();don[x]=0;
                dat[x].clear(),daf[x].clear();
                calc(x,f);
                break;
            }
        }
        put(ans);
    }
}