欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[Vani有约会]雨天的尾巴

程序员文章站 2022-05-18 23:00:58
我之前考试是遇到过这题,但是数据范围k<=20,状压就能过。 结果原题范围k<=100000…… 果断线段树合并。 普及线段树合并: 比如两个相同大小的线段树,将b树各个区间上的值合并到a树上,从树根开始合并,然后递归合并左右儿子,有三种情况: (假设现在a树遍历到x点,b树遍历到y点) 1.x,y ......

我之前考试是遇到过这题,但是数据范围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<cstdio>
#include<algorithm>
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]]<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],qx,d);
    update(u);
}
void merge(int &a,int b,int l,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],ls[b],l,mid);
    merge(rs[a],rs[b],mid+1,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,t,i=1;i<n;i++)
    {
        f=rd(),t=rd();
        ae(f,t),ae(t,f);
    }
    dfs1(1),dfs2(1,1);
    for(int f,t,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,t,z,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,m,rt[f],z,1);
        insert(1,m,rt[t],z,1);
        insert(1,m,rt[lca],z,-1);
        if(lca!=1)insert(1,m,rt[fa[lca]],z,-1);
    }
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d\n",to[ans[i]]);
    }
    return 0;
}

在这里提一下空间问题:

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