【WC2014】紫荆花之恋

Author Avatar
mrsrz 9月 11, 2020

点分树重构，平衡树

题目大意：

给定一棵树，初始没有结点，每次加入一个结点，带点权 $r_i$ 以及边权。

每次加上一个点后，求满足 $i\lt j$ 且 $\mathrm{dist(i,j)}\leq r_i+r_j$ 的点对 $(i,j)$ 的数量。

强制在线。

题解：

考虑此题的离线做法。

先考虑只询问一次的做法。一种容易想到的做法是对树进行点分治，令 $d_i$ 表示 $i$ 到当前分治中心的距离，则我们要求 $d_i+d_j\leq r_i+r_j$，相当于 $d_i-r_i\leq r_j-d_j$。那么我们对每个结点，可以二分得到它的贡献。

考虑动态加入的情况。我们可以先建出这棵树的点分树，插入的时候对它所在的每个连通块（不超过 $\log n$ 个）都考虑贡献。由于是动态插入的过程，所以我们用平衡树来维护每个连通块的信息。查询时在平衡树上二分即可。注意减去自己子树里的贡献。时间复杂度 $O(n\log^2 n)$，空间复杂度 $O(n\log n)$。

现在加上了强制在线，不能直接建出点分树了。

我们考虑将替罪羊树上使用的重构思想，用在点分树上。即当一个连通块的某个子树大小非常不平衡的时候，对这整个连通块重新做一遍点分治，同时重新得到每个连通块的信息。这样就能够保证均摊复杂度正确了。

由于重构操作比较慢，所以平衡因子可以取得大一点，如 $0.9$。

点分树重构的总复杂度是 $O(n\log n)$ 的，因此最终的复杂度为 $O(n\log^3 n)$。

由于重构操作会对平衡树上的信息产生非常多的修改，所以平衡树部分的效率要高，且需要使用内存回收来防止泄露。

我使用了带旋的 treap 实现，用了很多的 vector，导致效率并不是很高。

Code：

