This documentation is automatically generated by online-judge-tools/verification-helper
#include "seq/inversion.hpp"
#pragma once
#include "ds/fenwicktree/fenwicktree_01.hpp"
template <typename T>
ll inversion(vc<T> A) {
int N = len(A);
if (A.empty()) return 0;
ll ANS = 0;
FenwickTree_01 bit(N);
auto I = argsort(A);
for (auto& i: I) {
ANS += bit.sum_all() - bit.sum(i);
bit.add(i, 1);
}
return ANS;
}
// i 番目:A_i が先頭になるように rotate したときの転倒数
template <typename T, bool SMALL = false>
vi inversion_rotate(vc<T>& A) {
const int N = len(A);
if (!SMALL) {
auto key = A;
UNIQUE(key);
for (auto&& x: A) x = LB(key, x);
}
ll K = MAX(A) + 1;
ll ANS = 0;
FenwickTree<Monoid_Add<int>> bit(K);
for (auto&& x: A) {
ANS += bit.sum(x + 1, K);
bit.add(x, 1);
}
vi res(N);
FOR(i, N) {
res[i] = ANS;
ll x = A[i];
ANS = ANS + bit.sum(x + 1, K) - bit.prefix_sum(x);
}
return res;
}
// inv[i][j] = inversion A[i:j) であるような (N+1, N+1) テーブル
template <typename T>
vvc<int> all_range_inversion(vc<T>& A) {
int N = len(A);
vv(int, dp, N + 1, N + 1);
FOR_R(L, N + 1) FOR(R, L + 2, N + 1) {
dp[L][R] = dp[L][R - 1] + dp[L + 1][R] - dp[L + 1][R - 1];
if (A[L] > A[R - 1]) ++dp[L][R];
}
return dp;
}
template <typename T>
ll inversion_between(vc<T> A, vc<T> B) {
int N = len(A);
map<T, vc<int>> MP;
FOR(i, N) MP[B[i]].eb(i);
vc<int> TO(N);
FOR_R(i, N) {
auto& I = MP[A[i]];
if (I.empty()) return -1;
TO[i] = POP(I);
}
return inversion(TO);
}
#line 2 "ds/fenwicktree/fenwicktree_01.hpp"
#line 2 "alg/monoid/add.hpp"
template <typename E>
struct Monoid_Add {
using X = E;
using value_type = X;
static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
static constexpr X inverse(const X &x) noexcept { return -x; }
static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
static constexpr X unit() { return X(0); }
static constexpr bool commute = true;
};
#line 3 "ds/fenwicktree/fenwicktree.hpp"
template <typename Monoid>
struct FenwickTree {
using G = Monoid;
using MX = Monoid;
using E = typename G::value_type;
int n;
vector<E> dat;
E total;
FenwickTree() {}
FenwickTree(int n) { build(n); }
template <typename F>
FenwickTree(int n, F f) {
build(n, f);
}
FenwickTree(const vc<E>& v) { build(v); }
void build(int m) {
n = m;
dat.assign(m, G::unit());
total = G::unit();
}
void build(const vc<E>& v) {
build(len(v), [&](int i) -> E { return v[i]; });
}
template <typename F>
void build(int m, F f) {
n = m;
dat.clear();
dat.reserve(n);
total = G::unit();
FOR(i, n) { dat.eb(f(i)); }
for (int i = 1; i <= n; ++i) {
int j = i + (i & -i);
if (j <= n) dat[j - 1] = G::op(dat[i - 1], dat[j - 1]);
}
total = prefix_sum(m);
}
E prod_all() { return total; }
E sum_all() { return total; }
E sum(int k) { return prefix_sum(k); }
E prod(int k) { return prefix_prod(k); }
E prefix_sum(int k) { return prefix_prod(k); }
E prefix_prod(int k) {
chmin(k, n);
E ret = G::unit();
for (; k > 0; k -= k & -k) ret = G::op(ret, dat[k - 1]);
return ret;
}
E sum(int L, int R) { return prod(L, R); }
E prod(int L, int R) {
chmax(L, 0), chmin(R, n);
if (L == 0) return prefix_prod(R);
assert(0 <= L && L <= R && R <= n);
E pos = G::unit(), neg = G::unit();
while (L < R) { pos = G::op(pos, dat[R - 1]), R -= R & -R; }
while (R < L) { neg = G::op(neg, dat[L - 1]), L -= L & -L; }
return G::op(pos, G::inverse(neg));
}
vc<E> get_all() {
vc<E> res(n);
FOR(i, n) res[i] = prod(i, i + 1);
return res;
}
void add(int k, E x) { multiply(k, x); }
void multiply(int k, E x) {
static_assert(G::commute);
total = G::op(total, x);
for (++k; k <= n; k += k & -k) dat[k - 1] = G::op(dat[k - 1], x);
}
void set(int k, E x) { add(k, G::op(G::inverse(prod(k, k + 1)), x)); }
template <class F>
int max_right(const F check, int L = 0) {
assert(check(G::unit()));
E s = G::unit();
int i = L;
// 2^k 進むとダメ
int k = [&]() {
while (1) {
if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
if (i == 0) { return topbit(n) + 1; }
int k = lowbit(i) - 1;
if (i + (1 << k) > n) return k;
E t = G::op(s, dat[i + (1 << k) - 1]);
if (!check(t)) { return k; }
s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
}
}();
while (k) {
--k;
if (i + (1 << k) - 1 < len(dat)) {
E t = G::op(s, dat[i + (1 << k) - 1]);
if (check(t)) { i += (1 << k), s = t; }
}
}
return i;
}
// check(i, x)
template <class F>
int max_right_with_index(const F check, int L = 0) {
assert(check(L, G::unit()));
E s = G::unit();
int i = L;
// 2^k 進むとダメ
int k = [&]() {
while (1) {
if (i % 2 == 1) { s = G::op(s, G::inverse(dat[i - 1])), i -= 1; }
if (i == 0) { return topbit(n) + 1; }
int k = lowbit(i) - 1;
if (i + (1 << k) > n) return k;
E t = G::op(s, dat[i + (1 << k) - 1]);
if (!check(i + (1 << k), t)) { return k; }
s = G::op(s, G::inverse(dat[i - 1])), i -= i & -i;
}
}();
while (k) {
--k;
if (i + (1 << k) - 1 < len(dat)) {
E t = G::op(s, dat[i + (1 << k) - 1]);
if (check(i + (1 << k), t)) { i += (1 << k), s = t; }
}
}
return i;
}
template <class F>
int min_left(const F check, int R) {
assert(check(G::unit()));
E s = G::unit();
int i = R;
// false になるところまで戻る
int k = 0;
while (i > 0 && check(s)) {
s = G::op(s, dat[i - 1]);
k = lowbit(i);
i -= i & -i;
}
if (check(s)) {
assert(i == 0);
return 0;
}
// 2^k 進むと ok になる
// false を維持して進む
while (k) {
--k;
E t = G::op(s, G::inverse(dat[i + (1 << k) - 1]));
if (!check(t)) { i += (1 << k), s = t; }
}
return i + 1;
}
int kth(E k, int L = 0) {
return max_right([&k](E x) -> bool { return x <= k; }, L);
}
};
#line 4 "ds/fenwicktree/fenwicktree_01.hpp"
struct FenwickTree_01 {
int N, n;
vc<u64> dat;
FenwickTree<Monoid_Add<int>> bit;
FenwickTree_01() {}
FenwickTree_01(int n) { build(n); }
template <typename F>
FenwickTree_01(int n, F f) {
build(n, f);
}
void build(int m) {
N = m;
n = ceil<int>(N + 1, 64);
dat.assign(n, u64(0));
bit.build(n);
}
template <typename F>
void build(int m, F f) {
N = m;
n = ceil<int>(N + 1, 64);
dat.assign(n, u64(0));
FOR(i, N) { dat[i / 64] |= u64(f(i)) << (i % 64); }
bit.build(n, [&](int i) -> int { return popcnt(dat[i]); });
}
int sum_all() { return bit.sum_all(); }
int sum(int k) { return prefix_sum(k); }
int prefix_sum(int k) {
int ans = bit.sum(k / 64);
ans += popcnt(dat[k / 64] & ((u64(1) << (k % 64)) - 1));
return ans;
}
int sum(int L, int R) {
if (L == 0) return prefix_sum(R);
int ans = 0;
ans -= popcnt(dat[L / 64] & ((u64(1) << (L % 64)) - 1));
ans += popcnt(dat[R / 64] & ((u64(1) << (R % 64)) - 1));
ans += bit.sum(L / 64, R / 64);
return ans;
}
void add(int k, int x) {
if (x == 1) add(k);
elif (x == -1) remove(k);
else assert(0);
}
void add(int k) {
dat[k / 64] |= u64(1) << (k % 64);
bit.add(k / 64, 1);
}
void remove(int k) {
dat[k / 64] &= ~(u64(1) << (k % 64));
bit.add(k / 64, -1);
}
int kth(int k, int L = 0) {
if (k >= sum_all()) return N;
k += popcnt(dat[L / 64] & ((u64(1) << (L % 64)) - 1));
L /= 64;
int mid = 0;
auto check = [&](auto e) -> bool {
if (e <= k) chmax(mid, e);
return e <= k;
};
int idx = bit.max_right(check, L);
if (idx == n) return N;
k -= mid;
u64 x = dat[idx];
int p = popcnt(x);
if (p <= k) return N;
k = binary_search([&](int n) -> bool { return (p - popcnt(x >> n)) <= k; }, 0, 64, 0);
return 64 * idx + k;
}
int next(int k) {
int idx = k / 64;
k %= 64;
u64 x = dat[idx] & ~((u64(1) << k) - 1);
if (x) return 64 * idx + lowbit(x);
idx = bit.kth(0, idx + 1);
if (idx == n || !dat[idx]) return N;
return 64 * idx + lowbit(dat[idx]);
}
int prev(int k) {
if (k == N) --k;
int idx = k / 64;
k %= 64;
u64 x = dat[idx];
if (k < 63) x &= (u64(1) << (k + 1)) - 1;
if (x) return 64 * idx + topbit(x);
idx = bit.min_left([&](auto e) -> bool { return e <= 0; }, idx) - 1;
if (idx == -1) return -1;
return 64 * idx + topbit(dat[idx]);
}
};
#line 3 "seq/inversion.hpp"
template <typename T>
ll inversion(vc<T> A) {
int N = len(A);
if (A.empty()) return 0;
ll ANS = 0;
FenwickTree_01 bit(N);
auto I = argsort(A);
for (auto& i: I) {
ANS += bit.sum_all() - bit.sum(i);
bit.add(i, 1);
}
return ANS;
}
// i 番目:A_i が先頭になるように rotate したときの転倒数
template <typename T, bool SMALL = false>
vi inversion_rotate(vc<T>& A) {
const int N = len(A);
if (!SMALL) {
auto key = A;
UNIQUE(key);
for (auto&& x: A) x = LB(key, x);
}
ll K = MAX(A) + 1;
ll ANS = 0;
FenwickTree<Monoid_Add<int>> bit(K);
for (auto&& x: A) {
ANS += bit.sum(x + 1, K);
bit.add(x, 1);
}
vi res(N);
FOR(i, N) {
res[i] = ANS;
ll x = A[i];
ANS = ANS + bit.sum(x + 1, K) - bit.prefix_sum(x);
}
return res;
}
// inv[i][j] = inversion A[i:j) であるような (N+1, N+1) テーブル
template <typename T>
vvc<int> all_range_inversion(vc<T>& A) {
int N = len(A);
vv(int, dp, N + 1, N + 1);
FOR_R(L, N + 1) FOR(R, L + 2, N + 1) {
dp[L][R] = dp[L][R - 1] + dp[L + 1][R] - dp[L + 1][R - 1];
if (A[L] > A[R - 1]) ++dp[L][R];
}
return dp;
}
template <typename T>
ll inversion_between(vc<T> A, vc<T> B) {
int N = len(A);
map<T, vc<int>> MP;
FOR(i, N) MP[B[i]].eb(i);
vc<int> TO(N);
FOR_R(i, N) {
auto& I = MP[A[i]];
if (I.empty()) return -1;
TO[i] = POP(I);
}
return inversion(TO);
}