BZOJ4756 Promotion Counting（线段树合并）

题目描述

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

Input

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

Output

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

Sample Input

5
804289384
846930887
681692778
714636916
957747794
1
1
2
3
1
2
3
4
5
6
7
8
9
10

Sample Output

2
0
1
0
0
1
2
3
4
5

$1\le N\le 10^5$

题目大意

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

题解

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

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

注：要离散化

code

#include
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79