问题描述:

$n$只奶牛构成了一个树形的公司,每个奶牛有一个能力值$p_i$,$1$号奶牛为树根。问对于每个奶牛来说,它的子树中有几个能力值比它大的。

输入:

第一行一个整数$n$,表示有$n$头奶牛
接下来$n$行为$1-n$号奶牛的能力值$p_i$
接下来$n-1$行为$2-n$号奶牛的经理(树中的父亲)

输出:

共$n$行,每行输出奶牛$i$的下属中有几个能力值比$i$大

思路:

其实看完题后第一反应是树上启发式合并(不过应该可做,这种方法先坑着)。既然这是线段树合并的模版,那么还是先用这种方法做一遍吧。

首先离散化,然后对于每一个节点都建一颗权值线段树(里面都只有一个节点),接着dfs一遍,将每个节点儿子的线段树并在该节点上,然后跟新这个节点的答案就好了。

不过合并的操作复杂度是取决于线段树重合部分的大小,空间也要开很多倍。

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define MAXN 100005
using namespace std;

int n, m, cnt, tot, a[MAXN], b[MAXN], head[MAXN], root[MAXN], ans[MAXN];

struct Node {int size, ls, rs;} t[MAXN*20];
struct Edge {int next, to;} edge[MAXN*2];

void addedge(int from, int to)
{
    edge[++cnt].next=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void up(int root)
{
    t[root].size=t[t[root].ls].size+t[t[root].rs].size;
}

void insert(int &root, int l, int r, int x)
{
    root= ++tot;
    if(l==r) {t[root].size=1; return;}
    int mid=(l+r)>>1;
    if (x<=mid) insert(t[root].ls, l, mid, x);
    else insert(t[root].rs, mid+1, r, x);
    up(root);
}

int merge(int x, int y)
{
    if((!x) || (!y)) return x+y;
    t[x].ls=merge(t[x].ls, t[y].ls);
    t[x].rs=merge(t[x].rs, t[y].rs);
    up(x);
    return x;
}

int query(int root, int l, int r, int x, int y)
{
    if(r<x || l>y) return 0;
    if(l>=x && r<=y) return t[root].size;
    int mid=(l+r)>>1;
    return query(t[root].ls, l, mid, x, y)+query(t[root].rs, mid+1, r, x, y);
}

void dfs(int x)
{
    for(int i=head[x]; i; i=edge[i].next)
    {
        int to=edge[i].to;
        dfs(to);
        root[x]=merge(root[x], root[to]);
    }
    ans[x]=query(root[x], 1, n, a[x]+1, tot);
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &a[i]), b[i]=a[i];
    sort(b+1, b+n+1);
    m=unique(b+1, b+n+1)-b-1;
    for(int i=1; i<=n; i++) a[i]=lower_bound(b+1, b+m+1, a[i])-b;
    for(int i=2; i<=n; i++)
    {
        int x;
        scanf("%d", &x);
        addedge(x, i);
    }
    for(int i=1; i<=n; i++) insert(root[i], 1, n, a[i]);
    dfs(1);
    for(int i=1; i<=n; i++) printf("%d\n", ans[i]);
}

发表评论

邮箱地址不会被公开。 必填项已用*标注