Loading...

[USACO17JAN]Promotion Counting晋升者计数

check评论:0 条 remove_red_eye浏览量:62 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-05

原题链接

  • 题目描述
给定一棵带权树,求每个点的子树中分别有多少个比他权值大的节点
  • 题目分析

权值比较,自然想到了权值线段树,然后可以采用线段树合并,就可以了快速合并答案了

具体的合并方法,我们先看是不是两个节点都存在,如果只有一个存在就返回另一个,否则就新建节点,储存两个点的信息,同时更新左右儿子即可

  • 代码实现
/*deco loves Chino*/
#include <bits/stdc++.h>
using namespace std;
int rt[100010],val[100010],ans[100010],cnt=1,n,sum[2000010];
int ls[2000010],rs[2000010],tv[100010],tot;
vector<int> vc[100010];
int modify(int &o,int lf,int rg,int w)
{
    if(!o)
    {
        o=++cnt;
    }
    sum[o]++;
    if(lf==rg)
    {
        return 0;
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        modify(ls[o],lf,mid,w);
    }
    if(mid<w)
    {
        modify(rs[o],mid+1,rg,w);
    }
}
int merge(int x,int y)
{
    if(!x)
    {
        return y;
    }
    if(!y)
    {
        return x;
    }
    int t=++cnt;
    sum[t]=sum[x]+sum[y];
    ls[t]=merge(ls[x],ls[y]);
    rs[t]=merge(rs[x],rs[y]);
    return t; 
}
int query(int o,int lf,int rg,int w)
{
    if(!o)
    {
        return 0;
    }
    if(lf>=w)
    {
        return sum[o];
    }
    int mid=(lf+rg)>>1;
    if(w<=mid)
    {
        return query(ls[o],lf,mid,w)+query(rs[o],mid+1,rg,w);
    }
    if(mid<w)
    {
        return query(rs[o],mid+1,rg,w);
    }
}
void dfs(int u)
{
    for(int i=0;i<vc[u].size();i++)
    {
        int v=vc[u][i];
        dfs(v);
        rt[u]=merge(rt[u],rt[v]);
    }
    ans[u]=query(rt[u],1,tot,val[u]+1);
    modify(rt[u],1,tot,val[u]);
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        tv[i]=val[i];
    }
    sort(tv+1,tv+n+1);
    int m=unique(tv+1,tv+n+1)-tv-1;
    for(int i=1;i<=n;i++)
    {
        val[i]=lower_bound(tv+1,tv+m+1,val[i])-tv;
    }
    for(int i=2;i<=n;i++)
    {
        int fa;
        scanf("%d",&fa);
        vc[fa].push_back(i);
    }
    tot=m;
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        cout<<ans[i]<<"\n";
    }
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名