Inversion-Number(転倒数) (math/inversion_number.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-25 02:18:11+09:00

なにこれ

配列 $v$ の転倒数を求める．

関数

• inv_count(v)：配列 v の転倒数を返す．

計算量

配列 $v$ の要素数を $n$ とする．

• $O(n \log n)$

Depends on

• binary_indexed_tree(BIT) (tree/binary_indexed_tree.cpp)

Verified with

• test/aoj_ALDS1_5_D.cpp

Code

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

Back to top page