[BOJ] 17408 수열과 쿼리 24

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

17408번: 수열과 쿼리 24

알고리즘: Segment tree

 

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

---

접근:

$l\le i < j \le r$ 구간에서 $A_i+A_j$의 최댓값을 구하는 문제이다.

 

$A_i+A_j$가 최대가 되려면 $A_i$와 $A_j$가 각각 구간 내에서 최댓값, 두번째 최댓값이 되야한다.

 

따라서 [l, r] 구간에서 최댓값을 구하는 segment tree를 약간 변형시켜서,

노드에다가 최댓값과 두번째 최댓값을 저장하는 방식으로 해결하였다. 

 

---

다른 사람들 풀이를 보니, 알아두면 괜찮은 기법이 있었다.

{최댓값, 두번째 최댓값}을 저장하는게 아니라, {최댓값, 최댓값의 index}를 저장하는거다.

[l, r] 쿼리를 통해 최댓값을 찾고 -> [l, i-1], [i+1, r] 쿼리를 통해 두번째 최댓값을 찾는다.

 

이 기법은 나중에 한번쯤 다른 문제에 사용할 것 같다.

 

 

	// 17408: 수열과 쿼리 24
	// fail: 1~2 Ai를 v로 바꿀 때 max 갱신하는 부분 실수
	// 시간 없어서 대충 짜가지고 cmp 부분이 좀 비효율적임 -> 나중에 고쳐보자 -> 완료
	#include<iostream>
	#include<algorithm>
	#define MAX(a,b) (((a)>(b))?(a):(b))
	using namespace std;
	typedef pair<int, int> ii;
	int N, M, a, q, u, v, tree_size = 1;
	ii tree[1<<18];
	ii cmp(ii a, ii b)
	{
	int x, y;
	x = MAX(a.second, b.second);
	if (a.first >= b.first)
	{
	y = MAX(b.first, x);
	a.second = y;
	}
	else
	{
	y = MAX(a.first, x);
	a.first = b.first;
	a.second = y;
	}
	return a;
	}
	void updateST(int idx, int val)
	{
	idx += tree_size;
	tree[idx].first = val;
	while (idx > 1)
	{
	tree[idx>>1] = cmp(tree[idx], tree[idx^1]);
	idx >>= 1;
	}
	}
	int getAns(int l, int r)
	{
	ii ans = {0, 0};
	l += tree_size, r += tree_size;
	while (l <= r)
	{
	if (l & 1)
	{
	ans = cmp(ans, tree[l]);
	l++;
	}
	if (~r & 1)
	{
	ans = cmp(ans, tree[r]);
	r--;
	}
	l >>= 1, r >>= 1;
	}
	return ans.first + ans.second;
	}
	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;
	updateST(i, a);
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
	cin >> q >> u >> v;
	if (q == 1) updateST(u-1, v);
	else cout << getAns(u-1, v-1) << "\n";
	}
	return 0;
	}

view raw BOJ_17408.cpp hosted with ❤ by GitHub