オフラインの時間区間処理

components/offline_time_segments.hpp · GitHub で見る

共通ページ

各操作が有効な半開区間 [left,right) を登録し、snapshot と rollback を持つ状態で時刻順に処理します。オフライン動的連結性の内部で使う部品です。

#include "lib/components/offline_time_segments.hpp"
#include "lib/data_structure/rollback_union_find.hpp"
#include <cassert>
#include <utility>
#include <vector>

int main() {
	std::vector<std::pair<int,int>> edges = { {0, 1}, {1, 2} };
	OfflineTimeSegments timeline(3, { {0, 2, 0}, {1, 3, 1} });
	RollbackUnionFind uf(3);
	timeline.run(uf, [&](RollbackUnionFind &state, int id) {
		state.merge(edges[id].first, edges[id].second);
	}, [&](int time, const RollbackUnionFind &state) {
		assert(state.same(0, 2) == (time == 1));
	});
	assert(uf.component_count() == 3);
}

操作・型	内容・返り値	計算量
Interval	int left, right, item。item は利用者が決める操作 ID	\(O(1)\)
OfflineTimeSegments(times, intervals)	時刻数と有効区間から構築	\(O(T+I\log T)\)
size() / entry_count()	時刻数／時間セグメント木に置いた操作 ID の総数	\(O(1)\)
run(state,apply,visit)	有効な操作を適用し、各時刻に問い合わせる。最後は開始時の状態へ戻す	\(O(T+K)\) 回の状態操作

times は0以上で、各区間は 0 <= left <= right <= times としてください。空区間は無視します。同じ ID の複数登録も別の操作として適用します。時刻数0ではコールバックを呼びません。

state.snapshot() が現在位置を返し、state.rollback(saved) がそこへ戻すことが必要です。apply(state,item) は操作を適用し、visit(time,const_state) はその時刻の問い合わせを処理します。visit は0から times-1 まで必ず昇順に1回ずつ呼びます。visit から snapshot が管理する状態を変更しないでください。

同じ時刻に有効な操作の適用順は保証しません。適用順によらず問い合わせの答えが一致する用途に使ってください。外部データを変更する場合、その復元も state.rollback で行います。コールバックでこの時間区間オブジェクトを変更しないでください。

各セグメントの操作 ID を1本の配列へまとめます。要素数の集計・累積和の後、同じ配列の開始位置を使って格納するため、書き込み用の位置配列は別に作りません。DFS の再帰の深さは \(O(\log T)\) です。

時刻数を \(T\)、区間数を \(I\)、格納した操作 ID の総数を \(K=O(I\log T)\) とします。構築は \(O(T+I\log T)\) 時間、空間は \(O(T+K)\) です。run は \(O(T+K)\) 回の操作を行い、apply・snapshot・rollback・visit の実際のコストは別に加算します。追加スタックは \(O(\log T)\) です。空の場合や長さ1の場合にも定数時間かかります。

検証コード

• test/offline_dynamic_connectivity.test.cpp

コード

#ifndef OFFLINE_TIME_SEGMENTS_HPP
#define OFFLINE_TIME_SEGMENTS_HPP

#include <bit>
#include <cassert>
#include <cstddef>
#include <utility>
#include <vector>

class OfflineTimeSegments {
	int n_;
	std::size_t base_;
	std::vector<std::size_t> offset_;
	std::vector<int> items_;

  public:
	struct Interval { int left, right, item; };
	OfflineTimeSegments(int n, const std::vector<Interval> &intervals) : n_(n), base_(1) {
		assert(n >= 0);
		if (!n || intervals.empty()) return;
		base_ = std::bit_ceil(static_cast<std::size_t>(n));
		offset_.resize(base_ * 2 + 1);
		auto cover = [&](const Interval &interval, auto &&visit) {
			assert(0 <= interval.left && interval.left <= interval.right && interval.right <= n);
			for (std::size_t l = base_ + interval.left, r = base_ + interval.right; l < r; l >>= 1, r >>= 1) {
				if (l & 1) visit(l++);
				if (r & 1) visit(--r);
			}
		};
		for (const auto &interval : intervals) cover(interval, [&](std::size_t v) { ++offset_[v]; });
		for (std::size_t v = 1; v < offset_.size(); ++v) offset_[v] += offset_[v - 1];
		items_.resize(offset_.back());
		for (const auto &interval : intervals)
			cover(interval, [&](std::size_t v) { items_[--offset_[v]] = interval.item; });
	}
	int size() const { return n_; }
	std::size_t entry_count() const { return items_.size(); }
	template <class State, class Apply, class Visit>
	void run(State &state, Apply &&apply, Visit &&visit) const {
		if (!n_) return;
		if (items_.empty()) {
			for (int t = 0; t < n_; ++t) visit(t, std::as_const(state));
			return;
		}
		auto dfs = [&](auto &&self, std::size_t v, std::size_t l, std::size_t r) -> void {
			auto saved = state.snapshot();
			for (std::size_t i = offset_[v]; i < offset_[v + 1]; ++i) apply(state, items_[i]);
			if (r - l == 1) visit(static_cast<int>(l), std::as_const(state));
			else {
				std::size_t m = (l + r) / 2;
				self(self, v * 2, l, m);
				if (m < static_cast<std::size_t>(n_)) self(self, v * 2 + 1, m, r);
			}
			state.rollback(saved);
		};
		dfs(dfs, 1, 0, base_);
	}
};

#endif

Back to top page