count-inv (転倒数)
(src/algorithm/count-inv.hpp)

• View this file on GitHub
• Last update: 2023-01-09 21:32:45+09:00
• Include: #include "src/algorithm/count-inv.hpp"

概要

列に対して転倒数を求めます。配列$A$の転倒数とは$i < j$かつ$A_i > A_j$を満たす順序対$(i, j)$の総数を指します。

内部実装にマージソートを用いています。

機能

long long count_inv<T>(const std::vector<T>& ins)

• insの転倒数を求めます。
• 計算量 : $O(N\log N)$
  • (insの長さを $N$ とする)

Verified with

• test/count-inv.test.cpp

Code

#pragma once

#include <vector>

namespace zawa::impl {

template <class T>
long long sort(std::vector<T>& arr, int left, int right) {
	if (right - left == 1) {
		return 0LL;
	}
	long long res = 0LL;
	int mid = left + ((right - left) >> 1);
	res += sort(arr, left, mid);
	res += sort(arr, mid, right);
	std::vector<T> fronts(arr.begin() + left, arr.begin() + mid);
	std::vector<T> backs(arr.begin() + mid, arr.begin() + right);
	int front_idx = 0, back_idx = 0;
	for (int i = left ; i < right ; i++) {
		if (front_idx < (int)fronts.size() and 
				(back_idx == (int)backs.size() or fronts[front_idx] <= backs[back_idx])) {
			arr[i] = fronts[front_idx++];
		}
		else {
			arr[i] = backs[back_idx++];
			res += mid - left - front_idx;
		}
	}
	return res;
}

} // namespace zawa

namespace zawa {

template <class T>
long long count_inv(const std::vector<T>& in) {
	std::vector arr = in;
	return impl::sort(arr, 0, (int)arr.size());
}

} // namespace zawa

#line 2 "src/algorithm/count-inv.hpp"

#include <vector>

namespace zawa::impl {

template <class T>
long long sort(std::vector<T>& arr, int left, int right) {
	if (right - left == 1) {
		return 0LL;
	}
	long long res = 0LL;
	int mid = left + ((right - left) >> 1);
	res += sort(arr, left, mid);
	res += sort(arr, mid, right);
	std::vector<T> fronts(arr.begin() + left, arr.begin() + mid);
	std::vector<T> backs(arr.begin() + mid, arr.begin() + right);
	int front_idx = 0, back_idx = 0;
	for (int i = left ; i < right ; i++) {
		if (front_idx < (int)fronts.size() and 
				(back_idx == (int)backs.size() or fronts[front_idx] <= backs[back_idx])) {
			arr[i] = fronts[front_idx++];
		}
		else {
			arr[i] = backs[back_idx++];
			res += mid - left - front_idx;
		}
	}
	return res;
}

} // namespace zawa

namespace zawa {

template <class T>
long long count_inv(const std::vector<T>& in) {
	std::vector arr = in;
	return impl::sort(arr, 0, (int)arr.size());
}

} // namespace zawa

Back to top page