백준 알고리즘 1517번 : 버블 소트

링크

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

sol1) FenwickTree + inversion counting + 좌표 압축

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define int int64_t
using namespace std;

using pii = pair<int, int>;

vector<int> coord;
int arr[500001], idx[500001];

inline int getIdx(int val)
{
    return (lower_bound(coord.begin(), coord.end(), val) - coord.begin()) + 1;
}

template <size_t sz>
struct FenwickTree
{
    vector<int> tree;
    FenwickTree() : tree(sz + 1) {}
    void update(int i, int val)
    {
        for (; i <= sz; i += i & -i)
            tree[i] += val;
    }
    int query(int i)
    {
        int ret = 0;
        for (; i; i -= i & -i)
            ret += tree[i];
        return ret;
    }
};

int32_t main()
{
    fastio;
    int n, r = 0;
    cin >> n;
    vector<pii> v;
    FenwickTree<500001> FT;
    for (int i = 1; i <= n; i++)
    {
        cin >> arr[i];
        coord.push_back(arr[i]);
    }
    // compress coordinate
    sort(coord.begin(), coord.end());
    coord.erase(unique(coord.begin(), coord.end()), coord.end());
    for (int i = 1; i <= n; i++)
        idx[i] = getIdx(arr[i]);
    for (int i = n; i >= 1; i--)
    {
        int t = idx[i];
        r += FT.query(t - 1);
        FT.update(t, 1);
    }
    cout << r << "\n";
}

입력으로 들어오는 좌표값의 범위가 굉장히 크기 때문에 좌표 압축이 필요합니다.