#include<iostream>
#include<random>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
typedef long long LL;
// ------------------------------ Treap begin ------------------------------
mt19937 mt(size_t(new unsigned));
struct node{
    unsigned rd;
    int ch[2],sz;LL val;
    inline void clear(){sz=val=ch[0]=ch[1]=0;}
}d[6000002];
struct MemoryPool{
    int sta[6000002],top=0;
    MemoryPool(){
        for(int i=1;i<=6000000;++i)sta[i]=i,d[i].rd=mt();
        top=6000000;
    }
    inline int new_id(LL v){int x=sta[top--];d[x].sz=1,d[x].val=v;return x;}
    inline void recycle(int x){d[x].clear(),sta[++top]=x;}
}P;
inline void update(int x){d[x].sz=d[d[x].ch[0]].sz+d[d[x].ch[1]].sz+1;}
void rotate(int&x,bool c){
    int k=d[x].ch[c];
    d[x].ch[c]=d[k].ch[!c];
    d[k].ch[!c]=x;
    update(x),update(x=k);
}
void insert(int&x,int y){
    if(!x)x=y;else{
        const bool c=d[x].val<=d[y].val;
        insert(d[x].ch[c],y);
        if(d[x].rd<d[d[x].ch[c]].rd)rotate(x,c);
        else update(x);
    }
}
int getrk(int u,LL k){
    int res=0;
    while(u)
    if(d[u].val<=k)res+=d[d[u].ch[0]].sz+1,u=d[u].ch[1];
    else u=d[u].ch[0];
    return res;
}
void dispose(int x){
    if(!x)return;
    dispose(d[x].ch[0]),dispose(d[x].ch[1]);
    P.recycle(x);
}
// ------------------------------ Treap end ------------------------------
LL ans;
struct edge{
    int to,nxt,w;
}e[N<<1];
int head[N],cnt,n,V[N];
inline void addedge(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
}
struct info{
    int id,fa,zx;LL dis;
    inline bool operator<(const info&rhs)const{return id<rhs.id;}
};
struct structure{
    int _rt,fa;
    vector<int>son,_rts;
    vector<info>ns;
    void reset(){
        fa=0,ns.clear();
        dispose(_rt);
        for(int i:_rts)dispose(i);
        _rt=0,_rts.clear();
    }
    inline int find_id(int x){
        return lower_bound(ns.begin(),ns.end(),(info){x})-ns.begin();
    }
    inline info find_info(int x){
        return*lower_bound(ns.begin(),ns.end(),(info){x});
    }
}G[N];
bool vis[N];
int root,sz[N],mxd[N],all;
void getrt(int now,int pre){
    sz[now]=1,mxd[now]=0;
    for(int i=head[now];i;i=e[i].nxt)if(e[i].to!=pre&&vis[e[i].to]){
        getrt(e[i].to,now);
        sz[now]+=sz[e[i].to];
        mxd[now]=max(mxd[now],sz[e[i].to]);
    }
    mxd[now]=max(mxd[now],all-sz[now]);
    if(!root||mxd[now]<mxd[root])root=now;
}
void dfs(int now,int pre,LL d,const int&zx){
    G[root].ns.push_back((info){now,pre,zx,d});
    insert(G[root]._rts.back(),P.new_id(d-V[now]));
    insert(G[root]._rt,P.new_id(d-V[now]));
    for(int i=head[now];i;i=e[i].nxt)if(vis[e[i].to]&&e[i].to!=pre)
    dfs(e[i].to,now,d+e[i].w,zx);
}
void DFS(int now,int pre,vector<int>&vc){
    vc.push_back(now);
    for(int i=head[now];i;i=e[i].nxt)if(vis[e[i].to]&&e[i].to!=pre)DFS(e[i].to,now,vc);
}
void rebuild(int x,vector<int>&vc){
    for(int i:vc)vis[i]=1;
    all=vc.size();
    root=0;getrt(vc[0],0);
    G[root].fa=x;
    G[root].ns.push_back((info){root,0,0,0});
    insert(G[root]._rt,P.new_id(-V[root]));
    int tt=0,it=0;
    for(int i=head[root];i;i=e[i].nxt)if(vis[e[i].to]){
        ++tt;
        G[root]._rts.push_back(0);
        dfs(e[i].to,root,e[i].w,(int)G[root]._rts.size()-1);
    }
    sort(G[root].ns.begin(),G[root].ns.end());
    vector<vector<int> >VEC(tt);
    for(int i=head[root];i;i=e[i].nxt)if(vis[e[i].to])DFS(e[i].to,root,VEC[it++]);
    for(int i:vc)vis[i]=0;
    int rt=root;
    for(auto&it:VEC)rebuild(rt,it);
}
void insert_(int id,int fa,int vt,int et){
    G[id].fa=fa;
    G[id]._rt=P.new_id(-vt);
    G[id].ns.push_back((info){id,0,0,0});
    int re_id=0;
    for(int x=fa;x;x=G[x].fa){
        const info&F=G[x].find_info(fa);
        LL d=F.dis+et;
        insert(G[x]._rt,P.new_id(d-vt));
        info nw=(info){id,fa,(x==fa?(int)G[x]._rts.size():F.zx),d};
        if(x==fa){
            G[x]._rts.push_back(P.new_id(d-vt));
        }else insert(G[x]._rts[nw.zx],P.new_id(d-vt));
        G[x].ns.push_back(nw);
        ans+=getrk(G[x]._rt,vt-d)-getrk(G[x]._rts[nw.zx],vt-d);
        if(::d[G[x]._rts[nw.zx]].sz*100>=(int)G[x].ns.size()*91)
        re_id=x;
    }
    if(re_id){
        vector<int>vc;
        int f=G[re_id].fa;
        for(info&x:G[re_id].ns)vc.push_back(x.id);
        for(int i:vc)G[i].reset();
        rebuild(f,vc);
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>n;
    int v;
    cin>>v>>v>>v;
    V[1]=v;
    G[1]._rt=P.new_id(-v);
    cout<<"0\n";
    G[1].ns.push_back((info){1,0,0,0});
    for(int i=2;i<=n;++i){
        int f,w,t;
        cin>>f>>w>>t;
        V[i]=t;
        f^=ans%1000000000;
        addedge(i,f,w);
        insert_(i,f,t,w);
        cout<<ans<<'\n';
    }
    return 0;
}
Powered by Hexo
Theme - Material