20200703 专题：线段树合并

总览：

动态开点线段树，像暴力的合并（然而不是 时间复杂度：$O(nlogn)$ 模板：

inline int merge(int x,int y,int l,int r){ if(!x||!y) return x|y; if(l==r){ //将y合并到x return x; } int mid=(l+r)>>1; tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid); tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r); pushup(x); return x; }

如果需要可持久化，可以动态开点

T1 P4556 [Vani有约会]雨天的尾巴 /【模板】线段树合并

思路： 差分 在 x,y 处加，lca(x,y),f(lca(x,y)) 处减 从叶子结点开始合并查询

代码：

#include <bits/stdc++.h> using namespace std; #define re register namespace IO { #define in Read() inline char ch() { static char buf[1 << 21], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } inline int in { int s = 0, f = 1; char x; for (x = getchar(); x < '0' || x > '9'; x = getchar()) if (x == '-') f = -1; for (; x >= '0' && x <= '9'; x = getchar()) s = (s << 1) + (s << 3) + (x & 15); return f == 1 ? s : -s; } } // namespace IO using namespace IO; const int A=4e5+5; const int K=1e5; int n,m; int head[A],tot_road; struct Road{ int nex,to; }road[2*A]; inline void edge(int x,int y){ road[++tot_road]={head[x],y};head[x]=tot_road; } int dep[A],f[A],top[A],son[A],sz[A]; inline void DFS1(int fa,int x){ f[x]=fa,dep[x]=dep[fa]+1,sz[x]=1; for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; DFS1(x,z); sz[x]+=sz[z]; if(sz[z]>sz[son[x]]) son[x]=z; } return; } inline void DFS2(int x){ if(son[x]){ top[son[x]]=top[x]; DFS2(son[x]); } for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(top[z]) continue; top[z]=z; DFS2(z); } return; } inline void tree_cut(){ DFS1(0,1); top[1]=1; DFS2(1); return; } inline int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=f[top[x]]; } return dep[x]<dep[y]?x:y; } int rt[A],tot; struct Tree{ int ls,rs,num,ans; }tr[20*A]; int res[A]; inline void pushup(int x){ if(tr[tr[x].ls].num<=0&&tr[tr[x].rs].num<=0) return; if(tr[tr[x].ls].num>=tr[tr[x].rs].num){ tr[x].num=tr[tr[x].ls].num; tr[x].ans=tr[tr[x].ls].ans; } else{ tr[x].num=tr[tr[x].rs].num; tr[x].ans=tr[tr[x].rs].ans; } return; } inline void add(int &x,int l,int r,int w,int val){ if(!x) x=++tot; if(l==r){ tr[x].num+=val; tr[x].ans=tr[x].num>0?l:0; return; } int mid=(l+r)>>1; if(w<=mid) add(tr[x].ls,l,mid,w,val); else add(tr[x].rs,mid+1,r,w,val); pushup(x); return; } inline int merge(int x,int y,int l,int r){ if(!x||!y) return x|y; if(l==r){ tr[x].num+=tr[y].num; tr[x].ans=tr[x].num>0?l:0; return x; } int mid=(l+r)>>1; tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid); tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r); pushup(x); return x; } inline void work(int fa,int x){ for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; work(x,z); rt[x]=merge(rt[x],rt[z],1,K); } res[x]=tr[rt[x]].ans; return; } signed main() { n=in,m=in; for(int i=1;i<n;i++){ int u=in,v=in; edge(u,v),edge(v,u); } tree_cut(); for(int i=1;i<=m;i++){ int u=in,v=in,w=in; add(rt[u],1,K,w,1); add(rt[v],1,K,w,1); add(rt[lca(u,v)],1,K,w,-1); add(rt[f[lca(u,v)]],1,K,w,-1); } work(0,1); for(int i=1;i<=n;i++) printf("%d\n",res[i]); return 0; }

T2 P1600 天天爱跑步

思路： 先将路径拆成 s 到 lca 和 lca 到 t 两部分 对于 s 到 lca： 对 i 有贡献，当且仅当 $$\begin{gathered} de{p}_s-de{p}_i=w_i \\ de{p}_i+w_i=de{p}_s \end{gathered}$$

对于 lca 到 t： 对 i 有贡献，当且仅当 $$\begin{gathered} de{p}_s-de{p}_{lca}+de{p}_i-de{p}_{lca}=w_i \\ de{p}_s-2\times de{p}_{lca}=w_i-de{p}_i \end{gathered}$$ 注意可能产生负数

线段树合并维护即可

代码：

#include <bits/stdc++.h> using namespace std; #define re register namespace IO { #define in Read() inline char ch() { static char buf[1 << 21], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++; } inline int in { int s = 0, f = 1; char x; for (x = getchar(); x < '0' || x > '9'; x = getchar()) if (x == '-') f = -1; for (; x >= '0' && x <= '9'; x = getchar()) s = (s << 1) + (s << 3) + (x & 15); return f == 1 ? s : -s; } } // namespace IO using namespace IO; const int A=3e5+5; const int K=3e5; int n,m; int head[A],tot_road; struct Road{ int nex,to; }road[2*A]; inline void edge(int x,int y){ road[++tot_road]={head[x],y};head[x]=tot_road; } int f[A],dep[A],sz[A],son[A],top[A]; inline void DFS1(int fa,int x){ f[x]=fa,dep[x]=dep[fa]+1,sz[x]=1; for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; DFS1(x,z); sz[x]+=sz[z]; if(sz[z]>sz[son[x]]) son[x]=z; } return; } inline void DFS2(int x){ if(son[x]){ top[son[x]]=top[x]; DFS2(son[x]); } for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(top[z]) continue; top[z]=z; DFS2(z); } return; } inline void tree_cut(){ DFS1(0,1); top[1]=1; DFS2(1); return; } inline int lca(int x,int y){ while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]]) swap(x,y); x=f[top[x]]; } return dep[x]<dep[y]?x:y; } int tim[A]; int rt[A],tot; struct Tree{ int ls,rs,s[2]; }tr[20*A]; int res[A]; inline void pushup(int x){ if(!tr[x].ls&&!tr[x].rs) return; tr[x].s[0]=tr[tr[x].ls].s[0]+tr[tr[x].rs].s[0]; tr[x].s[1]=tr[tr[x].ls].s[1]+tr[tr[x].rs].s[1]; return; } inline void add(int &x,int l,int r,int w,int val,int pos){ if(!x) x=++tot; if(l==r){ tr[x].s[pos]+=val; return; } int mid=(l+r)>>1; if(w<=mid) add(tr[x].ls,l,mid,w,val,pos); else add(tr[x].rs,mid+1,r,w,val,pos); pushup(x); return; } inline int merge(int x,int y,int l,int r){ if(!x||!y) return x|y; if(l==r){ tr[x].s[0]+=tr[y].s[0]; tr[x].s[1]+=tr[y].s[1]; return x; } int mid=(l+r)>>1; tr[x].ls=merge(tr[x].ls,tr[y].ls,l,mid); tr[x].rs=merge(tr[x].rs,tr[y].rs,mid+1,r); pushup(x); return x; } inline int qurey(int x,int l,int r,int w,int pos){ if(!x) return 0; if(l==r) return tr[x].s[pos]; int mid=(l+r)>>1; if(w<=mid) return qurey(tr[x].ls,l,mid,w,pos); else return qurey(tr[x].rs,mid+1,r,w,pos); } inline void work(int fa,int x){ for(int y=head[x];y;y=road[y].nex){ int z=road[y].to; if(z==fa) continue; work(x,z); rt[x]=merge(rt[x],rt[z],-K,K); } res[x]+=qurey(rt[x],-K,K,dep[x]+tim[x],0); res[x]+=qurey(rt[x],-K,K,tim[x]-dep[x],1); return; } signed main() { n=in,m=in; for(int i=1;i<n;i++){ int u=in,v=in; edge(u,v),edge(v,u); } tree_cut(); for(int i=1;i<=n;i++) tim[i]=in; for(int i=1;i<=m;i++){ int u=in,v=in; int k=lca(u,v); add(rt[u],-K,K,dep[u],1,0); add(rt[f[k]],-K,K,dep[u],-1,0); add(rt[v],-K,K,dep[u]-2*dep[k],1,1); add(rt[k],-K,K,dep[u]-2*dep[k],-1,1); } work(0,1); for(int i=1;i<=n;i++) printf("%d ",res[i]); return 0; }