当前位置：首页 > news >正文

BZOJ4756 Promotion Counting（线段树合并）

news 来源：原创 2024/5/17 18:29:24

题目描述

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

Input

第一行包含整数 $n$ ，表示有几只奶牛，接下来 $n$ 个数，表示 $1 - n$ 号奶牛的能力值 $p_i$ ，接下来 $n - 1$ 行为 $2 - n$ 号奶牛的经理（树中的父亲）。

Output

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

Sample Input

Sample Output

$1\leq N\leq 10^5$

题目大意

有 $n$ 个点，每个点有一个权值 $p_i$ 。对于每个点，求它的子树中有几个点权值比它大。

题解

这道题要用到线段树合并，是一道比较模板的题。

给每一个点都开一个权值线段树，存储各个能力值有多少个点。 $D FS$ 遍历全图，把儿子的线段树合并到自己身上，查询能力值比自己大的有多少个即可。

注：要离散化

code

#include<bits/stdc++.h>
using namespace std;
int n,x,tot=0,sum,d[100005],l[100005],r[100005],rt[100005],ans[100005];
long long a[100005],num[100005];
struct node{
    int lc,rc,s;
}tr[5000005];
void add(int xx,int yy){
    l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void pt(int &k,int l,int r,int v){
    if(!k) k=++tot;
    if(l==r){
        tr[k].s=1;return;
    }
    int mid=(l+r)/2;
    if(v<=mid) pt(tr[k].lc,l,mid,v);
    else pt(tr[k].rc,mid+1,r,v);
    tr[k].s=tr[tr[k].lc].s+tr[tr[k].rc].s;
}
void find(int k,int l,int r,int x,int y){
    if(!k) return;
    if(l>=x&&r<=y){
        sum+=tr[k].s;return;
    }
    if(l>y||r<x) return;
    if(l==r) return;
    int mid=(l+r)/2;
    if(x<=mid) find(tr[k].lc,l,mid,x,y);
    if(y>mid) find(tr[k].rc,mid+1,r,x,y);
}
void merge(int &r1,int r2,int l,int r){
    if(!r1||!r2){
        r1=r1+r2;return;
    }
    if(l==r){
        tr[r1].s+=tr[r2].s;return;
    }
    int mid=(l+r)/2;
    merge(tr[r1].lc,tr[r2].lc,l,mid);
    merge(tr[r1].rc,tr[r2].rc,mid+1,r);
    tr[r1].s=tr[tr[r1].lc].s+tr[tr[r1].rc].s;
}
int dfs(int u){
    int siz=1;
    for(int i=r[u];i;i=l[i]){
        siz+=dfs(d[i]);
        merge(rt[u],rt[d[i]],1,n);
    }
    sum=0;
    find(rt[u],1,n,1,a[u]);
    ans[u]=siz-sum;
    return siz;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);num[i]=a[i];
    }
    sort(num+1,num+n+1);
    int gs=unique(num+1,num+n+1)-num-1;
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(num+1,num+gs+1,a[i])-num;
    }
    for(int i=2;i<=n;i++){
        scanf("%d",&x);
        add(x,i);
    }
    tot=0;
    for(int i=1;i<=n;i++){
        pt(rt[i],1,n,a[i]);
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}