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

핵심 아이디어

<aside> 💡

$i$번째 수가 $a_i$라면 $a_i$는 $1$번째 수부터 $i-1$번째 수 중에서 $a_i$보다 큰 원소의 수만큼 스왑연산이 이뤄진다.

</aside>

Inversion Counting 문제

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long ll;

class Seg
{
    private:
        int n;
        vector<int> tree;

        void upd(int node, int start, int end, int idx, int val)
        {
            if(idx<start || end<idx) return;
            if(start == end){
                tree[node]++;
                return;
            }

            int mid = start+end>>1;
            upd(2*node, start, mid, idx, val);
            upd(2*node+1, mid+1, end, idx, val);
            tree[node] = tree[2*node]+tree[2*node+1];
        }

        int qry(int node, int start, int end, int left, int right)
        {
            if(end<left || right<start) return 0;
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            int l = qry(2*node, start, mid, left, right);
            int r = qry(2*node+1, mid+1, end, left, right);
            return l+r;
        }

    public:
        void init(int n)
        {
            this->n = n;
            tree.resize(4*n);
        }

        void upd(int idx, int val) { upd(1, 1, n, idx, val); }
        int qry(int l, int r) { return qry(1, 1, n, l, r); }
};

int n;
int a[500'001];

vector<int> itov;
int vtoi(int v) {return lower_bound(itov.begin(), itov.end(), v)-itov.begin();}

signed main()
{
    FASTIO;
    cin >> n;
    itov.resize(n);
    Seg cnt;
    cnt.init(n);

    for(int i = 0; i<n; i++){
        cin >> a[i];
        itov[i] = a[i];
    }

    sort(itov.begin(), itov.end());
    itov.erase(unique(itov.begin(), itov.end()), itov.end());
    
    ll ans = 0;
    for(int i = 0; i<n; i++){
        int idx = vtoi(a[i])+1;
        cnt.upd(idx, 1);
        ans += cnt.qry(idx+1, n);
    }
    cout << ans;

    return 0;
}