백준17400 깃발춤

작성일 | In

문제 링크

  • http://icpc.me/17400

사용 알고리즘

  • Segment Tree

풀이

홀수 번째와 짝수 번째 공연자들을 따로 분리해서 세그먼트 트리로 관리해주면 됩니다.
구현에 들어가기 전에 0-based로 할 것인지 1-based로 할 것인지 명확하게 정해둬야 구현이 꼬이지 않습니다.

전체 코드

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
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long ll;

struct Seg {
	ll tree[1 << 20];
	int bias = 1 << 19;
	void update(int x, ll v) {
		x |= bias; tree[x] += v;
		while (x >>= 1) {
			tree[x] = tree[x << 1] + tree[x << 1 | 1];
		}
	}
	ll query(int l, int r) {
		l |= bias, r |= bias;
		ll ret = 0;
		while (l <= r) {
			if (l & 1) ret += tree[l++];
			if (~r & 1) ret += tree[r--];
			l >>= 1, r >>= 1;
		}
		return ret;
	}
}odd, even;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, q; cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		ll t; cin >> t;
		if (i & 1) odd.update(i / 2 + 1, t);
		else even.update(i / 2, t);
	}
	while (q--) {
		ll op, a, b; cin >> op >> a >> b;
		if (op == 1) {
			int oddL = a / 2 + 1, oddR = b / 2;
			if (b & 1) oddR++;
			int evenL = a / 2, evenR = b / 2;
			if (a & 1) evenL++;
			ll x = odd.query(oddL, oddR);
			ll y = even.query(evenL, evenR);
			cout << abs(x - y) << "\n";
		}
		else {
			if (a & 1) odd.update(a / 2 + 1, b);
			else even.update(a / 2, b);
		}
	}
}