백준2934 LRH 식물

작성일 | In

문제 링크

  • http://icpc.me/2934

사용 알고리즘

  • Fenwick Tree

시간복잡도

  • O(NlgN)

풀이

Fenwick Tree with Range update Point query

[S, E]구간에 식물이 추가된다면 (S에 있는 가로 줄기의 개수 + E에 있는 가로 줄기의 개수)만큼 꽃이 피고, (S, E)구간에 가로 줄기가 생성됩니다.
(S, E)구간에 가로 줄기가 생성되는 것은 [S+1, E-1]구간에 1을 더하는 것으로 표현할 수 있습니다.

Fenwick Tree에서는 range update, point query를 쉽게 구현할 수 있습니다.
그러므로 꽃이 피는 개수는 query(s) + query(e)로 구해주고, 가로 줄기가 생성되는 것은 update(s, e, 1)처럼 구현해주면 됩니다.

전체 코드

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

typedef long long ll;

ll tree[101010];

void update(int x, int v){
	x++;
	while(x < 101010){
		tree[x] += v;
		x += x & -x;
	}
}

void update(int l, int r, int v){
	update(l, v); update(r+1, -v);
}

ll query(int x){
	x++;
	ll ret = 0;
	while(x){
		ret += tree[x];
		x -= x & -x;
	}
	return ret;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	ll ans = 0;
	for(int i=1; i<=n; i++){
		int s, e; cin >> s >> e;
		int a = query(s);
		int b = query(e);

		update(s, -a), update(s+1, a);
		update(e, -b), update(e+1, b);
		update(s+1, e-1, 1);
		cout << a+b << "\n";
	}
}