haar_lib/algebra/
max_contiguous_true.rs

1//! `bool`値列の結合による、連続する`true`列の最大長
2//!
3//! # Problems
4//! - <https://codeforces.com/contest/484/problem/E>
5
6pub use crate::algebra::traits::*;
7use crate::impl_algebra;
8
9use std::cmp::max;
10
11/// 連続する`true`列の最大長を管理する。
12#[derive(Clone, Copy, Default, Debug, PartialEq, Eq, Hash)]
13pub struct MaxContiguousTrue {
14    /// 最大連続長
15    pub count: usize,
16    /// 左側最大連続長
17    pub left: usize,
18    /// 右側最大連続長
19    pub right: usize,
20    /// 区間長
21    pub length: usize,
22}
23
24impl MaxContiguousTrue {
25    /// `value`を値にもつ`MaxContiguousTrue`を生成する。
26    pub fn new(value: bool) -> Self {
27        let value = if value { 1 } else { 0 };
28        Self {
29            count: value,
30            left: value,
31            right: value,
32            length: 1,
33        }
34    }
35
36    /// `MaxContiguousTrue`を合成する。
37    pub fn compose(self, b: Self) -> Self {
38        let a = self;
39        let count = max(a.count, b.count).max(a.right + b.left);
40        let left = if a.count == a.length {
41            a.count + b.left
42        } else {
43            a.left
44        };
45        let right = if b.count == b.length {
46            b.count + a.right
47        } else {
48            b.right
49        };
50        let length = a.length + b.length;
51
52        Self {
53            count,
54            left,
55            right,
56            length,
57        }
58    }
59}
60
61/// [`MaxContiguousTrue`]の合成
62#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
63pub struct Composition;
64
65impl_algebra!(
66    Composition;
67    set: MaxContiguousTrue;
68    op: |_, a: Self::Element, b: Self::Element| a.compose(b);
69    id: |_| MaxContiguousTrue { count: 0, left: 0, right: 0, length: 0 };
70    assoc;
71);
haar_lib/algebra/max_contiguous_true.rs

haar_lib/algebra/
max_contiguous_true.rs
