普及线段树合并

概述本文章向大家介绍普及线段树合并，需要的朋友可以参考一下

我之前考试是遇到过这题，但是数据范围k<=20，状压就能过。

结果原题范围k<=100000……

果断线段树合并。

普及线段树合并：

比如两个相同大小的线段树,将b树各个区间上的值合并到a树上，从树根开始合并，然后递归合并左右儿子，有三种情况：

（假设现在a树遍历到x点，b树遍历到y点）

1.x，y至少其一未被修改过（语文不好勿喷），则将x变为遍历过的那个。

2.x，y位于叶节点（l==r），则sum[x]+=sum[y]。

3.一般情况，递归处理左右儿子，最后更新当前点。

本题中合并如下：

voID merge(int &a,int b,int l,int r)

{

if(!b)return ;

if(!a){a=b;return ;}

//1

if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}//注意维护

//2

int mID = (l+r)>>1;

merge(ls[a],ls[b],l,mID);//递归左子树

merge(rs[a],rs[b],mID+1,r);//递归右子树

update(a);

//3

}

juruo代码奉上：

#include

#include

using namespace std;

#define N 100105

inline int rd()

{

int f=1,c=0;char ch = getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){c=10*c+ch-'0';ch=getchar();}

return f*c;

}

int n,m,hed[N],cnt;

struct eg

{

int to;

int nxt;

}e[2*N];

voID ae(int f,int t)

{

e[++cnt].to = t;

e[cnt].nxt = hed[f];

hed[f] = cnt;

}

int dep[N],fa[N],son[N],tp[N],siz[N];

voID dfs1(int u)

{

dep[u]=dep[fa[u]]+1;

siz[u]=1;

for(int j=hed[u];j;j=e[j].nxt)

{

int to = e[j].to;

if(to==fa[u])continue;

fa[to]=u;

dfs1(to);

siz[u]+=siz[to];

if(siz[to]>siz[son[u]])son[u]=to;

}

}

voID dfs2(int u,int topn)

{

tp[u]=topn;

if(!son[u])return ;

dfs2(son[u],topn);

for(int j=hed[u];j;j=e[j].nxt)

{

int to = e[j].to;

if(to==fa[u]||to==son[u])continue;

dfs2(to,to);

}

}

int get_lca(int a,int b)

{

while(tp[a]!=tp[b])

{

if(dep[tp[a]]

a=fa[tp[a]];

}

return dep[a]

}

int rt[N],sum[70*N],sn[70*N],ls[70*N],rs[70*N],tot;

voID update(int u)

{

sn[u]=sum[ls[u]]>=sum[rs[u]]?sn[ls[u]]:sn[rs[u]];

sum[u]=sum[ls[u]]>=sum[rs[u]]?sum[ls[u]]:sum[rs[u]];

}

voID insert(int l,int r,int &u,int qx,int d)

{

if(!u)u=++tot;

if(l==r)

{

sum[u]+=d;

if(sum[u])sn[u]=l;

else sn[u]=0;

return ;

}

int mID = (l+r)>>1;

if(qx<=mID)insert(l,mID,ls[u],qx,d);

else insert(mID+1,r,rs[u],d);

update(u);

}

voID merge(int &a,int r)

{

if(!b)return ;

if(!a){a=b;return ;}

if(l==r){sum[a]+=sum[b];if(sum[a]==sum[b])sn[a]=l;return ;}

int mID = (l+r)>>1;

merge(ls[a],mID);

merge(rs[a],r);

update(a);

}

int ans[N];

voID dfs(int u)

{

for(int j=hed[u];j;j=e[j].nxt)

{

int to = e[j].to;

if(to==fa[u])continue;

dfs(to);

merge(rt[u],rt[to],1,m);

}

ans[u]=sn[rt[u]];

}

struct ND

{

int f,t,z;

}nd[N];

bool cmp(ND a,ND b)

{

return a.z

}

int to[N];

int main()

{

n=rd(),m=rd();

for(int f,i=1;i

{

f=rd(),t=rd();

ae(f,t),ae(t,f);

}

dfs1(1),dfs2(1,1);

for(int f,z,i=1;i<=m;i++)

{

f=rd(),t=rd(),z=rd();

nd[i].f=f,nd[i].t=t,nd[i].z=z;

}

sort(nd+1,nd+1+m,cmp);

int las=-1,k=0;

for(int f,lca,i=1;i<=m;i++)

{

if(nd[i].z!=las)

{

las=nd[i].z;

to[++k]=nd[i].z;

}

nd[i].z=k;

f = nd[i].f,t = nd[i].t,z = nd[i].z;

lca = get_lca(f,t);

insert(1,rt[f],1);

insert(1,rt[t],rt[lca],-1);

if(lca!=1)insert(1,rt[fa[lca]],-1);

}

dfs(1);

for(int i=1;i<=n;i++)

{

printf("%dn",to[ans[i]]);

}

return 0;

}

在这里提一下空间问题：

每进行一次插入，会添加log级的点，因此juruo认为开nlogn级数组即可。

总结

以上是内存溢出为你收集整理的普及线段树合并全部内容，希望文章能够帮你解决普及线段树合并所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。