백준17082 쿼리와 쿼리

작성일 | In

문제 링크

  • http://icpc.me/17082

사용 알고리즘

  • 그리디

시간복잡도

  • $O((N+Q) log N)$

풀이

모든 $[L_i, R_i]$ 구간을 합한 집합을 $S$라고 하면, 문제에서 요구하는 것은 $L_i$ 와 $R_j$ 를 적절하게 매칭해서 $S$의 최댓값을 최소로 만드는 것입니다.

어떤 놀이에서 $L_i ≤ L_j, R_i ≤ R_j$ 인 $L_i, L_j, R_i, R_j$ 에 대해 $[L_i, R_j], [L_j, R_i]$를 매칭한 경우를 생각해봅시다.
만약 $L_i > R_j$ 혹은 $L_j > R_i$ 라면 정답은 최댓값인 $10^9$가 됩니다.

그렇지 않다면 항상 $[L_i, R_j]$ 구간이 $[L_j, R_i]$ 구간을 포함하고 있습니다.
포함 관계를 풀어서 $[L_i, R_i], [L_j, R_j]$ 로 매칭을 해줘도 손해를 보지는 않고, 오히려 $L_i > R_j$ 혹은 $L_j, R_i$인 상황을 풀어줄 수도 있습니다.
위 사실을 이용해 $[L_i, R_i], [L_j, R_j]$로 매칭하는 것이 최적이라는 것을 Exchange Argument 방식으로 증명할 수 있습니다.

모든 $L_i$들과 $R_i$들을 정렬해준 다음, 작은 것부터 하나씩 매칭해주면 됩니다.

전체 코드

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <bits/stdc++.h>
using namespace std;

int n, m, q;
multiset<int> st;

int arr[202020];
int l[202020], r[202020];

int tree[202020];
int chk[202020];
void update(int x, int v){
    while(x < 202020){
        tree[x] += v;
        x += x & -x;
    }
}
int query(int x){
    int ret = 0;
    while(x){
        ret += tree[x];
        x -= x & -x;
    }
    return ret;
}

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

    while(q--){
        int a, b; cin >> a >> b;
        if(chk[a]) st.erase(st.lower_bound(arr[a]));
        if(chk[b]) st.erase(st.lower_bound(arr[b]));
        swap(arr[a], arr[b]);
        if(chk[a]) st.insert(arr[a]);
        if(chk[b]) st.insert(arr[b]);
        cout << *st.rbegin() << "\n";
    }
}