P3920 [WC2014]紫荆花之恋（动态点分树）

· · 题解

45 行 1.7KB 紫荆花之恋了解一下~

总时间不到 20s，暂时是洛谷最优解。

树上路径询问，带修，和距离有关，果断想到点分树。

把题目中的式子移项，就是 dis(i,l)-r_i\leq r_j-dis(j,l)，其中 l 是 i,j 在点分树上的 lca。

用平衡树维护，每新增一个点 i 时，先对 i 的所有点分树上的祖先 l，查询 r_i-dis(i,l) 的排名，然后向平衡树插入 dis(i,l)-r_i。

因为在 fa_l 的平衡树中查询时 l 的子树会算重，所以要再开一个平衡树用来容斥，向其中插入 dis(i,fa_l)-r_i。

因为平衡树码量和常数都较大，所以这里用 basic_string/vector 和根号重构。具体做法是维护两个 basic_string 分别为 big 和 small，插入时直接向 small push_back。如果 small 的大小大于根号，就对 big 和 small 归并排序，然后放入 big 中。查询时在 big 中二分，然后在 small 中暴力枚举。这样的复杂度是 O(n\sqrt n)。

因为此题有加点操作，还要强制在线，所以要动态点分树。

具体做法是，加入一个点 i 和边 (i,j) 时先将 fa_i 设为 j。然后从根节点开始枚举 i 在点分树上的祖先，如果 sz_x>\alpha\times sz_{fa_x}，就对 fa_x 的子树重新建树，这里 fa 表示点分树上的父亲。\alpha 取 0.8 左右即可。这样可以保证点分树高为 \log n。

重新建树只需要对整棵树点分治一遍即可。

一些实现细节：

对每个点 i 开两个 basic_string f 和 d，分别表示祖先 j 和 dis(i,j)。

再开一个 basic_string g，表示 i 的点分树子树中的结点。

重构子树 i 时，对于 g_i 中的每一个点 k，清空 k 的平衡树和 g_k，然后不断同时弹出 f_k 和 d_k 的末尾，直到 f_k 弹出点 i。这样 f_k 中就只剩下 i 子树以外的点了。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+3;
struct T{//根号重构 basic_string
    basic_string<int>b,s,t;
    void st(){sort(b.begin(),b.end());}
    int get(int x){
        if(s.size()>300)t.resize(s.size()+b.size()),sort(s.begin(),s.end()),merge(b.begin(),b.end(),s.begin(),s.end(),t.begin()),swap(b,t),s={};
        int w=upper_bound(b.begin(),b.end(),x)-b.begin();
        for(int i:s)w+=i<=x;
        return s+=-x,w;
    }
}u[N],v[N];
basic_string<int>f[N],d[N],g[N],h;
long long ans;
int m,o,r,he[N],len[N*2],to[N*2],ne[N*2],w[N],sz[N];
bool b[N];
void gr(int x,int y){//求重心
    int i=he[x],j,w=0;
    for(sz[x]=1;i;i=ne[i])if(b[j=to[i]]&&j!=y)gr(j,x),sz[x]+=sz[j],w=max(w,sz[j]);
    if((w=max(w,m-sz[x]))<=o)o=w,r=x;
}
void gd(int x,int y,int z){//求距离
    if(d[x].size())v[r].b+=d[x].back()-w[x];
    f[x]+=r,d[x]+=z,g[r]+=x,u[r].b+=z-w[x];
    for(int i=he[x],j;i;i=ne[i])if(b[j=to[i]]&&j!=y)gd(j,x,z+len[i]);
}
void wk(int x){//点分治
    int i=he[x],l=m,j;
    for(b[x]=0,gd(x,0,0),u[x].st(),v[x].st();i;i=ne[i])if(b[j=to[i]])o=m=sz[j]<sz[x]?sz[j]:l-sz[x],gr(j,0),wk(r);
}
int main(){
    int n,i,j,k,l,z,y,x,t=0;
    for(scanf("%*d%d%*d%*d%d",&n,w+1),f[1]+=1,g[1]+=1,d[1]+=0,u[1].s+=-w[1],i=2;printf("%lld\n",ans),i<=n;++i){
        scanf("%d%d%d",&j,&x,w+i),j^=ans%int(1e9),ne[++t]=he[i],to[t]=j,len[t]=x,he[i]=t,ne[++t]=he[j],to[t]=i,len[t]=x,he[j]=t,f[i]=f[j],d[i]=d[j];
        for(int&k:d[i])k+=x;
        for(f[i]+=i,d[i]+=0,l=f[i].size(),k=l-1;~k;--k)if(g[z=f[i][k]]+=i,ans+=u[z].get(w[i]-d[i][k]),k)ans-=v[z].get(w[i]-d[i][k-1]);//更新答案
        for(k=0;k<l-1;++k)if(g[z=f[i][k]].size()*.8<g[f[i][k+1]].size()){
            for(int o:h=g[z])for(u[o].b=u[o].s=v[o].b=v[o].s=g[o]={},b[o]=1;y=f[o].back(),f[o].pop_back(),d[o].pop_back(),y!=z;);//清空
            m=o=h.size(),gr(z,0),wk(r);
            break;
        }
    }
    return 0;
}