1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170

//! 作用付きモノイド

/// 作用付きモノイド
pub trait ExtMonoid {
    /// 要素のデータ型
    type X: Clone + PartialEq;
    /// 作用素のデータ型
    type F: Clone + PartialEq;
    /// 要素Xの単位元を返す
    fn id_x() -> Self::X;
    /// 作用素Fの単位元を返す
    fn id_f() -> Self::F;
    /// 要素同士の演算
    fn op(x: &Self::X, y: &Self::X) -> Self::X;
    /// 要素に対する作用
    fn mapping(x: &Self::X, y: &Self::F) -> Self::X;
    /// 作用素同士の演算
    fn composition(x: &Self::F, y: &Self::F) -> Self::F;
    /// 作用素の集約
    fn aggregate(x: &Self::F, p: usize) -> Self::F;
}

/// （遅延セグ木）作用付きモノイド
pub mod examples {

    use super::ExtMonoid;

    /// ## AddSum
    /// - 区間加算
    /// - 区間和
    #[derive(Debug)]
    pub struct AddSum;

    impl ExtMonoid for AddSum {
        type X = isize;
        type F = isize;
        fn id_x() -> Self::X {
            0
        }
        fn id_f() -> Self::F {
            0
        }
        fn op(x: &Self::X, y: &Self::X) -> Self::X {
            x + y
        }
        fn mapping(x: &Self::X, y: &Self::F) -> Self::X {
            x + y
        }
        fn composition(x: &Self::F, y: &Self::F) -> Self::F {
            x + y
        }
        fn aggregate(x: &Self::F, p: usize) -> Self::F {
            x * p as isize
        }
    }

    /// ## UpdateMin
    /// - 区間更新
    /// - 区間最小値
    #[derive(Debug)]
    pub struct UpdateMin;

    impl ExtMonoid for UpdateMin {
        type X = isize;
        type F = isize;
        fn id_x() -> Self::X {
            isize::MAX
        }
        fn id_f() -> Self::F {
            isize::MAX
        }
        fn op(x: &Self::X, y: &Self::X) -> Self::X {
            *x.min(y)
        }
        fn mapping(_x: &Self::X, y: &Self::F) -> Self::X {
            *y
        }
        fn composition(_x: &Self::F, y: &Self::F) -> Self::F {
            *y
        }
        fn aggregate(x: &Self::F, _p: usize) -> Self::F {
            *x
        }
    }

    /// ## UpdateMax
    /// - 区間更新
    /// - 区間最大値
    #[derive(Debug)]
    pub struct UpdateMax;

    impl ExtMonoid for UpdateMax {
        type X = isize;
        type F = isize;
        fn id_x() -> Self::X {
            isize::MIN
        }
        fn id_f() -> Self::F {
            isize::MIN
        }
        fn op(x: &Self::X, y: &Self::X) -> Self::X {
            *x.max(y)
        }
        fn mapping(_x: &Self::X, y: &Self::F) -> Self::X {
            *y
        }
        fn composition(_x: &Self::F, y: &Self::F) -> Self::F {
            *y
        }
        fn aggregate(x: &Self::F, _p: usize) -> Self::F {
            *x
        }
    }

    /// ## AddMin
    /// - 区間加算
    /// - 区間最小値
    #[derive(Debug)]
    pub struct AddMin;
    impl ExtMonoid for AddMin {
        type X = isize;
        type F = isize;
        fn id_x() -> Self::X {
            isize::MAX
        }
        fn id_f() -> Self::F {
            0
        }
        fn op(x: &Self::X, y: &Self::X) -> Self::X {
            *x.min(y)
        }
        fn mapping(x: &Self::X, y: &Self::F) -> Self::X {
            x + y
        }
        fn composition(x: &Self::F, y: &Self::F) -> Self::F {
            x + y
        }
        fn aggregate(x: &Self::F, _p: usize) -> Self::F {
            *x
        }
    }

    /// ## UpdateSum
    /// - 区間更新
    /// - 区間和取得
    #[derive(Debug)]
    pub struct UpdateSum;
    impl ExtMonoid for UpdateSum {
        type X = isize;
        type F = Option<isize>;
        fn id_x() -> Self::X {
            0
        }
        fn id_f() -> Self::F {
            None
        }
        fn op(x: &Self::X, y: &Self::X) -> Self::X {
            x + y
        }
        fn mapping(_x: &Self::X, y: &Self::F) -> Self::X {
            y.unwrap()
        }
        fn composition(_x: &Self::F, y: &Self::F) -> Self::F {
            *y
        }
        fn aggregate(x: &Self::F, p: usize) -> Self::F {
            x.map(|x| x * p as isize)
        }
    }
}