백준 알고리즘 10090번 : Counting Inversions

링크

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

sol1) FenwickTree

#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>;

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;
  FenwickTree<1 << 20> FT;
  vector<int> v(n);
  for(auto& c : v) cin >> c;
  for(int i = n - 1; i >= 0; i--){
    int t = v[i];
    r += FT.query(t - 1);
    FT.update(t , 1);
  }
  cout << r << "\n";
}

sol2) SegmentTree