버블 소트

백준 1517번: 버블 소트

아이디어

문제 이름은 버블 소트지만 버블 소트 하면서 몇번 swap했나 세면 당연히 틀린다. N이 최대 500,000이므로 O(NlogN)에 풀어야 한다.

세그트리에 정렬 여부를 기록한다. 쿼리를 날리면 해당 구간에 정렬되지 않은 원소가 몇개인지 합을 구해서 알려준다.
작은 숫자부터(sort()하면 NlogN에 가능) 0 ~ 자기 인덱스에 정렬되지 않은 원소가 몇개인지 세서 정답에 더한다. 그리고 세그트리에 정렬했다고 업데이트해준다.

코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> arr;
vector<int> tree;

int init(int start, int end, int node) {
    if (start == end) return tree[node] = 1;
    return tree[node] = init(start, (start+end)/2, node*2) + init((start+end)/2+1, end, node*2+1);
}

int query(int start, int end, int left, int right, int node) {
    if (right < start || left > end) return 0;
    if (left <= start && end <= right) return tree[node];
    return query(start, (start+end)/2, left, right, node*2) + query((start+end)/2+1, end, left, right, node*2+1);
}

void update(int start, int end, int idx, int node, int value) {
    if (start > idx || end < idx) return;
    if (start == end) {
        if (start == idx) tree[node] = value;
        return;
    }
    update(start, (start+end)/2, idx, node*2, value);
    update((start+end)/2+1, end, idx, node*2+1, value);
    tree[node] = tree[node*2] + tree[node*2+1];
    return;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;
        arr.push_back({x, i});
    }

    int h = (int)ceil(log2(N));
    int size = (1<<h+1);
    tree.resize(size);
    init(0, N-1, 1);
    sort(arr.begin(), arr.end());

    long long ans = 0;
    for (int i = 0; i < N; i++) {
        int q = arr[i].second;
        ans += query(0, N-1, 0, q, 1)-1;
        update(0, N-1, q, 1, 0);
    }
    cout << ans;
    return 0;
}

여담

세그트리 고수의 길.. 사실 합병정렬로 더 쉽게 풀 수 있다고 한다. 나중에 알아봐야겠다.