Range LIS Query（区間の最長増加部分列）

data_structure/range_lis_query.hpp · GitHub で見る

共通ページ

変更のない列に対して、半開区間 [l,r) の最長増加部分列の長さを求めます。問い合わせは構築後に順次指定でき、順列以外の列や重複する値にも対応します。

#include "lib/data_structure/range_lis_query.hpp"

std::vector<int> a{3, 1, 2, 2, 4};
RangeLISQuery<> tree(a);
int x = tree.query(0, 5); // 3: 1, 2, 4
int y = tree.query(1, 4); // 2: 1, 2
int z = tree.query(2, 2); // 0

RangeLISQuery<false> weak(a);
int w = weak.query(0, 5); // 4: 1, 2, 2, 4

RangeLISQuery<> decreasing(a, std::greater<>{});
int d = decreasing.query(0, 5); // 2: 3, 1

既定は狭義増加です。RangeLISQuery<false> は等しい値を続けて選べる広義増加を求めます。比較関数には厳密弱順序を指定します。狭義では compare(x,y)、広義では !compare(y,x) を満たす順に選びます。

操作	内容・返り値	計算量
RangeLISQuery<Strict=true>()	空の列を作る	\(O(1)\)
RangeLISQuery<Strict>(a,compare=std::less<>{})	列 a から構築する	\(O(n\log^2 n)\)
build(a,compare=std::less<>{})	列と比較を指定して構築し直す	\(O(n\log^2 n)\)
query(l,r) const	[l,r) の最長増加部分列の長さを int で返す	\(O(\log n)\)
size() / empty()	列の長さ / 空列かどうか	\(O(1)\)
clear()	空列に戻す	\(O(n)\)
swap(other)	同じ Strict の構造と内容を交換する	\(O(1)\)

a には const でサイズ取得とランダムアクセスができる範囲を渡します。vector・array・C 配列・span・deque・string_view などを利用できます。要素のコピーや値の加減算は不要で、比較できれば使えます。元の列を変更・破棄しても、構築済みの答えには影響しません。

区間は 0 <= l <= r <= size()、列の長さは INT_MAX 以下とします。空の列や空区間の答えは 0 です。部分列そのものの復元や、構築後の要素更新には対応しません。列全体の長さや復元だけが必要な場合は LIS を利用できます。

参考: Library Checker: Static Range LIS Query、Tiskin: Semi-local string comparison。

列の長さを \(n\) とし、比較を定数時間とすると、前計算は \(O(n\log^2 n)\) 時間、問い合わせは \(O(\log n)\) 時間・\(O(1)\) 追加空間です。保持空間は \(O(n\log n)\) bit、前計算の作業領域は \(O(n)\) word です。

依存ライブラリ

• Quad Bit Vector
• Range LIS の前計算

検証コード

• test/range_lis_query.test.cpp

コード

#ifndef RANGE_LIS_QUERY_HPP
#define RANGE_LIS_QUERY_HPP

#include "../components/quad_bit_vector.hpp"
#include "../components/range_lis.hpp"
#include <algorithm>
#include <array>
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <limits>
#include <numeric>
#include <ranges>
#include <utility>
#include <vector>

template <bool Strict = true>
class RangeLISQuery {
	int n = 0;
	std::vector<QuadBitVector> bits;
	std::vector<std::array<int, 4>> offsets;
	[[gnu::always_inline]] int query_impl(int l, int r) const {
		int length = r - l, removed = 0;
		unsigned upper = unsigned(r);
		for (int level = 0; level < int(bits.size()) && l < r; ++level) {
			int digit = (upper >> (2 * (int(bits.size()) - 1 - level))) & 3;
			const auto &row = bits[level];
			removed += row.below(r, digit) - row.below(l, digit);
			l = offsets[level][digit] + row.rank(l, digit);
			r = offsets[level][digit] + row.rank(r, digit);
		}
		return length - removed;
	}
#if defined(__x86_64__) || defined(__i386__)
	__attribute__((target("popcnt"))) int query_popcnt(int l, int r) const { return query_impl(l, r); }
#endif

public:
	RangeLISQuery() = default;
	template <class Range, class Compare = std::less<>>
		requires std::ranges::random_access_range<const Range> && std::ranges::sized_range<const Range>
	explicit RangeLISQuery(const Range &values, Compare compare = {}) { build(values, std::move(compare)); }
	RangeLISQuery(const RangeLISQuery &) = default;
	RangeLISQuery &operator=(const RangeLISQuery &) = default;
	RangeLISQuery(RangeLISQuery &&other) noexcept { swap(other); }
	RangeLISQuery &operator=(RangeLISQuery &&other) noexcept {
		if (this != &other) {
			RangeLISQuery replacement(std::move(other));
			swap(replacement);
		}
		return *this;
	}
	void swap(RangeLISQuery &other) noexcept {
		std::swap(n, other.n);
		bits.swap(other.bits);
		offsets.swap(other.offsets);
	}
	int size() const { return n; }
	bool empty() const { return n == 0; }
	void clear() { n = 0; bits.clear(); offsets.clear(); }
	template <class Range, class Compare = std::less<>>
		requires std::ranges::random_access_range<const Range> && std::ranges::sized_range<const Range>
	void build(const Range &values, Compare compare = {}) {
		assert(std::ranges::size(values) <= std::size_t(std::numeric_limits<int>::max()));
		n = int(std::ranges::size(values));
		bits.clear();
		offsets.clear();
		if (!n) return;
		auto first = std::ranges::begin(values);
		std::vector<int> order(n), permutation(n);
		std::iota(order.begin(), order.end(), 0);
		std::sort(order.begin(), order.end(), [&](int a, int b) {
			if (compare(first[a], first[b])) return true;
			if (compare(first[b], first[a])) return false;
			if constexpr (Strict) return a > b;
			else return a < b;
		});
		for (int i = 0; i < n; ++i) permutation[order[i]] = i;
		auto endpoints = range_lis_detail::seaweed(permutation);
		std::vector<std::uint32_t> current(n), next(n);
		for (int i = 0; i < n; ++i) current[i] = endpoints[i] < 0 ? unsigned(n) : unsigned(endpoints[i]);
		int levels = (std::bit_width(unsigned(n)) + 1) / 2;
		bits.reserve(levels);
		offsets.resize(levels);
		for (int level = 0; level < levels; ++level) {
			int shift = 2 * (levels - 1 - level);
			auto &row = bits.emplace_back(n);
			row.build(current, shift);
			auto counts = row.ranks(n);
			for (int digit = 1; digit < 4; ++digit) offsets[level][digit] = offsets[level][digit - 1] + counts[digit - 1];
			if (level + 1 == levels) break;
			auto positions = offsets[level];
			for (auto value : current) next[positions[(value >> shift) & 3]++] = value;
			current.swap(next);
		}
	}
	int query(int l, int r) const {
		assert(0 <= l && l <= r && r <= n);
		if (r - l <= 1) return r - l;
#if defined(__x86_64__) || defined(__i386__)
		static const bool hardware = __builtin_cpu_supports("popcnt");
		if (hardware) return query_popcnt(l, r);
#endif
		return query_impl(l, r);
	}
};

#endif

Back to top page