contest_algorithms/range_query/
specs.rs

1//! A collection of example ArqSpec implementations
2
3pub trait ArqSpec {
4    /// Type of underlying array elements.
5    type S: Clone;
6    /// Type of data representing an endomorphism.
7    // Note that while a Fn(S) -> S may seem like a more natural representation
8    // for an endomorphism, compositions would then have to delegate to each of
9    // their parts. This representation is more efficient.
10    type F: Clone;
11
12    /// Must satisfy the Associative Law:
13    /// For all a,b,c, op(a, op(b, c)) = op(op(a, b), c)
14    fn op(a: &Self::S, b: &Self::S) -> Self::S;
15    /// Must satisfy the Identity Law:
16    /// For all a, op(a, identity()) = op(identity(), a) = a
17    fn identity() -> Self::S;
18    /// Must satisfy the Composition Law:
19    /// For all f,g,a, apply(compose(f, g), a) = apply(f, apply(g, a))
20    fn compose(f: &Self::F, g: &Self::F) -> Self::F;
21    /// Must satisfy the Distributive Law:
22    /// For all f,a,b, apply(f, op(a, b), s+t) = op(apply(f, a, s), apply(f, b, t))
23    /// The `size` parameter makes this law easier to satisfy in certain cases.
24    fn apply(f: &Self::F, a: &Self::S, size: i64) -> Self::S;
25
26    // The following relaxations to the laws may apply.
27    // If only point updates are made, the Composition and Distributive Laws
28    // no longer apply.
29    // - compose() is never called, so it can be left unimplemented!().
30    // - apply() is only ever called on leaves, i.e., with size == 1.
31    // If only point queries are made, the Associative and Distributive Laws
32    // no longer apply.
33    // - op()'s result only matters when identity() is an argument.
34    // - apply()'s result only matters on leaves, i.e., with size == 1.
35}
36
37/// Range Minimum Query (RMQ), a classic application of ARQ.
38/// update(l, r, &f) sets all entries a[l..=r] to f.
39/// query(l, r) finds the minimum value in a[l..=r].
40//
41// Exercises: try augmenting this struct to find the index of a minimum element
42// in a range query, as well as the number of elements equal to the minimum.
43// Then instead of overwriting values with a constant assignment a[i] = f,
44// try supporting addition: a[i] += f.
45pub enum AssignMin {}
46impl ArqSpec for AssignMin {
47    type S = i64;
48    type F = i64;
49    fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
50        a.min(b)
51    }
52    fn identity() -> Self::S {
53        i64::max_value()
54    }
55    fn compose(&f: &Self::F, _: &Self::F) -> Self::F {
56        f
57    }
58    fn apply(&f: &Self::F, _: &Self::S, _: i64) -> Self::S {
59        f
60    }
61}
62
63/// Range Sum Query, a slightly trickier classic application of ARQ.
64/// update(l, r, &f) sets all entries a[l..=r] to f.
65/// query(l, r) sums all the entries a[l..=r].
66///
67/// # Panics
68///
69/// Associated functions will panic on overflow.
70//
71// Note that while the `size` parameter seems necessary to satisfy the
72// Distributive Law, it is merely a convenience: in essence what we've done
73// is move to the product monoid of tuples (value, size_of_subtree).
74//
75// In mathematical jargon, we say that constant assignment f(a) = f is not an
76// endomorphism on (i64, +) because f(a+b) = f != 2*f = f(a) + f(b).
77// On the other hand, f((a, s)) = (f*s, s) is indeed an endomorphism on pairs
78// with vector addition: f((a, s) + (b, t)) = f((a+b, s+t)) = (f*(s+t), s+t)
79//                       = (f*s, s) + (f*t, t) = f((a,s)) + f((b,t)).
80pub enum AssignSum {}
81impl ArqSpec for AssignSum {
82    type S = i64;
83    type F = i64;
84    fn op(&a: &Self::S, &b: &Self::S) -> Self::S {
85        a + b
86    }
87    fn identity() -> Self::S {
88        0
89    }
90    fn compose(&f: &Self::F, _: &Self::F) -> Self::F {
91        f
92    }
93    fn apply(&f: &Self::F, _: &Self::S, size: i64) -> Self::S {
94        f * size
95    }
96}
97
98/// Supply & Demand, based on https://codeforces.com/gym/102218/problem/F
99/// update(i, i, &(p, o)) increases supply by p and demand by o at time i.
100/// query(l, r) computes total supply and demand at times l to r, as well as
101//              how much of the supply is subsequently met by the demand.
102//
103// Note that the apply() operation is only correct when applied to leaf nodes.
104// Therefore, update() must only be used in "eager" mode, i.e., with l == r.
105// compose() should be unimplemented!() to prevent accidental "lazy" updates.
106pub enum SupplyDemand {}
107impl ArqSpec for SupplyDemand {
108    type S = (i64, i64, i64); // production, orders, sales
109    type F = (i64, i64);
110    fn op((p1, o1, s1): &Self::S, (p2, o2, s2): &Self::S) -> Self::S {
111        let extra = (p1 - s1).min(o2 - s2);
112        (p1 + p2, o1 + o2, s1 + s2 + extra)
113    }
114    fn identity() -> Self::S {
115        (0, 0, 0)
116    }
117    fn compose(_: &Self::F, _: &Self::F) -> Self::F {
118        unimplemented!()
119    }
120    fn apply(&(p_add, o_add): &Self::F, &(p, o, _): &Self::S, s: i64) -> Self::S {
121        assert_eq!(s, 1);
122        let p = p + p_add;
123        let o = o + o_add;
124        (p, o, p.min(o))
125    }
126}
contest_algorithms/range_query/specs.rs

contest_algorithms/range_query/
specs.rs
