[백준 14427] 수열과 쿼리 15

작성일 | In |

문제 링크

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

풀이

${A_i, i}$를 관리하는 최솟값 세그 트리를 구현해 주면 됩니다. 하지만 전체 구간에 대한 쿼리로 주어지므로 set이나 삭제가 가능한 우선순위큐를 이용해 최솟값만 가져올 수 있도록 구현해도 됩니다. 업데이트 $O(\log N)$, 쿼리 $O(1)$이므로 전체 시간복잡도는 $O(M \log N)$입니다. 아래는 삭제가 가능한 우선순위큐로 구현한 코드입니다.

전체 코드

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
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int n, m, a[100100];
priority_queue<pii, vector<pii>, greater<pii>> pq, rpq;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        pq.push({a[i], i});
    }
    cin >> m;
    while(m--){
        int q; cin >> q;
        if(q == 1){
            int i, v; cin >> i >> v;
            rpq.push({a[i], i});
            a[i] = v;
            pq.push({a[i], i});
        }else{
            while(!rpq.empty() && pq.top() == rpq.top()) pq.pop(), rpq.pop();
            cout << pq.top().second << "\n";
        }
    }
}