백준17422 지폐가 넘쳐흘러

작성일 | In

문제 링크

  • http://icpc.me/17422

문제 출처

  • 2019 선린 정올 4번

사용 알고리즘

  • DP

시간복잡도

  • \[O(Q log^2 N)\]

풀이

트리의 한 정점을 잡고 잡아당겨서 밑에 있는 어느 점까지의 가중치를 최대화하는 문제입니다.
트리의 지름을 구하면 된다는 강한 확신이 듭니다.

대회 당시에는 정점 분할을 한 다음에 트리의 지름을 구해서 65점을 긁었습니다.

dp[i] = i를 루트로 하는 서브트리에 대한 정답, mx[i] = i를 루트로 하는 서브트리에서 i와 가장 멀리 떨어져있는 리프노드
로 정의합시다.
문제에서 주어지는 트리는 깊이가 \(O(log N)\)입니다. 그러므로 어떤 노드가 갱신되면 그 갱신이 영향을 끼치는 원소의 개수는 \(O(log N)\)개입니다.

map으로 관리해주면 \(O(Q log^2 N)\)에 정답을 구할 수 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n, q;
ll w[606060];
ll dp[606060];
map<ll, ll> mp;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> w[i];

	for(int i=n; i>=1; i--){
		dp[i] = max(dp[i << 1], dp[i << 1 | 1]) + w[i];
		mp[dp[i << 1] + dp[i << 1 | 1] + w[i]]++;
	}
	cout << prev(mp.end())->first << "\n";

	cin >> q;
	while(q--){
		ll x, v; cin >> x >> v;
		ll t = x;
		while(t){
			if(--mp[dp[t << 1] + dp[t << 1 | 1] + w[t]] == 0){
				mp.erase(dp[t << 1] + dp[t << 1 | 1] + w[t]);
			}
			t >>= 1;
		}
		w[x] = v;
		while(x){
			dp[x] = max(dp[x << 1], dp[x << 1 | 1]) + w[x];
			mp[dp[x << 1] + dp[x << 1 | 1] + w[x]]++;
			x >>= 1;
		}
		cout << prev(mp.end())->first << "\n";
	}
}