[BOJ] 14427 수열과 쿼리 15

https://www.acmicpc.net/problem/14427

14427번: 수열과 쿼리 15

알고리즘: Segment tree

 

시간복잡도: $O((M+N)logN)$

---

접근:

1. 많은 수의 쿼리 ($1\le M\le 10^5$)

 

일단 쿼리 수가 너무 많다는 점에서 나이브한 방법으로는 안된다는 걸 알 수 있다.

 

매 쿼리마다 최솟값을 구하다 보면 시간복잡도가 $O(MN)$이 나와 TLE를 받게 된다.

지금보니 쿼리가 구간 쿼리가 아니여서 naive하게 구현해도 될 듯 싶다. (priority queue 등)

 

고로 매 순간마다 쿼리를 계산하는게 아니라,

미리 전처리를 한 데이터를 가지고 쿼리를 빠른 속도로 계산하는 방식으로 접근해야 한다.

그리고 이런 유형의 문제에서 강력한 도구가 바로 트리 구조이다.

 

문제를 해결할 수 있는 다양한 트리구조가 있는데 그 중 segment tree를 사용하여 문제를 해결하였다.

(binary search tree인 set을 이용해도 해결이 가능하다.)

 

 

segment tree의 value를 $\{ A_i,\ i\}$로 설정하여,

부모 node 마다 최솟값을 갱신해나가면 쉽게 쿼리를 처리해줄 수 있다.

 

	// 14427: 수열과 쿼리 15
	#include<iostream>
	#include<utility>
	using namespace std;
	int N, M, a, b, c, tree_size = 1;
	pair<int, int> tree[1<<18];
	int main()
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	while (tree_size < N) tree_size <<= 1;
	for (int i = 0; i < N; ++i)
	{
	cin >> a;
	tree[tree_size + i] = {a, i+1};
	}
	for (int i = N; i < tree_size; ++i)
	tree[tree_size + i] = {0x7fffffff, i+1};
	for (int i = tree_size-1; i >= 1; --i)
	{
	if (tree[i<<1].first <= tree[(i<<1)|1].first)
	tree[i] = tree[i<<1];
	else
	tree[i] = tree[(i<<1)|1];
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> a;
	if (a == 1)
	{
	cin >> b >> c;
	int idx = tree_size + b - 1;
	tree[idx].first = c;
	while (idx > 1)
	{
	idx >>= 1;
	if (tree[idx<<1].first <= tree[(idx<<1)|1].first)
	tree[idx] = tree[idx<<1];
	else
	tree[idx] = tree[(idx<<1)|1];
	}
	}
	else
	cout << tree[1].second << "\n";
	}
	}

view raw BOJ_14427.cpp hosted with ❤ by GitHub