結果
| 問題 |
No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
|
| コンテスト | |
| ユーザー |
 ynn
|
| 提出日時 | 2024-03-14 23:22:10 |
| 言語 | Rust (1.83.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 196 ms / 5,000 ms |
| コード長 | 56,443 bytes |
| コンパイル時間 | 22,758 ms |
| コンパイル使用メモリ | 378,312 KB |
| 実行使用メモリ | 29,972 KB |
| 最終ジャッジ日時 | 2024-09-29 23:51:29 |
| 合計ジャッジ時間 | 17,307 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
コンパイルメッセージ
warning: method `update` is never used
--> src/main.rs:460:8
|
286 | / impl<T: Copy + 'static + std::fmt::Debug, F> LazySegmentTree<T, F>
287 | | where
288 | | F: Fn(T, T) -> T,
| |_____________________- method in this implementation
...
460 | fn update(&mut self, mut k: usize, a: T) {
| ^^^^^^
|
= note: `#[warn(dead_code)]` on by default
ソースコード
//IMPORTS {{{
#![allow(unused_parens)]
#![allow(unstable_name_collisions)] //`num::Integer::div_ceil()`, `num::Integer::next_multiple_of()` etc.
use std::io::{self, Read};
#[allow(unused_imports)]
use std::{
cmp::Ordering::{self, Equal, Greater, Less},
cmp::Reverse,
collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque},
f64::consts::{FRAC_PI_2, PI},
mem::swap,
rc::Rc,
sync::atomic::{AtomicUsize, Ordering::SeqCst},
time::Instant,
};
//}}}
//MACROS {{{
//input parser
#[allow(unused_macros)]
macro_rules! collect {
($v:expr) => {{
$v.collect_scalar()
}};
($v:expr, $i:expr) => {{
$v.collect_vector($i)
}};
($v:expr, $i:expr, $j: expr) => {{
$v.collect_matrix($i, $j)
}};
}
#[allow(unused_macros)]
macro_rules! collect_step {
($v:expr, $i:expr, $j: expr) => {{
$v.collect_vector_step($i, $j)
}};
}
#[allow(unused_macros)]
macro_rules! collect_seq {
($v:expr) => {{
$v.collect_sequence()
}};
}
#[allow(unused_macros)]
macro_rules! collect_special {
($v:expr, $i:expr) => {{
$v.collect_vector_special($i)
}};
}
//debug print
#[allow(unused_macros)]
macro_rules! o {
(---) => { #[cfg(test)] println!("\u{001B}[090m{}\u{001B}[0m", "―".repeat(10)) };
($expr:literal) => { #[cfg(test)] println!("{}", $expr) };
($expr:expr) => { #[cfg(test)] println!("{} = {:?}", stringify!($expr), $expr) };
($($expr:expr),*) => { #[cfg(test)] println!($($expr),*) };
}
#[allow(unused_macros)]
macro_rules! oo {
($v:expr) => {
#[cfg(test)]
{
if ($v.is_empty()) {
println!("{} = []", stringify!($v));
} else {
println!("{} = [", stringify!($v));
$v.iter().enumerate().for_each(|(i, e)| {
println!(" {:3}: {:?}", i, e);
});
println!("]");
}
}
};
}
#[allow(unused_macros)]
macro_rules! ooo {
($v:expr) => {
#[cfg(test)]
{
if ($v.is_empty()) {
println!("{} = {{}}", stringify!($v));
} else {
println!("{} = {{", stringify!($v));
$v.iter().sorted().for_each(|(k, v)| {
println!(" {:3}: {:?}", k, v);
});
println!("}}");
}
}
};
}
//map literal, set literal
#[allow(unused_macros)]
macro_rules! map {
() => {
FxHashMap::default()
};
($($key:tt : $value:tt,)+) => {
map!($($key : $value),+)
};
($($key:tt : $value:tt),+) => {
{
let mut m = FxHashMap::default();
$(
m.insert($key, $value);
)+
m
}
};
}
#[allow(unused_macros)]
macro_rules! set {
() => {
FxHashSet::default()
};
($($value:expr,)+) => {
set!($($value),+)
};
($($value:expr),+) => {
{
let mut s = FxHashSet::default();
$(
s.insert($value);
)+
s
}
};
}
//stopwatch
//Example:
// let mut start = Instant::now();
// /* do something */
// tt!(start [, <title>]);
// /* do something */
// tt!(start [, <title>]);
#[allow(unused_macros)]
macro_rules! tt {
($t:expr) => {
#[cfg(test)]
{
println!("{}ms", $t.elapsed().as_millis());
#[allow(unused_assignments)]
{
$t = Instant::now();
}
}
};
($t:expr, $title:expr) => {
#[cfg(test)]
{
println!("{}ms ({})", $t.elapsed().as_millis(), $title);
#[allow(unused_assignments)]
{
$t = Instant::now();
}
}
};
}
//cumulative time measurement for block
//Usage: `time! {{ ... }}`, then `time_print!()`
//Bug: The value may be cumulated over multiple tests. `cargo test -- --test-threads 1` can avoid it.
#[allow(dead_code)]
static ELAPSED_TIME_NS: AtomicUsize = AtomicUsize::new(0);
#[allow(unused_macros)]
macro_rules! time {
($v:block) => {{
#[cfg(test)]
let start = Instant::now();
let ret = $v;
#[cfg(test)]
ELAPSED_TIME_NS.fetch_add(start.elapsed().as_nanos() as usize, SeqCst);
ret
}};
}
#[allow(unused_macros)]
macro_rules! time_reset {
() => {{
#[cfg(test)]
ELAPSED_TIME_NS.store(0, SeqCst);
}};
}
#[allow(unused_macros)]
macro_rules! time_print {
() => {{
#[cfg(test)]
println!("{}ms", ELAPSED_TIME_NS.load(SeqCst) / 1000 / 1000);
}};
}
//}}}
/*-------------------------------------*/
/* solve */
//LazySegmentTree {{{
//遅延セグ木
//参考: |https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b71| (非遅延セグ木)
//参考: |https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b72| (遅延セグ木)
//
//問題によっては(試した限りほとんどの問題で)、この遅延セグ木はTLEするほどに遅い
//原因は、現状の実装は任意の作用に対応しており、作用の合成も可能だが、合成をする度に作用のclosureがネストされていくためである(空間計算量の問題もあるが、ネストしすぎて作用の適用自体に時間が掛かる可能性がある)
//つまり抽象化が原因であるため、「区間加算しか来ない」や「区間更新しか来ない」といったことが分かっている場合は、以下の何れかの方法で高速化が可能である
//- `self.__compose_action()`における作用の合成を最適化する(例えば区間加算の場合はclosureのネストは不要で、`+3`作用と`+5`作用であれば新しく`+8`作用を一つ作り直せば良い)
//- より速度が求められる場合は、さらに`self.action`の型を最適化すれば良い(例えば区間加算であればclosureは不要で`Vec<Option<T>>`で十分である)
// この変更だけで16886ms -> 237msになった例がある(参考:|https://atcoder.jp/contests/abc340/submissions/51207465|)
//以下では、非遅延セグ木の実装については前提とし、重複した説明は行わない
//
//通常のセグ木(非遅延セグ木)は、以下のことができる
//- `update()`(1点更新): あるノードの値を任意の別の値に変更する
//- `fold()`(区間取得): 指定した区間における演算の累積結果を取得する
//遅延セグ木は、これに加えて以下の操作を追加でサポートする
//- 区間作用: 指定した区間に対して何らかの作用(action)を一括で適用する(「指定区間に一括で`+1`する」や「指定区間の値を全て`x`にする」など)
//
//ある区間`[l, r)`に対して作用を適用することを考えたとき、愚直に適用するとO(r - l)掛かってしまうため、以下のようにして効率化する
//1. 最下層の各ノードに即座に作用を適用する代わりに、それらの親ノードに作用を持たせる(作用を格納するための配列が追加で必要となる)
//2. あるノード`i`が持っている作用は、`i`およびその間接的または直接的な全ての子ノードにも適用されると解釈する
struct LazySegmentTree<T: Copy, F>
where
F: Fn(T, T) -> T,
{
//最下段の要素数
//これは`__original_n.next_power_of_two()`と一致(処理を簡単にするために2の累乗にする)
//木全体の構造は`self.v`のコメントを参照
n: usize,
//コンストラクタに渡された配列の要素数(`assert!()`や`Debug`トレートの実装にのみ使用)
__original_n: usize,
//セグ木の本体
//
//完全二分木であり、親ノードは二つの子ノードの値を演算した結果を持つ
//ルートノードを`0`番要素と考え、左から右へ、上から下へ、の順番でインデックスを大きくする
//
// 0
// _________ / \ __________
// / \
// 1 2
// / \ / \
// / \ / \
// 3 4 5 6
// / \ / \ / \ / \
// 7 8 9 10 11 12 13 14
//
//次のような性質を持つ
//- 要素数は`2 * n - 1`(証明: ルートノードから下に下がる度にノード数が二倍になるが、`1 + 2 + 4 + ...`は等比級数の和として計算できる)
//- 最下段の`i`番要素は全体としては`i + (n - 1)`番要素
//- 親のインデックスを`k`としたとき、子のインデックスは`2 * k + 1`および`2 * k + 2`
//- 子のインデックスが`k`であるとき、親のインデックスは`(k - 1) / 2`
v: Vec<T>,
//作用配列
//
//作用`Fn(T, usize) -> T`をノード`i`に適用するとき、次の二つが渡される
//- `v[i]`の値
//- `i`をルートノードとする部分木の最下層のノード数
//後者は、例えば作用が区間加算である場合に`a + b + c` -> `(a + x) + (b + x) + (c + x) = (a + b + c) + 3 * x`のような計算をするために必要となる(最下層のノード数が分からないと、`x`を何回加算すれば良いかが分からない)
//なお、作用の具体的な関数形は`operation`にも依存して決まる(`test_integration_test_range_sum()`と`test_integration_test_range_min()`を見比べると良くて、同じ作用でも関数形が異なっていることが分かる)
//
//既に作用`A`を持っているノードにさらに別の作用`B`が適用されるとき、`B(A(x))`のような合成関数として解釈される(時系列順に作用が適用される)
//区間加算した後に区間減算するというように、異なる作用を単一のセグ木に適用する用法にも対応している(対応するテストは`test_integration_test_range_sum()`など)
//
//どんな作用でも適用できるわけではない
//例えば「作用は区間加算で、`operation`は区間和」や「作用は区間加算で、`operation`は区間最小値」といった組み合わせは可能だが、「作用は区間加算で、`operation`は区間積」といった組み合わせには対応できない(例えば`a * b * c * d := x`における`a`, `b`, `c`, `d`は分からないが`x`だけ知っている場合(最下層の子ノードを4つ持つ親ノードの場合)に、`x`の値と区間加算`+p`という情報だけで`(a + p) * (b + p) * (c + p) * (d + p)`の値を計算できない)
//
//`Rc`を使っているのはRustの実装の都合上である(`Box<dyn Fn(T, usize) -> T>`は`Clone`トレートを実装しないため)
action: Vec<Option<Rc<dyn Fn(T, usize) -> T>>>,
//単位元
//例えば和であれば`0`、積であれば`1`、`usize`型の`max()`であれば`0`
identity_element: T,
//セグ木に載せたい二項演算を表すラムダ式
//例えば累積MAXであれば`|a, b| a.max(b)`を入力する
//
//結合法則は満たしている必要があるため、`+`や`max`といった演算は許されるが、`-`や`/`は不可
//一方で、交換法則を満たしている必要は無いため、行列の積といった演算も許される
operation: F,
}
impl<T: Copy + 'static + std::fmt::Debug, F> LazySegmentTree<T, F>
where
F: Fn(T, T) -> T,
{
fn new(l: &[T], identity_element: T, operation: F) -> Self {
let n = l.len().next_power_of_two();
let mut v = vec![identity_element; n * 2 - 1];
//最下段を更新
for i in 0..l.len() {
v[i + (n - 1)] = l[i];
}
//上に登りながら親ノードの値を計算していく
for i in (0..(n - 1)).rev() {
v[i] = (operation)(v[i * 2 + 1], v[i * 2 + 2]);
}
Self {
n,
__original_n: l.len(),
v,
action: vec![None; n * 2 - 1],
identity_element,
operation,
}
}
//ノード`i`が上から何層目にあるか
//ルートノードを第`0`層とする
fn __depth(&self, i: usize) -> u32 {
(i + 1).ilog2()
}
//ノード`i`をルートノードとする部分木の最下層のノード数
fn __number_of_children(&self, i: usize) -> usize {
let depth_max = self.__depth(2 * self.n - 1 - 1); //最下段の深さ
let depth = self.__depth(i);
2usize.pow(depth_max - depth)
}
//親ノードのインデックス
fn __parent(&self, i: usize) -> usize {
assert_ne!(0, i);
(i - 1) / 2
}
//左の子ノードのインデックス
fn __left_child(&self, i: usize) -> usize {
assert!(i * 2 + 1 < self.n * 2 - 1);
i * 2 + 1
}
//右の子ノードのインデックス
fn __right_child(&self, i: usize) -> usize {
assert!(i * 2 + 2 < self.n * 2 - 1);
i * 2 + 2
}
//ノード`i`に作用を追加する
//既に作用が存在する場合は、作用の合成を行う(単に関数の合成を行い、既存の作用が先に呼ばれるような順番とする)
fn __compose_action(&mut self, i: usize, action: Rc<dyn Fn(T, usize) -> T>) {
self.action[i] = Some(action);
}
//ノード`k`の間接的または直接的な親ノードの作用を、ルートノードから順に、ノード`k`まで伝搬させる
//
//例えば、以下のような状況を考える
//作用`P`, `Q`, `R`があり、ノード`k`が入力された場合である
//
// P
// _________ / \ __________
// / \
// Q .
// / \ / \
// / \ / \
// . . R .
// / \ / \ / \ / \
// . . . . . . . .
//
// ↑
// k
//
//このとき、`k`の間接的または直接的な親ノードは三つあるが、上にあるものから伝搬を行っていく
//ただし、あるノードの作用を伝搬させるとき、その直接的な子ノードにのみ伝搬させる(そうでないと、`k`と無関係な部分木にも潜ることになりO(N)掛かる)
//
// .
// _________ / \ __________
// / \
// P Q P
// / \ / \
// / \ / \
// . . R .
// / \ / \ / \ / \
// . . . . . . . .
//
// ↑
// k
//
// ↓
//
// .
// _________ / \ __________
// / \
// . P
// / \ / \
// / \ / \
// P Q P Q R .
// / \ / \ / \ / \
// . . . . . . . .
//
// ↑
// k
//
// ↓
//
// .
// _________ / \ __________
// / \
// . P
// / \ / \
// / \ / \
// P Q . R .
// / \ / \ / \ / \
// . . P Q P Q . . . .
//
// ↑
// k
//
fn __propagate_above(&mut self, k: usize) {
for i in (1..=self.__depth(k)).rev() {
let cur = ((k + 1) >> i) - 1; //始点`k`から`i`階層だけ登った親
if (self.action[cur].is_none()) {
continue;
}
let cur_action = self.action[cur].clone().unwrap();
//現在位置の作用を直接の子ノードに伝搬させる
//再帰的な伝搬はせず、あくまで直接の子ノードにしか伝搬させない(それで十分であるし、そうしないとO(N)掛かってしまう)
for child in [self.__left_child(cur), self.__right_child(cur)] {
self.__compose_action(child, cur_action.clone());
}
//自身の値に作用を適用した上で、作用を空にする
self.v[cur] = self.__evaluate_node(cur);
self.action[cur] = None;
}
}
//現在のノードの値を、作用の適用込みで返す
fn __evaluate_node(&self, i: usize) -> T {
if let Some(action) = &self.action[i] {
action(self.v[i], self.__number_of_children(i))
} else {
self.v[i]
}
}
//現在のノードの間接的または直接的な親ノードの値を下から上の順番に再計算する
fn __calculate_above(&mut self, mut i: usize) {
while (i > 0) {
i = self.__parent(i); //親ノードへの移動
let child_1 = self.__left_child(i);
let child_2 = self.__right_child(i);
let v_left = self.__evaluate_node(child_1);
let v_right = self.__evaluate_node(child_2);
self.v[i] = (self.operation)(v_left, v_right);
}
}
//最下段の`k`番要素を値`a`に更新する
fn update(&mut self, mut k: usize, a: T) {
assert!(k < self.__original_n);
//最下段のインデックスに変換
k += self.n - 1;
//更新対象の要素の全ての親ノードをルートノードから順に見ていき、作用を伝搬させる
self.__propagate_above(k);
self.v[k] = a;
self.action[k] = None; //作用もリセットする必要がある
//更新対象の要素から上に登りながらノードの値を再計算していく
self.__calculate_above(k);
}
//`[l, r)`範囲に作用を加える
//
//例えば、以下の区間に作用`S`を適用するクエリが来たときを考える
//
// .
// _________ / \ __________
// / \
// . .
// / \ / \
// / \ / \
// . . . .
// / \ / \ / \ / \
// . . . . . . . .
//
// |<--------------------------------------------->|
//
//このとき、以下のように可能な限り上層に作用を保存しておく
//ただし、`.`は値配列(`self.v`)の値を表しており、`. ■ S`は作用配列(`self.action`)に作用`S`が入っていることを表す(`■`は単に区切り文字)
//
// .
// _________ / \ __________
// / \
// . ■ S .
// / \ / \
// / \ / \
// . . . ■ S .
// / \ / \ / \ / \
// . . . . . . . ■ S .
//
// |<--------------------------------------------->|
//
//この状態で「親ノードの作用`S`は子ノードや孫ノードにも伝搬する」と解釈すると、この状態で区間作用が適用できていると分かる
//さらに作用`T`を加えることを考えると、
//
// .
// _________ / \ __________
// / \
// . ■ S .
// / \ / \
// / \ / \
// . . . ■ S .
// / \ / \ / \ / \
// . . . . . . . ■ S .
//
// |<----------->|
//
// ↓
//
// .
// _________ / \ __________
// / \
// . ■ S .
// / \ / \
// / \ / \
// . ■ T . . ■ S .
// / \ / \ / \ / \
// . . . ■ T . . . . ■ S .
//
// |<----------->|
//
//とできるが、これには問題があって、後々作用を伝搬させるときに、`T`を先に作用させてから`S`を作用させるような形になってしまう(作用が可換であれば良いが、それを仮定しないのであれば、時系列順に適用させなければ正しい結果にならない)
//よって、作用を追加する場合は、まず指定区間の間接的または直接的な親ノードから作用を伝搬させた上で、次に新しい作用を追加するという手順を踏む必要がある
//
// .
// _________ / \ __________
// / \
// . ■ S .
// / \ / \
// / \ / \
// . . . ■ S .
// / \ / \ / \ / \
// . . . . . . . ■ S .
//
// |<----------->|
//
// ↓
//
// .
// _________ / \ __________
// / \
// . S .
// / \ / \
// / \ / \
// . ■ S . S . ■ S .
// / \ / \ / \ / \
// . . . ■ S . ■ S . . . ■ S .
//
// |<----------->|
//
// ↓
//
// .
// _________ / \ __________
// / \
// . S .
// / \ / \
// / \ / \
// . ■ S T . S . ■ S .
// / \ / \ / \ / \
// . . . ■ S T . ■ S . . . ■ S .
//
// |<----------->|
//
//ただし、以下の表記を用いている
//- `. S`と書いたとき、値`.`に作用`S`を(遅延させずに実際に)適用した結果を表す
//- `S T`と書いたとき、作用`S`, `T`の合成を表す(適用順は`S`が先)
//
//別の注意点として、以下のように作用を追加したときを考える
//
// .
// _________ / \ __________
// / \
// . .
// / \ / \
// / \ / \
// . ■ S . . .
// / \ / \ / \ / \
// . . . ■ S . . . . .
//
// |<------------>|
//
//この区間作用の後に、以下の区間について区間取得(`fold()`)が呼ばれた場合を考える
//
// .
// _________ / \ __________
// / \
// ○ .
// / \ / \
// / \ / \
// . ■ S . . .
// / \ / \ / \ / \
// . . . ■ S . . . . .
//
// |<------------------>|
//
//このとき、`○`で表したノードの値がそのまま返り値として用いられるが、`○`よりも下部の作用が適用されていない状態になっているため、正しい答えになっていない
//ただし、`○`の下部の作用を拾ってくることをしようとすると、O(N)掛かる
//そこで、`fold()`の段階で作用を下から拾ってくる代わりに、区間作用で作用を追加した時点で作用を上部に伝搬させることを行う
//つまり、以下のように作用を追加した上で、
//
// .
// _________ / \ __________
// / \
// . .
// / \ / \
// / \ / \
// . ■ S . . .
// / \ / \ / \ / \
// . . . ■ S . . . . .
//
// |<------------>|
//
//以下の`○`のノードの値を下から順に再計算する(厳密には、三つの`○`を上から順に`A`, `B`, `C`としたとき、後述のように`B`(左端)と`C`(右端)のみ考えるため、`B`の上部を考えてから`C`の上部を考えると、「下から順に」にはなっていない。このとき、`B`から上部への伝搬計算の際には上の図で言う最下層の`S`を拾ってこれないため正しい計算になっていないが、`C`から上部への伝搬計算の際には正しく再計算されるので問題が無い)
//
// ○
// _________ / \ __________
// / \
// ○ .
// / \ / \
// / \ / \
// . ■ S ○ . .
// / \ / \ / \ / \
// . . . ■ S . . . . .
//
// |<------------>|
//
//一般には`○`のノードは区間の長さに応じて増減するが、`fold()`の場合と同様に、左端と右端の`○`のみを考えたので良い
//よって、この操作はO(log(N))で行える
fn add_action(&mut self, mut l: usize, mut r: usize, action: Rc<dyn Fn(T, usize) -> T>) {
if (l == r) {
return;
}
assert!(r <= self.__original_n);
//最下段のインデックスに変換
l += self.n - 1;
r += self.n - 1;
//区間の上部の作用を伝搬させてくる
//方法は`fold()`の場合と全く同じ
{
let (ll, rr) = self.__get_leftmost_and_rightmost_parents(l, r);
self.__propagate_above(ll);
self.__propagate_above(rr);
}
//区間に作用を追加する
//できる限り上部に作用を追加する必要があるのだが、これは(非遅延セグ木の)`fold()`の実装を参考にすれば容易に実装できる
{
let mut l = l;
let mut r = r;
while (l < r) {
if (l % 2 == 0) {
self.__compose_action(l, action.clone());
l += 1;
}
if ((r - 1) % 2 == 1) {
self.__compose_action(r - 1, action.clone());
r -= 1;
}
l /= 2;
r /= 2;
}
}
//区間に追加した作用を上部に伝搬させておく
//`update()`と同様の計算をすれば良い
let (ll, rr) = self.__get_leftmost_and_rightmost_parents(l, r);
for k in [ll, rr] {
self.__calculate_above(k);
}
}
//`fold()`のコメントにおける左端の`○`と右端の`○`の位置を特定する
//
//入力の`l`はinclusive、`r`はexclusive
//返り値についてはどちらもinclusive
//
//[実装方針1(却下)]
//参考: |https://maspypy.com/segment-tree-%e3%81%ae%e3%81%8a%e5%8b%89%e5%bc%b72|
//実装方針1は、非遅延セグ木の`fold()`を参考にする
//非遅延セグ木の`fold()`では、以下のような実装がある
// while (l < r) {
// //現在のノードが`○`であるとき、解に寄与させた上で、一つ内側に現在位置を移す
// if (l % 2 == 0) {
// v_left = (self.operation)(v_left, self.v[l]);
// l += 1;
// }
// if ((r - 1) % 2 == 1) {
// v_right = (self.operation)(self.v[r - 1], v_right);
// r -= 1;
// }
//
// //一つ上層に登る
// l /= 2;
// r /= 2;
// }
//よって、初めて`l % 2 == 0`が満たされるまで`l /= 2`を繰り返せば左端の`○`が特定できるし、右端の`○`についても同様である
// while (l % 2 != 0) {
// l /= 2;
// }
// while ((r != 0) && ((r - 1) % 2 != 1)) {
// r /= 2;
// }
// (l, r)
//ただし、これは実際には誤りである
//というのは、この実装では`l`, `r`について独立に考えているが、実際には左端の`○`の位置は`l`, `r`の両方に依存して決まるため(右端の`○`も同様)、正しい`○`の位置が計算されることはあり得ない
//実際、具体値を適当に考えてみると反例がすぐに見つかる
//なお、だからといってリンク先の非遅延セグ木の実装が誤りとは限らなくて、`__get_leftmost_and_rightmost_parents()`の結果は`__propagate_above()`に渡される形でしか使用されないため、`fold()`のコメントで書いたLCAによる証明のように考えて結果的には正しいと言える可能性はある(ただ、いずれにしても`__get_leftmost_and_rightmost_parents()`単体としては誤りである)
//
//[実装方針2(採用)]
//左端`○`の特定を考える
//1. 区間`[l, r)`内の左端のノードからボトムアップに探索を始める
//2. 親ノードに登る
//3. 現在のノードをルートノードとする部分木における最下層の子ノードの最小インデックスを`i_min`、最大インデックスを`i_max`としたとき、`[i_min, i_max]`が`[l, r)`に内包されているかを考える
// (a) 内包されていないとき、現在の直前にいたノードが左端の`○`である(登りすぎたことになった初めてのタイミング)
// (b) 内包されているとき、親ノードに登る
//ただし、`i_min`, `i_max`については次のようにして計算できる
//1. あるノード`i`があったとき、その子ノードは`2 * i + 1`および`2 * i + 2`である
//2. `i`の深さや最下層の深さは`__depth()`によりO(1)で計算できるため、`i`の層から何層降りれば最下層に到達するかもO(1)で分かる
//3. よって、`a_{n+1} = 2 * a_n + p`という数列を考えると、特性方程式を用いて一般項が`a_n = 2^n (a_0 + p) - p`と求まる(`p = 1`または`p = 2`)
// つまり、以下が成り立つ
// - `i_min = 2^(下る回数) (i + 1) - 1`
// - `i_max = 2^(下る回数) (i + 2) - 2`
//ちなみに、ルートノードから探索を開始して上記の`i_min`, `i_max`を用いてトップダウンに探索することもできそうだったが、再帰で書かないと難しそうだった
fn __get_leftmost_and_rightmost_parents(&self, l: usize, r: usize) -> (usize, usize) {
assert!(l < r);
assert!((l >= self.n - 1) && (r <= 2 * self.n - 1)); //最下層のノードが入力されること
let i_min = |i: usize| -> usize {
2usize.pow(self.__depth(2 * self.n - 1 - 1) - self.__depth(i)) * (i + 1) - 1
};
let i_max = |i: usize| -> usize {
2usize.pow(self.__depth(2 * self.n - 1 - 1) - self.__depth(i)) * (i + 2) - 2
};
let f = |start: usize| -> usize {
let mut old;
let mut i = start;
loop {
if (i == 0) {
return i;
}
old = i;
i = self.__parent(i);
let i_min = i_min(i);
let i_max = i_max(i);
if !((l <= i_min) && (i_max <= r - 1)) {
i = old;
return i;
}
}
};
(f(l), f(r - 1))
}
//最下段における`[l, r)`範囲での累積結果を求める
//
//例えば、以下の区間に対する問い合わせが来たことを考える
//
// .
// _________ / \ __________
// / \
// . .
// / \ / \
// / \ / \
// . . . .
// / \ / \ / \ / \
// . . . . . . . .
//
// |<--------------------------------------------->|
//
//このとき、返り値に寄与するノードは以下の三つの`○`である
//
// .
// _________ / \ __________
// / \
// ○ .
// / \ / \
// / \ / \
// . . ○ .
// / \ / \ / \ / \
// . . . . . . ○ .
//
// |<--------------------------------------------->|
//
//遅延セグ木の場合は`○`よりも上部に伝搬前の作用が一般に存在するため、`○`の値を累積させる前に作用の伝搬が必要となる
//ただし、全ての`○`の上部を考える必要は無くて、実は左端の`○`と右端の`○`の上部のみを考えれば、全ての`○`の上部を考えたことと同値になる(証明を言語化するのが少し難しいが、`__propagate_above()`の動きを踏まえるとこれが正しいことが分かる。例えば上の図における右端の`○`(`C`と表記)について考えたとき、右から二番目の`○`(`B`と表記)と同じく木全体の右半身に属し、かつ`B`は`C`よりも上層にある。もう少し言えば、`B`, `C`のLCAを考えたとき、`B`はLCAよりも一層だけ下の層にいるが、`__propagate_above(C)`を呼んだときにLCAは必ず通過してLCAの作用が一つ下の層に伝搬するのである)
//
//よって、以下のような流れで`fold()`は実装できる
//1. 左端と右端の`○`を特定する
//2. それらの間接的または直接的な親ノードの作用を伝搬させる
//3. 非遅延セグ木の`fold()`と同様にボトムアップにノードの値を累積させていく
fn fold(&mut self, mut l: usize, mut r: usize) -> T {
assert!(r <= self.__original_n);
//最下段のインデックスに変換
l += self.n - 1;
r += self.n - 1;
//左端の`○`と右端の`○`を特定し、その間接的または直接的な親ノードの作用を伝搬させる
{
let (ll, rr) = self.__get_leftmost_and_rightmost_parents(l, r);
self.__propagate_above(ll);
self.__propagate_above(rr);
}
let mut v_left = self.identity_element;
let mut v_right = self.identity_element;
//`l == r - 1`の場合(現在位置が範囲ではなく単一のノードである場合)もイテレートは起きる
//そのとき、`l % 2 == 0`と`(r - 1) % 2 == 1`の何れか一方のみが必ず満たされるため、現在のノードの値を累積させた上で、`l += 1`もしくは`r -= 1`により次のイテレートは抑制される
while (l < r) {
if (l % 2 == 0) {
v_left = (self.operation)(v_left, self.__evaluate_node(l));
l += 1;
}
if ((r - 1) % 2 == 1) {
v_right = (self.operation)(self.__evaluate_node(r - 1), v_right);
r -= 1;
}
l /= 2;
r /= 2;
}
(self.operation)(v_left, v_right)
}
}
impl<T: Copy + std::fmt::Debug, F> std::fmt::Debug for LazySegmentTree<T, F>
where
F: Fn(T, T) -> T,
{
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
//最下段のみが出力対象で、また、2の累乗にするための余分な要素はカットしている
write!(
f,
"{:?}",
self.v
.iter()
.skip(self.n - 1)
.take(self.__original_n)
.collect::<Vec<_>>()
)
}
}
//}}}
fn solve(n: usize, q: usize, x: Vec<usize>, l: Vec<usize>, r: Vec<usize>) -> Vec<usize> {
let mut t = LazySegmentTree::new(
&(0..n).map(|_| (0, 0)).collect::<Vec<_>>(),
(0, 0),
|a, b| (a.0 + b.0, a.1 + b.1),
);
let mut score_a = 0;
let mut score_b = 0;
for i in 0..q {
match (x[i]) {
0 => {
let (p, q) = t.fold(l[i], r[i] + 1);
if (p > q) {
score_a += p;
} else if (p < q) {
score_b += q;
}
}
1 => {
t.add_action(l[i], r[i] + 1, Rc::new(|_, num_children| (num_children, 0)));
}
2 => {
t.add_action(l[i], r[i] + 1, Rc::new(|_, num_children| (0, num_children)));
}
_ => unreachable!(),
}
}
let (p, q) = t.fold(0, n);
score_a += p;
score_b += q;
vec![score_a, score_b]
}
fn front(s: String) -> String {
let mut ip = InputParser::new(tokenize(s));
#[rustfmt::skip]
let res = solve(
collect!(ip),
collect!(ip),
collect_step!(ip, 3, 0),
collect_step!(ip, 3, 0),
collect_step!(ip, 3, 0),
);
Converter::to_string(&res, " ", " ")
}
/*-------------------------------------*/
/* tests */
#[cfg(test)]
mod tests {
//PREP {{{
use super::*;
use std::sync::atomic::{AtomicUsize, Ordering};
static CASE: AtomicUsize = AtomicUsize::new(1);
fn cmp(
#[allow(unused_variables)] input: &str,
#[allow(unused_variables)] expected: &str,
actual: &str,
) -> bool {
// #[rustfmt::skip]
// let input: Vec<usize> = input.split_whitespace().map(|e| e.parse().unwrap()).collect::<Vec<_>>();
// #[rustfmt::skip]
// let expected: Vec<isize> = expected.split_whitespace().map(|e| e.parse().unwrap()).collect::<Vec<_>>();
// #[rustfmt::skip]
// let actual: Vec<isize> = actual.split_whitespace().map(|e| e.parse().unwrap()).collect::<Vec<_>>();
// let expected = expected.parse::<f64>().unwrap();
// let actual = actual.parse::<f64>().unwrap();
// (actual - expected).abs() < 1e-6
expected == actual
}
#[allow(unused_macros)]
macro_rules! t {
($i:expr, $o:expr) => {
println!(
"\u{001B}[1;036m[case{}]\u{001B}[0m",
CASE.fetch_add(1, Ordering::SeqCst)
);
let start = Instant::now();
let actual = front($i.to_owned());
println!(
"\u{001B}[090m({:?}ms)\u{001B}[0m",
start.elapsed().as_millis()
);
let expected = $o;
if (!cmp($i, expected, &actual)) {
assert_eq!(expected, &actual);
}
};
}
//loads a test case from files
//Example: `tf!("./in_01.txt", "./out_01.txt");`
#[allow(unused_macros)]
macro_rules! tf {
($in_file:expr, $out_file:expr) => {
let files = (
String::from($in_file).replace("~", &std::env::var("HOME").unwrap()),
String::from($out_file).replace("~", &std::env::var("HOME").unwrap()),
);
let content = (
std::fs::read_to_string(files.0).unwrap(),
std::fs::read_to_string(files.1).unwrap(),
);
let trim_only = false;
if (trim_only) {
let input = content.0.trim();
let output = content.1.trim();
t!(input, output);
} else {
//This is useful when you want to remove special characters such as `^M`.
//Note, however, every space is replaced by a newline, which may be problematic.
let input = content.0.split_whitespace().join("\n");
let output = content.1.split_whitespace().join("\n");
t!(&input, &output);
}
};
}
//}}}
#[test]
// #[ignore]
fn test01() {
t!(
"5
2
1 0 3
2 2 4",
"2 3"
);
t!(
"5
3
1 0 4
2 1 3
0 4 4",
"3 3"
);
t!(
"6
6
1 1 2
2 4 5
0 2 4
2 0 3
1 1 5
0 0 5",
"10 1"
);
}
// #[test]
// // #[ignore]
// fn test02() {
// }
//`gen!()`, `choose!()`, `choose_dup!()` {{{
#[allow(unused_macros)]
macro_rules! gen {
($rng:expr, $range:expr) => {{
$rng.gen_range($range)
}};
($rng:expr, $range:expr, $i:expr) => {{
let mut l = vec![];
for _ in 0..$i {
l.push($rng.gen_range($range));
}
l
}};
}
#[allow(unused_macros)]
macro_rules! choose {
($rng:expr, $l:expr) => {{
*$l.choose(&mut $rng).unwrap()
}};
($rng:expr, $l:expr, $i:expr) => {{
assert!($i <= $l.len());
$l.choose_multiple(&mut $rng, $i)
.copied()
.collect::<Vec<_>>()
}};
}
#[allow(unused_macros)]
macro_rules! choose_dup {
($rng:expr, $l:expr, $i:expr) => {{
let mut l = Vec::with_capacity($i);
for _ in 0..$i {
l.push(*$l.choose(&mut $rng).unwrap());
}
l
}};
}
//}}}
// #[test]
// // #[ignore]
// fn test_random() {
// let mut rng = StdRng::seed_from_u64(0);
// let mut start = (std::time::Instant::now(), std::time::Instant::now());
// let mut flag = false;
// for iter in 0.. {
// // statistics {{{
// let elapsed = start.1.elapsed();
// if ((!flag && elapsed.as_millis() >= 500) || (elapsed.as_secs() >= 5)) {
// flag = true;
// o!(
// "iter: {:.1e} (avg. {:.1e}/s)",
// iter as f64,
// (iter * 1000 / start.0.elapsed().as_millis()) as f64
// );
// start.1 = std::time::Instant::now();
// }
// // }}}
//
// let n = 3;
// let x = gen!(rng, 0..10, n);
// let pp = solve1(n, x.clone());
// let qq = solve(n, x.clone());
// if (pp != qq) {
// o!(n);
// o!(x);
// assert_eq!(pp, qq);
// }
// }
// }
}
/*-------------------------------------*/
/* main */
//HELPER {{{
//consumes stdin
fn input() -> String {
let mut s: String = String::new();
io::stdin().read_to_string(&mut s).unwrap();
s
}
//splits a string into whitespace-separeted tokens
fn tokenize(s: String) -> Vec<String> {
s.split_whitespace().map(|e| e.to_owned()).collect()
}
//InputParser {{{
struct InputParser {
v: Vec<String>,
num_collected: usize,
//for `collect_step!()`
step_count: usize,
step_collected_count: usize,
}
impl InputParser {
fn new(v: Vec<String>) -> Self {
Self {
v,
num_collected: 0,
step_count: 0,
step_collected_count: 0,
}
}
#[allow(dead_code)]
fn collect_scalar<T: std::str::FromStr>(&mut self) -> T
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
let ret = self.v[self.num_collected].parse().unwrap();
self.num_collected += 1;
ret
}
#[allow(dead_code)]
fn collect_vector<T: std::str::FromStr>(&mut self, length: usize) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
let ret = self
.v
.iter()
.skip(self.num_collected)
.take(if (length != 0) { length } else { usize::MAX })
.map(|e| e.parse::<T>().unwrap())
.collect::<Vec<_>>();
self.num_collected += length;
ret
}
#[allow(dead_code)]
fn collect_vector_step<T: std::str::FromStr>(&mut self, step: usize, length: usize) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
let is_first_call = self.step_count == 0; //when the first call of a series of `collect_step!()` calls
if (is_first_call) {
self.step_count = step; //starts countdown
}
let num_skip = self.num_collected + (step - self.step_count);
let ret = self
.v
.iter()
.skip(num_skip)
.step_by(step)
.take(if (length != 0) { length } else { usize::MAX })
.map(|e| e.parse::<T>().unwrap())
.collect::<Vec<_>>();
self.step_count -= 1;
//lazily increases `self.num_collected` when the last call of a series of `collect_step!()` calls completed
if (self.step_count == 0) {
self.num_collected += step * length;
}
//asserts each call collects the same number of elements
if (is_first_call) {
self.step_collected_count = ret.len();
} else {
assert_eq!(ret.len(), self.step_collected_count);
}
ret
}
//parses a single string `abc` as `['a', 'b', 'c']`
#[allow(dead_code)]
fn collect_sequence<T: std::str::FromStr>(&mut self) -> Vec<T>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
let ret = self.v[self.num_collected]
.chars()
.map(|e| e.to_string().parse::<T>().unwrap())
.collect();
self.num_collected += 1;
ret
}
//parses a special matrix, whose number of columns varies by each row:
// L1 a_{1,1} a_{1,2} ... a_{1,L1}
// L2 a_{2,1} a_{2,2} ... a_{2,L2}
// ...
#[allow(dead_code)]
fn collect_vector_special<T: std::str::FromStr>(
&mut self,
n: usize, //number of `L_i`s above
) -> Vec<Vec<T>>
where
<T as std::str::FromStr>::Err: std::fmt::Debug,
{
let mut ret = vec![];
let mut iter = 0;
loop {
iter += 1;
if (((n == 0) && (self.num_collected == self.v.len())) || ((n != 0) && (iter > n))) {
break;
}
let l = self.v[self.num_collected].parse().unwrap();
ret.push(
self.v
.iter()
.skip(self.num_collected + 1)
.take(l)
.map(|e| e.parse::<T>().unwrap())
.collect::<Vec<_>>(),
);
self.num_collected += 1 + l;
}
ret
}
}
//}}}
//Converter {{{
struct Converter;
impl Converter {
fn __convert_scalar<T: ToString>(v: &T, _: &str, _: &str) -> String {
v.to_string()
}
#[allow(clippy::ptr_arg)]
fn __convert_vector<T: ToString>(v: &Vec<T>, _: &str, line_sep: &str) -> String {
v.iter()
.map(|e| e.to_string())
.collect::<Vec<_>>()
.join(line_sep)
}
#[allow(clippy::ptr_arg)]
fn __convert_matrix<T: ToString>(v: &Vec<Vec<T>>, element_sep: &str, line_sep: &str) -> String {
v.iter()
.map(|e| Self::__convert_vector(e, element_sep, element_sep))
.collect::<Vec<_>>()
.join(line_sep)
}
fn __convert_vecdeque<T: ToString>(v: &VecDeque<T>, _: &str, line_sep: &str) -> String {
v.iter()
.map(|e| e.to_string())
.collect::<Vec<_>>()
.join(line_sep)
}
fn __convert_tuple_of_two<T1: ToString, T2: ToString>(
v: &(T1, T2),
_: &str,
line_sep: &str,
) -> String {
format!("{}{}{}", v.0.to_string(), line_sep, v.1.to_string())
}
fn __convert_tuple_of_three<T1: ToString, T2: ToString, T3: ToString>(
v: &(T1, T2, T3),
_: &str,
line_sep: &str,
) -> String {
format!(
"{}{}{}{}{}",
v.0.to_string(),
line_sep,
v.1.to_string(),
line_sep,
v.2.to_string()
)
}
fn to_string(v: &dyn std::any::Any, element_sep: &str, line_sep: &str) -> String {
//scalar
if let Some(e) = v.downcast_ref::<usize>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<isize>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<f64>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<&'static str>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<String>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<char>() {
return Self::__convert_scalar(e, element_sep, line_sep);
}
//bool
if let Some(e) = v.downcast_ref::<bool>() {
if (*e) {
return "Yes".to_owned();
} else {
return "No".to_owned();
}
}
//Vec<T>
if let Some(e) = v.downcast_ref::<Vec<usize>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<isize>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<f64>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<&'static str>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<String>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<char>>() {
return Self::__convert_vector(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<bool>>() {
return e
.iter()
.map(|&e| if (e) { "Yes" } else { "No" })
.collect::<Vec<_>>()
.join(line_sep);
}
//Vec<Vec<T>>
if let Some(e) = v.downcast_ref::<Vec<Vec<usize>>>() {
return Self::__convert_matrix(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<Vec<isize>>>() {
return Self::__convert_matrix(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<Vec<f64>>>() {
return Self::__convert_matrix(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<Vec<Vec<char>>>() {
return Self::__convert_matrix(e, element_sep, line_sep);
}
//VecDeque<T>
if let Some(e) = v.downcast_ref::<VecDeque<usize>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<VecDeque<isize>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<VecDeque<f64>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<VecDeque<&'static str>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<VecDeque<String>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<VecDeque<char>>() {
return Self::__convert_vecdeque(e, element_sep, line_sep);
}
//tuple (2 elements)
if let Some(e) = v.downcast_ref::<(usize, usize)>() {
return Self::__convert_tuple_of_two(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<(isize, isize)>() {
return Self::__convert_tuple_of_two(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<(f64, f64)>() {
return Self::__convert_tuple_of_two(e, element_sep, line_sep);
}
//tuple (3 elements)
if let Some(e) = v.downcast_ref::<(usize, usize, usize)>() {
return Self::__convert_tuple_of_three(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<(isize, isize, isize)>() {
return Self::__convert_tuple_of_three(e, element_sep, line_sep);
}
if let Some(e) = v.downcast_ref::<(f64, f64, f64)>() {
return Self::__convert_tuple_of_three(e, element_sep, line_sep);
}
unimplemented!();
}
}
//}}}
fn main() {
let output: String = front(input());
println!("{}", output);
}
//}}}
/*-------------------------------------*/