P6329 震波 题解
题面
动态点分治模板题。考虑建出点分树来之后，在每个点开两棵动态开点线段树，以距离为下标，\(t1\) 记录的是 \(u\) 连通块内到 \(u\) 所有距离为 \(i\) 的点的权值和，\(t2\) 记录的是 \(u\) 连通块内到点分树上 \(u\) 的父亲 \(fa_u\) 所有距离为 \(i\) 的点的权值和。
每次查询的时候，从 \(x\) 开始暴力在点分树上跳，跳到 \(u\) 的时候，加上 \(t1\) 中 \(0\sim k-dist(x,u)\)，再减去 \(u\) 的儿子 \(v\) 的第二棵线段树里的，这样就不会算错。修改的时候也是差不多这样。复杂度 \(O((n+m)\log^2 n)\)。
点击查看代码
const int N=1e5+13,logN=21;
struct Edge{int v,nxt;}e[N<<1];
int n,m,a[N],h[N],etot;
int siz[N],maxx[N],rt,psum,fa[N],dep[N],rtd[N],rtch[N],dis[N][logN];
bool vis[N];
inline void add_edge(int u,int v){e[++etot]=(Edge){v,h[u]};h[u]=etot;}
namespace Tree{
int fa[N],dep[N],siz[N],son[N],top[N];
void dfs1(int u,int f,int deep){
dep[u]=deep,siz[u]=1,fa[u]=f;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f) continue;
dfs1(v,u,deep+1);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
}
}
void dfs2(int u,int topf){
top[u]=topf;
if(!son[u]) return;
dfs2(son[u],topf);
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;
if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
}
}
inline void init(){dfs1(1,0,0);dfs2(1,1);}
inline int lca(int u,int v){
while(top[u]!=top[v]){
if(dep[top[u]]>1)
inline void refresh(int p){t[p].sum=t[ls].sum+t[rs].sum;}
void update(int &p,int l,int r,int x,int k){
if(!p) p=++ptot;
if(l==r) return t[p].sum+=k,void();
x<=mid?update(ls,l,mid,x,k):update(rs,mid+1,r,x,k);
refresh(p);
}
int query(int p,int l,int r,int L,int R){
if(!p) return 0;
if(L<=l&&r<=R) return t[p].sum;
if(R<=mid) return query(ls,l,mid,L,R);
if(L>mid) return query(rs,mid+1,r,L,R);
return query(ls,l,mid,L,R)+query(rs,mid+1,r,L,R);
}
#undef ls
#undef rs
#undef mid
void findrt(int u,int f){
siz[u]=1,maxx[u]=0;
for(int i=h[u];i;i=e[i].nxt){
int v=e[i].v;if(v==f||vis[v]) continue;
findrt(v,u);
siz[u]+=siz[v];
maxx[u]=max(maxx[u],siz[v]);
}
maxx[u]=max(maxx[u],psum-siz[u]);
if(maxx[u]y) continue;
ans+=query(rtch[fa[u]],0,n,0,y-tmp)-query(rtd[u],0,n,0,y-tmp);
}
println(lastans=ans);
}
else{
int delta=y-a[x];
update(rtch[x],0,n,0,delta);
for(int u=x;fa[u];u=fa[u]){
int tmp=dis[x][dep[x]-dep[fa[u]]];
update(rtch[fa[u]],0,n,tmp,delta),update(rtd[u],0,n,tmp,delta);
}
a[x]=y;
}
}
return 0;
}