haar_lib/algebra/
max_contiguous.rs

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

haar_lib/algebra/
max_contiguous.rs
