백준14428 수열과 쿼리 16

작성일 | In

문제 링크

  • http://icpc.me/14428

사용 알고리즘

  • Segment Tree

시간복잡도

  • O(M log N)

풀이

최솟값 세그 트리를 구현해주되, 원소의 값과 인덱스를 같이 관리해주면 됩니다.
C++ STL의 pair에는 less than operator가 이미 구현이 되어있으므로 행복하게 코드를 짤 수 있습니다.

전체 코드

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

typedef pair<int, int> p;

struct Seg{
	p tree[404040];
	int bias;

	void init(int n){
		for(bias=1; bias<n; bias<<=1);
		for(int i=0; i<bias*2; i++){
			tree[i] = {1e9+7, 1e9+7};
		}
	}

	void build(){
		for(int i=bias-1; i>=1; i--){
			tree[i] = min(tree[i << 1], tree[i << 1 | 1]);
		}
	}

	void update(int x, int v){
		x |= bias;
		tree[x].mini = v;
		while(x >>= 1){
			tree[x] = min(tree[x << 1], tree[x << 1 | 1]);
		}
	}

	int query(int l, int r){
		p ret = {1e9+7, 1e9+7};
		l |= bias, r |= bias;
		while(l < r){
			if(l & 1) ret = min(ret, tree[l++]);
			if(!(r & 1)) ret = min(ret, tree[r--]);
			l >>= 1, r >>= 1;
		}
		if(l == r) ret = min(ret, tree[l]);
		return ret.idx;
	}
}seg;

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n; cin >> n;
	seg.init(n);
	for(int i=1; i<=n; i++){
		int t; cin >> t;
		seg.tree[i | seg.bias] = {t, i};
	}
	seg.build();
	int m; cin >> m;
	while(m--){
		int op, a, b; cin >> op >> a >> b;
		if(op == 1){
			seg.update(a, b);
		}else{
			cout << seg.query(a, b) << "\n";
		}
	}
}