문제 요약 및 풀이
boj-14427 글에서 평방 분할을 이용한 풀이를 끄적였는데, solved.ac 난이도 기여를 하러 들어갔더니
대부분의 의견이 세그먼트 트리 기준으로 난이도 기여를 하지말아달라는 것이었다.
왤까 생각을 해보니.. 이 문제는 priority_queue로 간단하게 해결된다.
일단, 다른 수열과 쿼리 문제와 다르게 이 문제는 특정 구간을 구하는 쿼리가 아닌 전체 구간의 최소값을 구하는 것이다.
따라서 세그먼트 트리나 평방 분할같이 특정 구간의 대표값을 알아내는 쿼리 자료구조/알고리즘을 쓸 필요가 없었다.
그냥 값들을 모조리 priority_queue에 넣어두고, 현재 해당 인덱스에 들어가있는 값과 priority_queue의 top()의 값이 제대로 성립하는지 확인하면서 top()값들을 출력하면 되었다.
풀이 코드
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
#include <bits/stdc++.h>
#define for1(s,n) for(int i = s; i<n; i++)
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
priority_queue <pll, vector<pll>, greater<pll>> Q;
ll N, M;
ll ar[110000];
ll q, a, b;
int main() {
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> N;
for1(0, N) {
cin >> ar[i];
Q.push({ ar[i], i});
}
cin >> M;
while(M--) {
cin >> q;
if(q == 1) {
cin >> a >> b; a--;
ar[a] = b;
Q.push({b, a});
} else {
while(!Q.empty() && ar[Q.top().second] != Q.top().first) {
Q.pop();
}
cout << Q.top().second + 1<< "\n";
}
}
}