decomposable/
lib.rs

1//! 分解可能なクエリ。
2//!
3//! ## Preliminaries
4//!
5//! 集合 $`S\subseteq U`$ と要素 $`x\in U`$ に関する問題 $`Q_S(x)`$ を考える。
6//! $`S\cup T`$ に対する問題を解くにあたって、何らかの二項演算 $`\square`$ が存在して
7//! ```math
8//! Q_{S\cup T}(x) = Q_S(x) \mathop{\square} Q_T(x)
9//! ```
10//! と書けるとき、問題 $`Q`$ は *decomposable* であるという。
11//!
12//! ## Theorems
13//!
14//! 二種類のクエリを考える。
15//!
16//! - $`x`$ が与えられ、$`S \xgets{\cup} \{x\}`$ で更新する。
17//! - $`x`$ が与えられ、$`Q_S(x)`$ を出力する。
18//!
19//! $`Q_S(x)`$ が $`\angled{f(|S|), g(|S|)}`$ 時間で解けるとき、$`n`$ 個のクエリを $`O((f(n) + n\cdot g(n))\log(n))`$
20//! 時間でオンライン処理できる。
21//! ただし、$`f(n)\in n^{\Omega(1)}`$, $`g(n)\in n^{o(1)}`$ とし、$`\square`$ の計算も $`O(g(n))`$ 時間でできるとする。
22//!
23//! たとえば、$`Q_S(x)`$ が $`\angled{O(|S|\log(|S|)), O(\log(|S|))}`$ 時間で解けるなら、$`n`$ 個のクエリを $`O(n\log(n)^2)`$ 時間で処理できる。
24//!
25//! ## Ideas
26//!
27//! $`i`$ 番目の更新クエリの値を $`x_i`$ として、次のようなセグ木をイメージする。
28//!
29//! - $`i`$ 番目の葉に $`\{x_i\}`$ を持つ。
30//! - 子が $`S_L`$, $`S_R`$ を持っている頂点は $`S_L\cup S_R`$ を持つ。
31//! - $`S`$ を持つ頂点では $`Q_S`$ のためのデータ構造を保持する。
32//!
33//! 更新クエリを $`k`$ 個処理している状態では、$`[0\lldot k)`$ をカバーする区間にあるデータ構造を用いて各々を処理し、$`\square`$ で合成する。
34//!
35//! 実際にはこのセグ木の各ノードは更新せず、また各ノードを陽に持っておく必要もない。
36//! 次の擬似コードに示すようにして、高々 $`\log_2(n)`$ 個のデータ構造を保持しておけばよい。
37//!
38//! `meld` の際には、`other` の各要素を直接 `self` に追加してもよいし、一旦 `.into_iter()`
39//! のようなことをしてから再構築してもよい。
40//!
41//! ```
42//! enum Query<T> {
43//!     Union(T),
44//!     Search(T),
45//! }
46//! use Query::*;
47//! let qs = Vec::<Query<()>>::new();
48//!
49//! struct Ds<T> {
50//!     // ...
51//! #   _phd: std::marker::PhantomData<T>,
52//! }
53//! impl<T> Ds<T> {
54//!     pub fn singleton(elt: T) -> Self {
55//!         // ...
56//! #       Self { _phd: std::marker::PhantomData }
57//!     }
58//!     pub fn search<U>(&self, elt: &T) -> U {
59//!         // ...
60//! #       unimplemented!()
61//!     }
62//!     pub fn meld(&mut self, other: Self) {
63//!         // ...
64//!     }
65//! }
66//! # let id = ();
67//! # fn compose(_: (), _: ()) {}
68//!
69//! let mut clx = vec![];
70//! let mut count = 0_usize;
71//! for q in qs {
72//!     match q {
73//!         Union(x) => {
74//!             count += 1;
75//!             clx.push(Ds::singleton(x));
76//!             for _ in 0..count.trailing_zeros() {
77//!                 let tmp = clx.pop().unwrap();
78//!                 clx.last_mut().unwrap().meld(tmp);
79//!             }
80//!         }
81//!         Search(x) => {
82//!             let _ = clx.iter().map(|si| si.search(&x)).fold(id, compose);
83//!         }
84//!     }
85//! }
86//! ```
87//!
88//! ## References
89//!
90//! - <https://erikdemaine.org/papers/Retroactive_TALG/paper.pdf>
91//!     - 命名を参考にした。
92//! - <https://atcoder.jp/contests/abc244/submissions/30254752>
93//!     - 実装を参考にした。
decomposable/lib.rs

decomposable/
lib.rs
