This documentation is automatically generated by competitive-verifier/competitive-verifier
配列 $v$ の転倒数を求める.
v
の転倒数を返す.配列 $v$ の要素数を $n$ とする.
#pragma once
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#include "../tree/binary_indexed_tree.cpp"
template<typename T> long long inv_count(const vector<T> &v) {
const int N = v.size();
long long res = 0;
BIT<int> bt(N);
map<T, int> mp;
for(const T &a : v) mp.emplace(a, 0);
int i = 1;
for(auto &a : mp) {
a.second = i;
i++;
}
for(const T &a : v) {
bt.add(mp[a], 1);
res += bt.sum(mp[a] + 1, N);
}
return res;
};
#line 2 "math/inversion_number.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
#line 2 "tree/binary_indexed_tree.cpp"
#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif
template<typename T> struct BIT {
private:
vector<T> node;
const int N;
public:
BIT(int n) : node(n + 1, 0), N(n) {}
BIT(const vector<T> &v) : node(v.size() + 1, 0), N(v.size()) {
for(int i = 0; i < N; i++) node[i + 1] = v[i];
for(int i = 1; i < N; i++) {
int j = i + (i & -i);
if(j <= N) node[j] += node[i];
}
}
T sum(int idx) {
assert(0 <= idx && idx <= N);
T res = 0;
while(idx) {
res += node[idx];
idx -= idx & -idx;
}
return res;
}
T sum(int l, int r) {
assert(0 <= l && r <= N);
if(l > r) return T(0);
return sum(r) - sum(max(l - 1, 0));
}
inline T get(int idx) {
assert(0 < idx and idx <= N);
return sum(idx, idx);
}
void add(int idx, T val) {
assert(0 < idx && idx <= N);
while(idx <= N) {
node[idx] += val;
idx += idx & -idx;
}
}
};
#line 10 "math/inversion_number.cpp"
template<typename T> long long inv_count(const vector<T> &v) {
const int N = v.size();
long long res = 0;
BIT<int> bt(N);
map<T, int> mp;
for(const T &a : v) mp.emplace(a, 0);
int i = 1;
for(auto &a : mp) {
a.second = i;
i++;
}
for(const T &a : v) {
bt.add(mp[a], 1);
res += bt.sum(mp[a] + 1, N);
}
return res;
};