haar_lib/algebra/
max_contiguous.rs

1//! 列の中で同じ値が連続する最大長
2//!
3//! # Problems
4//! - <https://atcoder.jp/contests/abc415/tasks/abc415_f>
5
6use std::marker::PhantomData;
7
8use crate::algebra::traits::*;
9use crate::impl_algebra;
10
11/// 同じ値が連続する最大長を管理する。
12#[derive(Clone, Debug, PartialEq, Eq, Hash)]
13pub struct MaxContiguous<T> {
14    /// 最大連続長と値
15    pub max: (usize, T),
16    /// 左端からの最大連続長と値
17    pub left: (usize, T),
18    /// 右端からの最大連続長と値
19    pub right: (usize, T),
20    /// 列の長さ
21    pub length: usize,
22}
23
24impl<T: Copy + Eq> MaxContiguous<T> {
25    /// 値`value`をただ一つだけもつ列。
26    pub fn unit(value: T) -> Self {
27        Self {
28            max: (1, value),
29            left: (1, value),
30            right: (1, value),
31            length: 1,
32        }
33    }
34
35    /// `MaxContiguous`を合成する。
36    pub fn compose(self, b: Self) -> Self {
37        let a = self;
38        let max = max(max(a.max, b.max), join(a.right, b.left));
39
40        let left = if a.left.0 == a.length && a.left.1 == b.left.1 {
41            (a.left.0 + b.left.0, a.left.1)
42        } else {
43            a.left
44        };
45
46        let right = if b.right.0 == b.length && a.right.1 == b.right.1 {
47            (a.right.0 + b.right.0, b.right.1)
48        } else {
49            b.right
50        };
51
52        let length = a.length + b.length;
53
54        Self {
55            max,
56            left,
57            right,
58            length,
59        }
60    }
61}
62
63fn max<T>(a: (usize, T), b: (usize, T)) -> (usize, T) {
64    if a.0 >= b.0 {
65        a
66    } else {
67        b
68    }
69}
70
71fn join<T: Eq>(a: (usize, T), b: (usize, T)) -> (usize, T) {
72    if a.1 == b.1 {
73        (a.0 + b.0, a.1)
74    } else {
75        max(a, b)
76    }
77}
78
79/// [`MaxContiguous`]の合成
80#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash)]
81pub struct Composition<T>(PhantomData<T>);
82impl<T> Composition<T> {
83    /// [`Composition<T>`]を返す。
84    pub fn new() -> Self {
85        Self(PhantomData)
86    }
87}
88
89impl_algebra!(
90    {T: Copy + Eq} Composition<T>;
91    set: MaxContiguous<T>;
92    op: |_, a: MaxContiguous<T>, b| a.compose(b);
93    assoc;
94);
haar_lib/algebra/max_contiguous.rs

haar_lib/algebra/
max_contiguous.rs
