[백준 17082] 쿼리와 쿼리

작성일 | In |

문제 링크

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

풀이

문제에서 요구하는 것은 $[L_i, R_i]$ 구간의 합집합 중 최댓값을 구하는 것입니다. $L_i$와 $R_i$를 잘 매칭시켜서 합쳤을 때 구간을 최대한 적게 포함되도록 해야하는데 $L_i > R_i$인 경우를 피하면서 $L_i$과 $R_i$을 매칭한다면 어떻게 순서를 바꾸어도 구간의 합집합은 변하지 않습니다. 그러므로 누적합을 이용해 합집합에 포함된 위치를 찾아낼 수 있습니다. 합집합에 포함된 위치의 수를 모두 저장한 뒤에 쿼리의 입력으로 들어오는 위치의 수를 저장한 곳에서 교체할 수 있다면 저장한 값들 중 최댓값을 찾아내는 것으로 쿼리를 처리할 수 있습니다. 수를 저장하거나 지우는 데 $O(\log N)$, 최댓값을 찾는 데 $O(1)$인 multiset을 이용하면 총 시간복잡도 $O(Q \log N)$입니다.

$L_i > R_i$라면 누적합을 처리하는 중에 음수가 나오게 되고, 이때 쿼리는 모두 $10^9$를 출력해야 하는 것에 유의해야합니다.

전체 코드

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

int n, m, q, a[200200], l[200200], r[200200], t[200200];
multiset<int> s;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin >> n >> m >> q;
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=1;i<=m;i++) cin >> l[i];
    for(int i=1;i<=m;i++) cin >> r[i];
    for(int i=1;i<=m;i++) t[l[i]]++, t[r[i]+1]--;
    
    for(int i=1;i<=n;i++){
        t[i] += t[i-1];
        if(t[i] < 0){
            while(q--) cout << "1000000000\n";
            return 0;
        }
        if(t[i]) s.insert(a[i]);
    }

    while(q--){
        int x, y; cin >> x >> y;
        swap(a[x], a[y]);
        if(!t[x] + !t[y] == 1){
            if(t[y]) swap(x, y);
            s.erase(s.lower_bound(a[y]));
            s.insert(a[x]);
        }
        cout << *s.rbegin() << "\n";
    }
}