基本思路
线段树合并其实就是简单的暴力合并就可以了。一般是运用于权值线段树。通常是在每个节点都需要要一颗线段树才能维护答案,且有多个节点时,会使用线段树合并。但每个节点所有的权值不能太多,如果都是比较满的二叉树的话,时间复杂度就会很高。
通常,加入值的数量跟节点数量在同一级别的话,时间复杂度是\(O(n\log n)\) 级别的(但其实我不是很确定)。
具体代码
其实代码理解了之后就是非常简单的了。
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N=200011;
struct node{
int to,lt;
}e[N<<1];
int last[N],tot;
void add(int u,int v){//连边
e[++tot].lt=last[u];
e[tot].to=v;
last[u]=tot;
return ;
}
int dep[N],son[N],size[N],fa[N];
void dfs1(int u,int fat){//树剖求lca
dep[u]=dep[fat]+1;size[u]=1;fa[u]=fat;
for(int i=last[u];i;i=e[i].lt){
int v=e[i].to;
if(v==fat)continue;
dfs1(v,u);
size[u]+=size[v];
if(size[son[u]]<size[v])son[u]=v;
}
}
int top[N];
void dfs2(int u,int top_u){
top[u]=top_u;
if(son[u])dfs2(son[u],top_u);
for(int i=last[u];i;i=e[i].lt){
int v=e[i].to;
if(!top[v])dfs2(v,v);
}
}
int root[N];
int lca(int a,int b){
while(top[a]!=top[b]){
if(dep[top[a]]<dep[top[b]])swap(a,b);
a=fa[top[a]];//树剖这里记得是fa
}
if(dep[a]>dep[b])swap(a,b);
return a;
}
struct tree{
int lc,rc,date,maxid;
}t[N*30];
int cnt;
void update(int x){//更新节点
if(t[t[x].lc].date>=t[t[x].rc].date)t[x].maxid=t[t[x].lc].maxid;
else t[x].maxid=t[t[x].rc].maxid;
t[x].date=max(t[t[x].lc].date,t[t[x].rc].date);
return ;
}
void change(int &x,int l,int r,int k,int val){//修改 更新某个节点上权值线段树的值
if(!x)x=++cnt;//动态开点,没有就建立一个新的节点
if(l==r){
t[x].date+=val;
t[x].maxid=l;
return ;
}
int mid=(l+r)>>1;
if(k<=mid)change(t[x].lc,l,mid,k,val);
else change(t[x].rc,mid+1,r,k,val);
update(x);return ;
}
int merge(int a,int b,int l,int r){
if(!a)return b;if(!b)return a;//如果一个没有就返回另一个
if(l==r){
t[a].date+=t[b].date;
t[a].maxid=l;
return a;
}
int mid=(l+r)>>1;
t[a].lc=merge(t[a].lc,t[b].lc,l,mid);//由合并方式可以看出,如果每颗权值线段树都很满的话
t[a].rc=merge(t[a].rc,t[b].rc,mid+1,r);//时间复杂度是会很高的
update(a);
return a;
}
int ans[N];
#define maxn 100000
void work(int u){//从下往上合并线段树
for(int i=last[u];i;i=e[i].lt){
int v=e[i].to;
if(v==fa[u])continue;
work(v);
root[u]=merge(root[u],root[v],1,maxn);
}
if(t[root[u]].date)ans[u]=t[root[u]].maxid;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs1(1,0);dfs2(1,1);
for(int i=1;i<=m;i++){
int x,y,z,u;
cin>>x>>y>>z;
u=lca(x,y);
//运用树上差分的思想
change(root[x],1,maxn,z,1);change(root[y],1,maxn,z,1);
change(root[u],1,maxn,z,-1);change(root[fa[u]],1,maxn,z,-1);
}
//cout<<endl;
work(1);
for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
return 0;
}
标签:maxid,lc,int,线段,合并,笔记,date,root
From: https://www.cnblogs.com/shadom/p/17614403.html