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)]
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
37impl_algebra!(
38    MaxContiguousTrue;
39    op: |a: Self, b: Self| {
40        let count = max(a.count, b.count).max(a.right + b.left);
41        let left = if a.count == a.length {
42            a.count + b.left
43        } else {
44            a.left
45        };
46        let right = if b.count == b.length {
47            b.count + a.right
48        } else {
49            b.right
50        };
51        let length = a.length + b.length;
52
53        Self {
54            count, left, right, length
55        }
56    };
57    id: Self { count: 0, left: 0, right: 0, length: 0 };
58    assoc;
59);
haar_lib/algebra/max_contiguous_true.rs

haar_lib/algebra/
max_contiguous_true.rs
