転倒数

sequence/inversion_count.hpp · GitHub で見る

共通ページ

数列の転倒数、すなわち \(i<j\) かつ \(a_i>a_j\) を満たす添字の組の個数を返します。同じ値の組は数えません。入力は変更しません。

#include "lib/sequence/inversion_count.hpp"

std::vector<int> a{3, 1, 2, 1};
auto count = inversion_count(a);                     // 4
auto increasing = inversion_count(a, std::greater<>{}); // 1

操作	内容・返り値	計算量
inversion_count(a,compare = std::less<>{})	i < j かつ compare(a[j],a[i]) の組数を std::int64_t で返す	\(O(n\log n)\)

空列・長さ 1 の列は 0 です。比較関数は厳密弱順序を定めるものを使います。std::greater<>{} を指定すると、左の値が右の値より小さい組を数えます。比較関数で同値となる要素同士は、どちらの向きでも数えません。

入力は const なランダムアクセス・サイズ取得可能な range で、vector・array・span・deque・C 配列などを使えます。要素型に応じた比較関数を指定すれば、コピー不能な要素にも対応します。vector<bool> も扱えます。入力の長さは INT_MAX 以下とします。この範囲では最大の転倒数も符号付き 64 bit に収まります。

反復的なマージ処理で数え、座標圧縮や再帰は使いません。小さな単純コピー可能型では作業配列へ値をコピーし、それ以外では添字を並べ替えます。比較順で単調非減少・単調非増加の列では、作業配列を確保せずに答えを求めます。

長さを \(n\) として、時間は \(O(n\log n)\)、追加空間は \(O(n)\) です。単調非減少・単調非増加の列は \(O(n)\) 時間・\(O(1)\) 追加空間、空列は \(O(1)\) 時間・空間です。比較とランダムアクセスを \(O(1)\) とします。

検証コード

• test/inversion_count.test.cpp
• test/mo_inversions.test.cpp

コード

#ifndef INVERSION_COUNT_HPP
#define INVERSION_COUNT_HPP

#include <algorithm>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <ranges>
#include <type_traits>
#include <vector>

template<class Range, class Compare = std::less<>>
	requires std::ranges::random_access_range<const Range> && std::ranges::sized_range<const Range>
std::int64_t inversion_count(const Range &a, Compare compare = {}) {
	assert(std::ranges::size(a) <= std::size_t(std::numeric_limits<int>::max()));
	const std::size_t n = std::ranges::size(a);
	auto first = std::ranges::begin(a);
	std::size_t ordered = 1;
	while (ordered < n && !compare(first[ordered], first[ordered - 1])) ++ordered;
	if (ordered >= n) return 0;
	std::int64_t equal_pairs = 0;
	std::size_t run = 1, reversed = 1;
	for (; reversed < n && !compare(first[reversed - 1], first[reversed]); ++reversed) {
		if (compare(first[reversed], first[reversed - 1])) run = 1;
		else equal_pairs += static_cast<std::int64_t>(run++);
	}
	if (reversed == n) return static_cast<std::int64_t>(n) * (n - 1) / 2 - equal_pairs;
	using T = std::ranges::range_value_t<const Range>;
	constexpr bool cached = std::is_trivially_copyable_v<T> && sizeof(T) <= 16 &&
		std::is_default_constructible_v<T> && std::is_copy_constructible_v<T> &&
		std::is_copy_assignable_v<T> && !std::is_same_v<T, bool>;
	using Stored = std::conditional_t<cached, T, int>;
	std::vector<Stored> current(n), buffer(n);
	for (std::size_t i = 0; i < n; ++i) {
		if constexpr (cached) current[i] = first[i];
		else current[i] = static_cast<int>(i);
	}
	auto value = [&](const Stored &x) -> decltype(auto) {
		if constexpr (cached) return (x);
		else return first[x];
	};
	std::int64_t result = 0;
	constexpr std::size_t block = 8;
	for (std::size_t l = 0; l < n; l += block) {
		const auto end = std::min(l + block, n);
		for (std::size_t i = l + 1; i < end; ++i) {
			Stored x = current[i];
			std::size_t j = i;
			while (j > l && compare(value(x), value(current[j - 1]))) current[j] = current[j - 1], --j;
			current[j] = x;
			result += static_cast<std::int64_t>(i - j);
		}
	}
	for (std::size_t width = block; width < n; width *= 2) {
		for (std::size_t l = 0; l < n; l += 2 * width) {
			const auto mid = std::min(l + width, n), r = std::min(l + 2 * width, n);
			if (mid == r || !compare(value(current[mid]), value(current[mid - 1]))) {
				std::copy(current.begin() + l, current.begin() + r, buffer.begin() + l);
				continue;
			}
			if (compare(value(current[r - 1]), value(current[l]))) {
				result += static_cast<std::int64_t>(mid - l) * (r - mid);
				std::copy(current.begin() + mid, current.begin() + r, buffer.begin() + l);
				std::copy(current.begin() + l, current.begin() + mid, buffer.begin() + (l + r - mid));
				continue;
			}
			std::size_t i = l, j = mid, k = l;
			while (i < mid && j < r) {
				if (compare(value(current[j]), value(current[i]))) {
					buffer[k++] = current[j++];
					result += static_cast<std::int64_t>(mid - i);
				} else buffer[k++] = current[i++];
			}
			std::copy(current.begin() + i, current.begin() + mid, buffer.begin() + k);
			std::copy(current.begin() + j, current.begin() + r, buffer.begin() + (k + mid - i));
		}
		current.swap(buffer);
	}
	return result;
}

#endif

Back to top page