[BOJ | 백준] 14428번: 수열과 쿼리 16

by Kimcoding on 2020-03-05 16:24

in BOJ

문제 설명

BOJ 14428

점 업데이트와 구간 쿼리를 하는 문제입니다.

구간 쿼리는 최솟값을 구하는 쿼리입니다.

풀이

세그먼트 트리 문제입니다.

기본적인 세그먼트 트리 형태이고 구간 쿼리만 값을 우선으로 최솟값을 구해주고 차선으로 인덱스의 최솟값을 구해주면 됩니다.

저는 구조체로 값과 인덱스를 저장한 뒤 세그먼트 트리 update, query를 할 때 값이 같을 때는 인덱스의 최솟값을 그렇지 않을 때는 값의 최솟값을 구했습니다.

구간 쿼리를 하고 나온 인덱스 값을 출력하면 됩니다.

기본 세그먼트 트리라 세그먼트 트리를 배우고 바로 풀기에 좋은 문제 같아요 :)

소스 코드

#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

struct p {
	int Min = 1e9 + 7, idx = 0;
	bool operator< (const p& u) const {
		if (Min == u.Min) return idx < u.idx;
		return Min < u.Min;
	}
};

struct ST {
	p* tree;
	int leaf;
	ST(int n) {
		leaf = (1 << (int)ceil(log2(n)));
		tree = new p[leaf * 2];
		leaf--;
	}
	void update(int idx, int val) {
		idx += leaf;
		tree[idx] = p{ val, idx - leaf };
		while (idx >>= 1) tree[idx] = min(tree[idx << 1], tree[idx << 1 | 1]);
	}
	p query(int l, int r) {
		p ret;
		l += leaf, r += leaf;
		for (; l <= r; l >>= 1, r >>= 1) {
			if (l & 1) ret = min(ret, tree[l++]);
			if (~r & 1) ret = min(ret, tree[r--]);
		}
		if (l == r) ret = min(ret, tree[l]);
		return ret;
	}
	~ST() {
		delete[] tree;
	}
};

int main() {
	FIO;
	int n, m; cin >> n;
	ST st(n);
	FOR(i, 1, n) {
		int x; cin >> x;
		st.update(i, x);
	}
	cin >> m;
	while (m--) {
		int a, b, c; cin >> a >> b >> c;
		if (a == 1) st.update(b, c);
		else cout << st.query(b, c).idx << '\n';
	}
	return 0;
}