백준 알고리즘 9463번 : 순열 그래프

링크

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

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

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

sol2) 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>;

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(){
  int tc; cin >> tc;
  while(tc--){
    int n,r = 0; cin >> n;
    int check[100001] = {0,};
    vector<pii> v(n);
    FenwickTree<100001> FT;
    for(int i = 1; i <= n; i++){
      int t; cin >> t;
      check[t] = i;
    }
    for(int i = 1; i <= n; i++){
      int t; cin >> t;
      v[i - 1] = {i, check[t]};
    }
    sort(v.begin(), v.end());
    for(int i = n - 1; i >= 0; i--){
      int t = v[i].second;
      r += FT.query(t - 1);
      FT.update(t, 1);
    }
    cout << r << "\n";
  }
}

겹치는 선분의 갯수를 구하는 문제여서 inversion counting을 구해주면 되는 문제였고, 공장문제와 똑같이 풀어주면 되는 문제였습니다.