[C++] 27897번 특별한 화재 경보

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

---

 

26/02/20

 

 

간단한 인버전 카운팅 문제이다.

---

 

문제 접근 방식:

 

 

먼저, 문제에서 정의하는 "확인 절차에 걸리는 전체 시간"은 다음과 같이 정의한다.

- $1$부터 $N$까지의 정수로 이루어진 순열 $A$가 주어진다.
- 어떤 $i$에 대해 $A[i] < A[j]$이면서 $j < i$인 $j$의 개수를 "학생 $i$를 확인하는데 걸리는 시간"이라고 정의한다.
- 순열 $A$에 대해 모든 "학생 $i$를 확인하는데 걸리는 시간"을 더한 값을 "확인 절차에 걸리는 전체 시간"이라고 정의한다.

일단 $L$번의 행동 횟수 제한을 제외한다면, 순열을 $N \ N-1 \ \dots \ 2 \ 1$순으로 나열한다면 확인 절차에 걸리는 전체 시간의 최댓값을 구할 수 있다.

그리고 그 값은 $N(N-1) / 2$이다.

하나의 순열에 대해서 두 인접한 원소를 교환한다면, "확인 절차에 걸리는 전체 시간"은 $1$증가하거나 $1$감소한다.

$p, q$순으로 나열되어 있을 때, $p < q$인 원소를 교환한다면 $1$증가, $p > q$인 원소를 교환한다면 $1$감소한다.

우리는 두 인접한 원소를 최대 $L$번 교환할 수 있다.

먼저, 현재 주어진 순열의 "확인 절차에 걸리는 전체 시간"을 구하자.

이건 세그먼트 트리로 쉽게 구할 수 있다.(우리가 잘 아는 인버전 카운팅이다.)

우리가 구하고자 하는건 두 인접한 원소를 최대 $L$번 교환했을 때, "확인 절차에 걸리는 전체 시간"의 최댓값이다.

느낌상 왠지 $1$감소하도록 원소를 교환하는 행위는 이득이 아닐 것 같다.

실제로도 항상 증가하도록 원소를 교환할 수 있는데, 해당 방법은 다음과 같다.

가장 큰 원소를 계속 왼쪽으로 보내자. 더 이상 보낼 수 없다면 그 다음으로 큰 원소를 계속 왼쪽으로 보내자.

그런식으로 하면 항상 "전체 시간"이 증가하도록 원소를 교환할 수 있다.

따라서, 현재 순열의 "확인 절차에 걸리는 전체 시간" + $L$이 우리가 구하고자 하는 값이 될 것 같다.

최댓값이 제한되어있으므로, 정확히 이야기하면 $\min(N(N-1) / 2, \text{now total time} + L)$이 우리가 구하고자 하는 값이 될 것이다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

// 27897번 특별한 화재 경보
// 세그먼트 트리 (카운팅 인버전)
#include <iostream>
#include <vector>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'

struct Segtree{
    int N;
    vector<long long> tree;
    Segtree(int dataSize) : N(dataSize), tree(4*dataSize, 0) {};

    void build(const vector<long long>& arr){build(1, 0, N, arr);}
    void build(int node, int l, int r, const vector<long long>& arr){
        if (l+1 == r){
            tree[node] = arr[l];
            return;
        }
        build(node << 1, l, (l+r)>>1, arr);
        build((node << 1) | 1, (l+r)>>1, r, arr);
        tree[node] = tree[node<<1] + tree[(node << 1)|1];
        return;
    }

    void update(int idx, long long val){update(1, 0, N, idx, val);}
    void update(int node, int l, int r, int idx, long long val){
        if (idx < l || r <= idx) return;
        if (l+1 == r){
            tree[node] = val;
            return;
        }
        update(node << 1, l, (l+r)>>1, idx, val);
        update((node << 1)|1, (l+r)>>1, r, idx, val);
        tree[node] = tree[node << 1] + tree[(node << 1)|1];
        return;
    }

    long long select(int ql, int qr){return select(1, 0, N, ql, qr);}
    long long select(int node, int l, int r, int ql, int qr){
        if (ql <= l && r <= qr) return tree[node];
        if (qr <= l || r <= ql) return 0;
        return select(node << 1, l, (l+r)>>1, ql, qr) + select((node << 1)|1, (l+r)>>1, r, ql, qr);
    }
};

int main(void){
    fastio

    long long N, L; cin >> N >> L;
    Segtree segtree(N);
    long long a;
    long long inversionCounting = 0;
    for (int i = 0; i < N; ++i){
        cin >> a;
        segtree.update(a-1, 1);
        inversionCounting += segtree.select(a, N);
    }
    cout << min(N*(N-1)/2, inversionCounting + L);
    return 0;
}