Mod of Linear の Prefix Minimum の内部走査

components/mod_linear_prefix_min.hpp · GitHub で見る

共通ページ

操作	内容・返り値	計算量
mod_linear_detail::prefix_min<U>(n,m,a,b,emit)	更新点を圧縮し、各区間で emit(x,y,dx,dy,count) を呼ぶ	\(O(\log m)\)

math/prefix_min_of_mod_of_linear.hpp が使う、整数幅に応じた内部処理です。通常は公開側を使用します。

mod_linear_detail::prefix_min<U>(n, m, a, b, emit) は、U を std::uint32_t または std::uint64_t とし、\(1\le n\le m\)、\(m>0\)、\(0\le a,b<m\) を前提にします。 emit(x, y, dx, dy, count) を更新点の等差数列ごとに呼びます。各引数は U で、区間の意味は公開側と同じです。

時間 \(O(\log m)\)、追加空間 \(O(1)\) です。コールバック1回を \(O(1)\) とします。

検証コード

• test/prefix_min_of_mod_of_linear.test.cpp

コード

#ifndef MOD_LINEAR_PREFIX_MIN_HPP
#define MOD_LINEAR_PREFIX_MIN_HPP

#include <cstdint>
#include <type_traits>

namespace mod_linear_detail {
template <class U, class Emit>
void prefix_min(U n, U m, U a, U b, Emit &&emit) {
	using W = std::conditional_t<(sizeof(U) <= 4), std::uint64_t, __uint128_t>;
	bool first = true;
	if (a && b && n > 1) {
		U p = m - a, q = a, sp = 1, sq = 1, x = 0, remaining = n - 1;
		for (;;) {
			if (p <= b) {
				U k = b / p;
				bool final = W(k) * sp > remaining;
				if (final) k = remaining / sp;
				if (k) {
					if (first) emit(U(0), b, sp, p, U(k + 1));
					else emit(U(x + sp), U(b - p), sp, p, k);
					first = false;
					x += k * sp;
					b -= k * p;
					remaining -= k * sp;
				}
				if (final || !b) break;
			}
			if (sp > remaining || sq > remaining - sp) break;
			if (p > q) {
				U k = (p - b - 1) / q + 1, d = k * q;
				if (d == p) break;
				if (d > p) --k;
				sp += k * sq;
				if (sp > remaining) break;
				p -= k * q;
			} else {
				U k = q / p;
				q %= p;
				if (!q) break;
				sq += k * sp;
			}
		}
	}
	if (first) emit(U(0), b, U(0), U(0), U(1));
}
}

#endif

Back to top page