【树状数组】洛谷 P3605 Promotion Counting P
2021-06-03 22:15:00 # ACM

—–

题链

–解法一

跑一边$dfs$序，按照权值大小对$n$个点从大到小排好遍历，对于第$i$个点只要求它子树的和就行；

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 1e18
#define MS 100009

LL n,m;
struct node{
	LL val,id;
}a[MS];
LL b[MS],tb;
LL dfn[MS];
LL sz[MS];
vector<LL > vc[MS];
LL p[MS];
queue<LL > Q;
LL ac[MS];
LL tot;

bool cmp(node t1,node t2){
	return t1.val > t2.val;
}

LL lowbit(LL x){
	return x&(-x);
}

void add(LL pos,LL val){
	for(;pos<=n;pos+=lowbit(pos)) p[pos] += val;
}

LL query(LL pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)) ans += p[pos];
	return ans;
}

void dfs(LL x){
	dfn[x] = ++tot;
	sz[x] = 1;
	for(auto &i:vc[x]){
		dfs(i);
		sz[x] += sz[i];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i].val;
		a[i].id = i;
		b[i] = a[i].val;
	}
	sort(b+1,b+n+1);
	tb = 1;
	for(int i=2;i<=n;i++){
		if(b[i] != b[i-1]) b[++tb] = b[i];
	}
	for(int i=1;i<=n;i++){
		a[i].val = lower_bound(b+1,b+tb+1,a[i].val) - b;
	}
	sort(a+1,a+n+1,cmp);
	
	for(int i=2;i<=n;i++){
		LL x;
		cin >> x;
		vc[x].push_back(i);
	}
	
	dfs(1);
	
	for(int i=1;i<=n;i++){
		node t = a[i];
		LL tl = dfn[t.id];
		LL tr = tl+sz[t.id]-1;
		LL ans = query(tr) - query(tl);
		ac[t.id] = ans;
		add(dfn[t.id],1);
	}
	
	for(int i=1;i<=n;i++){
		cout << ac[i] << "\n";
	}
	

	return 0;
}

–解法二

离散化+树状数组，$dfs$求解；

$dfs$时，每碰到一个点就将它的权值记录在树状数组中，此时会有一个问题，有两颗子树互不影响，记两颗子树的头节点为$t1,t2$，$dfs$时会先遍历第一颗子树，此时到第二颗时，显然第二颗也就是$t2$的答案应该与之前维护的权值无关，此时可以两眼一闭查一下树状数组中比$t2$大的个数，然后把$t2$的子节点全部遍历完后再查一次比$t2$大的个数，两次的差值就是$t2$的答案；

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
#include <bits/stdc++.h>
using namespace std;
#define ls rt<<1
#define rs rt<<1|1
#define LL long long
#define PI acos(-1.0)
#define eps 1e-8
#define Pair pair<double,double>
// notice
#define mod 998244353 
#define MAXN 1e18
#define MS 100009

LL n,m;
LL a[MS];
LL b[MS],tb;
vector<LL > vc[MS];
LL p[MS];
LL ac[MS];

LL lowbit(LL x){
	return x&(-x);
} 

void add(LL pos,LL val){
	for(;pos<=n;pos+=lowbit(pos)) p[pos] += val;
}

LL query(LL pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)) ans += p[pos];
	return ans;
}

void dfs(LL x){
	ac[x] = -(query(n) - query(a[x]));
	for(auto &i:vc[x]){
		dfs(i);
	}
	ac[x] += query(n) - query(a[x]);
	add(a[x],1);
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		b[i] = a[i];
	}
	sort(b+1,b+n+1);
	tb = 1;
	for(int i=2;i<=n;i++){
		if(b[i] != b[i-1]) b[++tb] = b[i];
	}
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(b+1,b+tb+1,a[i]) - b;
	}
	
	for(int i=2;i<=n;i++){
		LL x;
		cin >> x;
		vc[x].push_back(i);
	}
	
	dfs(1);
	
	for(int i=1;i<=n;i++){
		cout << ac[i] << "\n";
	}

	return 0;
}

Prev
2021-06-03 22:15:00 # ACM
Next