백준16978 수열과 쿼리 22

작성일 | In

문제 링크

  • http://icpc.me/16978

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • O(Q log N)

풀이

1번 쿼리는 평범한 세그먼트 트리처럼 값을 변경하는 쿼리입니다.
2번 쿼리는 K번째 쿼리까지 적용되었을 때의 구간 합을 구하는 쿼리입니다.

쿼리를 정렬해서 오프라인으로 처리해주면 쉽게 풀 수 있습니다.

전체 코드

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

typedef long long ll;

struct asdf{
	ll kth, idx;
	ll op, a, b;

	bool operator < (asdf &t){
		if(kth != t.kth) return kth < t.kth;
		return op < t.op;
	}
};

ll tree[404040];
int bias;

void init(int n){
	for(bias=1; bias<=n; bias<<=1);
}

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;
}

vector<asdf> v;
int pv;
int pv2;
ll ans[101010];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n; init(n);
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		update(i, t);
	}

	int q; cin >> q;
	for(int i=1; i<=q; i++){
		asdf now;
		int op; cin >> op;
		now.op = op;
		if(op == 1){
			now.kth = ++pv2;
			cin >> now.a >> now.b;
		}else{
			now.idx = ++pv;
			cin >> now.kth >> now.a >> now.b;
		}
		v.push_back(now);
	}

	sort(v.begin(), v.end());

	for(auto i : v){
		int op = i.op;
		if(op == 1){
			update(i.a, i.b);
		}else{
			ll res = query(i.a, i.b);
			ans[i.idx] = res;
		}
	}

	for(int i=1; i<=pv; i++) cout << ans[i] << "\n";
}