[백준 2832] 정렬

문제

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

알고리즘

fenwick

풀이

감소하는 연속 부분 수열을 reverse를 몇번 해야 오름차순으로 만들 수 있는지 묻는 문제입니다.

주어진 순열중에서 연속한 내림차순이 있다면 해당 부분을 reverse함수를 통해 오름차순으로 만듭니다. 연속 부분 오름차순들이 여러개 만들어졌다면 이들 사이의 경계값은 길이가 2인 내림차순이 존재하게 됩니다. 길이가 2인 내림차순을 reverse하여 오름차순으로 정렬하는 것은 inversion을 counting하는 것과 일치합니다. $N$제한이 10만이므로 펜윅트리를 통해 빠르게 inversion을 세면 됩니다.

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

const int MAXN = 1e5 + 5;

long long N, ans, fen[MAXN];
vector<int> arr;

int query(int idx) {
    int ret = 0;
    while (idx) {
        ret += fen[idx];
        idx -= idx & -idx;
    }
    return ret;
}

void update(int idx, int val) {
    while (idx <= N) {
        fen[idx] += val;
        idx += idx & -idx;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    rep(i, N) {
        int x;
        cin >> x;
        arr.emplace_back(x);
    }
    arr.emplace_back(N + 1);
    int l = 0;
    int r = 1;
    while (r <= N) {
        if (arr[r - 1] > arr[r]) {
            ++r;
            continue;
        }
        if (l != r - 1) {
            reverse(arr.begin() + l, arr.begin() + r);
            ++ans;
        }
        l = r;
        r += 1;
    }
    rep(i, N) {
        ans += query(N) - query(arr[i]);
        update(arr[i], 1);
    }
    cout << ans;
    return 0;
}