区間の k 番目の値（クエリ一括処理）

data_structure/offline_range_kth_smallest.hpp · GitHub で見る

共通ページ

#include "lib/data_structure/offline_range_kth_smallest.hpp"

std::vector<int> a{3, 1, 4, 1, 5};
std::vector<std::array<int, 3>> queries{
	{0, 5, 2},
	{1, 4, 1},
	{2, 5, 0}
};
auto answer = offline_range_kth_smallest(a, queries); // {3, 1, 1}

操作	内容・返り値
offline_range_kth_smallest(values,queries)	各 {l,r,k} について、values[l,r) の小さい方から 0 始まりで k 番目の値を、問い合わせと同じ順の vector<T> で返す

values は vector<T>、queries は span<const array<int,3>> です。vector<array<int,3>> をそのまま渡せます。元の列と問い合わせは変更しません。

列長を \(N\) として、各問い合わせは \(0\le l<r\le N\)、\(0\le k<r-l\) を満たすものとします。列長・問い合わせ数は INT_MAX 以下です。空の問い合わせ列には空の vector を返します。

T はコピーと大小・等値比較が可能な型とします。整数・文字列などに対応します。問い合わせを一件ずつ処理する場合は Wavelet Matrix を使えます。

列長を \(N\)、問い合わせ数を \(Q\)、異なる値の数を \(\sigma\) とし、比較・コピーを定数時間とします。64 bit 以下の整数列では \(O((N+Q)\log\sigma)\) 時間、それ以外の型では \(O(N\log N+Q\log\sigma)\) 時間、追加空間は \(O(N+Q)\) です。値が一種類以下の場合は \(O(N+Q)\) 時間です。

依存ライブラリ

• 区間順位の一括処理（補助部品）
• Wavelet Matrix の座標圧縮

検証コード

• test/offline_range_kth_smallest.test.cpp

コード

#ifndef OFFLINE_RANGE_KTH_SMALLEST_HPP
#define OFFLINE_RANGE_KTH_SMALLEST_HPP

#include "../components/offline_range_kth.hpp"
#include "../components/wavelet_compression.hpp"
#include <array>
#include <cassert>
#include <limits>
#include <span>
#include <vector>

template <class T>
std::vector<T> offline_range_kth_smallest(const std::vector<T> &values, std::span<const std::array<int, 3>> queries) {
	assert(values.size() <= std::size_t(std::numeric_limits<int>::max()) && queries.size() <= std::size_t(std::numeric_limits<int>::max()));
	if (queries.empty()) return {};
	offline_range_kth_detail::Frontier frontier(queries.size());
	for (std::size_t i = 0; i < queries.size(); ++i) {
		auto [l, r, k] = queries[i];
		assert(0 <= l && l < r && std::size_t(r) <= values.size() && 0 <= k && k < r - l);
		frontier.left[i] = unsigned(l); frontier.right[i] = unsigned(r); frontier.rank[i] = unsigned(k);
	}
	std::vector<T> sorted;
	std::vector<int> positions, offsets;
	int ordered = 0;
	auto codes = wavelet_detail::compress<T, false>(values, sorted, ordered, positions, offsets);
	unsigned bits = std::bit_width(unsigned(sorted.size() - 1));
	if (bits && !ordered) offline_range_kth_detail::run(frontier, std::move(codes), bits);
	std::vector<T> result;
	result.reserve(queries.size());
	for (std::size_t i = 0; i < queries.size(); ++i) {
		if (ordered) {
			auto [l, r, k] = queries[i];
			result.push_back(values[ordered > 0 ? l + k : r - 1 - k]);
		} else result.push_back(sorted[frontier.answer[i]]);
	}
	return result;
}

#endif

Back to top page