BOJ 1517: 버블 소트 작성일 2020-02-26 https://www.acmicpc.net/problem/1517 2월동안 187문제 풀기(지난달 누적 87개) (68/187) 머지소트로 그냥 품, 머지 소트가 실행시간 자체는 더 빠름 Fenwick이나 segtree로는 arr를 sort하고 원래 index로 바꿔서 range를 줄인 뒤에 index가 역전된 카운트를 새면 됨 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include <bits/stdc++.h> using namespace std; typedef long long LL; class InversionCount { int N; LL count; vector<int> arr, bak; public: InversionCount(int n): N(n), arr(n), bak(n), count(0) { for(int i = 0; i < n; i++) scanf("%d", &arr[i]); } LL solve() { mergeSort(0, N-1); return count; } void mergeSort(int lb, int ub) { if(lb == ub) return; int m = (lb+ub)/2; mergeSort(lb, m); mergeSort(m+1, ub); merge(lb, m+1, ub+1); } void merge(int l, int r, int e) { int l0 = l, r0 = r; for(int i = l; i < e; i++) { if(r == e || (l < r0 && arr[l] <= arr[r])) bak[i] = arr[l++]; else bak[i] = arr[r++], count += r0 - l; } for(int i = l0; i < e; i++) arr[i] = bak[i]; } }; int main() { int N; scanf("%d", &N); InversionCount inv(N); cout << inv.solve(); }