dp/inversion-counting.hpp

• View this file on GitHub
• Last update: 2022-08-22 19:46:43+09:00
• Include: #include "dp/inversion-counting.hpp"

Depends on

• Binary Indexed Tree(Fenwick Tree) (data-structure/binary-indexed-tree.hpp)

Verified with

• verify/verify-yuki/yuki-1115.test.cpp

Code

#pragma once

#include "../data-structure/binary-indexed-tree.hpp"

// 転倒数
template <typename T>
long long inversion_counting(const vector<T>& v) {
  vector<T> xs{v};
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  int s = xs.size();
  BinaryIndexedTree<long long> bit(s + 1);
  long long ans = 0;
  for (auto& x : v) {
    int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
    if (i + 1 != s) ans += bit.sum(i + 1, s - 1);
    bit.add(i, 1);
  }
  return ans;
}

// 隣接 swap によって v を w に変えるのにかかる手数 (不可能 : -1)
template <typename T>
long long swap_distance(const vector<T>& v, const vector<T>& w) {
  if (v.size() != w.size()) return -1;
  int N = v.size();
  vector<pair<T, int>> vv(N), ww(N);
  for (int i = 0; i < N; i++) {
    vv[i] = make_pair(v[i], i);
    ww[i] = make_pair(w[i], i);
  }
  sort(begin(vv), end(vv));
  sort(begin(ww), end(ww));
  for (int i = 0; i < N; i++) {
    if (vv[i].first != ww[i].first) return -1;
  }
  vector<int> order(N);
  for (int i = 0; i < N; i++) {
    order[vv[i].second] = ww[i].second;
  }
  return inversion_counting(order);
}

#line 2 "dp/inversion-counting.hpp"

#line 2 "data-structure/binary-indexed-tree.hpp"

template <typename T>
struct BinaryIndexedTree {
  int N;
  vector<T> data;

  BinaryIndexedTree() = default;

  BinaryIndexedTree(int size) { init(size); }

  void init(int size) {
    N = size + 2;
    data.assign(N + 1, {});
  }

  // get sum of [0,k]
  T sum(int k) const {
    if (k < 0) return T{};  // return 0 if k < 0
    T ret{};
    for (++k; k > 0; k -= k & -k) ret += data[k];
    return ret;
  }

  // getsum of [l,r]
  inline T sum(int l, int r) const { return sum(r) - sum(l - 1); }

  // get value of k
  inline T operator[](int k) const { return sum(k) - sum(k - 1); }

  // data[k] += x
  void add(int k, T x) {
    for (++k; k < N; k += k & -k) data[k] += x;
  }

  // range add x to [l,r]
  void imos(int l, int r, T x) {
    add(l, x);
    add(r + 1, -x);
  }

  // minimize i s.t. sum(i) >= w
  int lower_bound(T w) {
    if (w <= 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] < w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }

  // minimize i s.t. sum(i) > w
  int upper_bound(T w) {
    if (w < 0) return 0;
    int x = 0;
    for (int k = 1 << __lg(N); k; k >>= 1) {
      if (x + k <= N - 1 && data[x + k] <= w) {
        w -= data[x + k];
        x += k;
      }
    }
    return x;
  }
};

/**
 * @brief Binary Indexed Tree(Fenwick Tree)
 * @docs docs/data-structure/binary-indexed-tree.md
 */
#line 4 "dp/inversion-counting.hpp"

// 転倒数
template <typename T>
long long inversion_counting(const vector<T>& v) {
  vector<T> xs{v};
  sort(begin(xs), end(xs));
  xs.erase(unique(begin(xs), end(xs)), end(xs));
  int s = xs.size();
  BinaryIndexedTree<long long> bit(s + 1);
  long long ans = 0;
  for (auto& x : v) {
    int i = lower_bound(begin(xs), end(xs), x) - begin(xs);
    if (i + 1 != s) ans += bit.sum(i + 1, s - 1);
    bit.add(i, 1);
  }
  return ans;
}

// 隣接 swap によって v を w に変えるのにかかる手数 (不可能 : -1)
template <typename T>
long long swap_distance(const vector<T>& v, const vector<T>& w) {
  if (v.size() != w.size()) return -1;
  int N = v.size();
  vector<pair<T, int>> vv(N), ww(N);
  for (int i = 0; i < N; i++) {
    vv[i] = make_pair(v[i], i);
    ww[i] = make_pair(w[i], i);
  }
  sort(begin(vv), end(vv));
  sort(begin(ww), end(ww));
  for (int i = 0; i < N; i++) {
    if (vv[i].first != ww[i].first) return -1;
  }
  vector<int> order(N);
  for (int i = 0; i < N; i++) {
    order[vv[i].second] = ww[i].second;
  }
  return inversion_counting(order);
}

Back to top page