C# · 12月 20, 2021

普及线段树合并

我之前考试是遇到过这题,但是数据范围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'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]]<dep[tp[b]])swap(a,b);

a=fa[tp[a]];

}

return dep[a]<dep[b]?a:b;

}

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<b.z;

}

int to[N];

int main()

{

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

for(int f,i=1;i<n;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级数组即可。