pub trait Bounded: Sized + PartialOrd {
// Required methods
fn maximum() -> Self;
fn minimum() -> Self;
// Provided methods
fn is_maximum(&self) -> bool { ... }
fn is_minimum(&self) -> bool { ... }
fn set_maximum(&mut self) { ... }
fn set_minimum(&mut self) { ... }
}Expand description
Trait for max/min bounds
Required Methods§
Provided Methods§
Sourcefn is_maximum(&self) -> bool
fn is_maximum(&self) -> bool
Examples found in repository?
crates/aizu_online_judge/src/grl/grl_1_a.rs (line 13)
8pub fn grl_1_a(reader: impl Read, writer: impl Write) {
9 prepare_io!(reader, writer);
10 sc!(vs, es, r, (graph, d): @DirectedGraphScanner::<usize, u64>::new(vs, es));
11 let cost = graph.standard_sp_additive().dijkstra([r], |eid| d[eid]);
12 for u in graph.vertices() {
13 if cost[u].is_maximum() {
14 pp!("INF");
15 } else {
16 pp!(cost[u]);
17 }
18 }
19}More examples
crates/competitive/src/math/min_plus_convolution/mod.rs (line 68)
56pub fn min_plus_convolution_naive<T>(a: &[T], b: &[T]) -> Vec<T>
57where
58 T: Signed,
59{
60 let len = output_len(a.len(), b.len());
61 if len == 0 {
62 return Vec::new();
63 }
64 let (outer, inner) = if a.len() <= b.len() { (a, b) } else { (b, a) };
65 let inner_is_finite = !inner.iter().any(T::is_maximum);
66 let mut result = vec![T::maximum(); len];
67 for (index, &left) in outer.iter().enumerate() {
68 if left.is_maximum() {
69 continue;
70 }
71 let output = &mut result[index..index + inner.len()];
72 if inner_is_finite {
73 for (slot, &right) in output.iter_mut().zip(inner) {
74 *slot = (*slot).min(left + right);
75 }
76 } else {
77 for (slot, &right) in output.iter_mut().zip(inner) {
78 if !right.is_maximum() {
79 *slot = (*slot).min(left + right);
80 }
81 }
82 }
83 }
84 result
85}
86
87/// Computes min-plus convolution by enumerating finite input pairs only.
88///
89/// If the inputs have `s_a` and `s_b` finite values, the running time is
90/// `O(s_a * s_b + n + m)`.
91///
92/// # Panics
93///
94/// Panics if the output length does not fit [`usize`]. Arithmetic overflow is
95/// the caller's responsibility.
96pub fn min_plus_convolution_sparse<T>(a: &[T], b: &[T]) -> Vec<T>
97where
98 T: Signed,
99{
100 let len = output_len(a.len(), b.len());
101 if len == 0 {
102 return Vec::new();
103 }
104 let a: Vec<_> = a
105 .iter()
106 .copied()
107 .enumerate()
108 .filter(|(_, value)| !value.is_maximum())
109 .collect();
110 let b: Vec<_> = b
111 .iter()
112 .copied()
113 .enumerate()
114 .filter(|(_, value)| !value.is_maximum())
115 .collect();
116 sparse(a.iter().copied(), b.iter().copied(), len)
117}
118
119fn sparse<T>(
120 a: impl IntoIterator<Item = (usize, T)>,
121 b: impl IntoIterator<Item = (usize, T)> + Clone,
122 len: usize,
123) -> Vec<T>
124where
125 T: Signed,
126{
127 let mut result = vec![T::maximum(); len];
128 for (i, left) in a {
129 for (j, right) in b.clone() {
130 result[i + j] = result[i + j].min(left + right);
131 }
132 }
133 result
134}
135
136const MAX_NTT_SIZE: usize = 1 << 23;
137
138#[derive(Clone, Copy, Debug)]
139struct BoundedRequirements<T> {
140 a_min: T,
141 b_min: T,
142 base: usize,
143 transform_len: usize,
144}
145
146fn finite_extrema<T>(values: &[T]) -> Option<(T, T)>
147where
148 T: Signed,
149{
150 let mut finite = values.iter().copied().filter(|value| !value.is_maximum());
151 let first = finite.next()?;
152 Some(finite.fold((first, first), |(minimum, maximum), value| {
153 (minimum.min(value), maximum.max(value))
154 }))
155}
156
157fn bounded_transform_len(a_len: usize, b_len: usize, base: usize) -> Option<usize> {
158 let left_len = a_len.checked_mul(base)?;
159 let right_len = b_len.checked_mul(base)?;
160 let coefficient_len = left_len
161 .checked_add(right_len)
162 .and_then(|len| len.checked_sub(1))?;
163 let transform_len = coefficient_len.checked_next_power_of_two()?;
164 (transform_len <= MAX_NTT_SIZE).then_some(transform_len)
165}
166
167fn bounded_requirements_from_extrema<T>(
168 a_len: usize,
169 b_len: usize,
170 (a_min, a_max): (T, T),
171 (b_min, b_max): (T, T),
172) -> Option<BoundedRequirements<T>>
173where
174 T: Signed,
175 T::Unsigned: TryInto<usize>,
176{
177 let a_span = a_max.abs_diff(a_min).try_into().ok()?;
178 let b_span = b_max.abs_diff(b_min).try_into().ok()?;
179 let base = a_span
180 .checked_add(b_span)
181 .and_then(|span| span.checked_add(1))?;
182 let transform_len = bounded_transform_len(a_len, b_len, base)?;
183 Some(BoundedRequirements {
184 a_min,
185 b_min,
186 base,
187 transform_len,
188 })
189}
190
191/// Computes exact min-plus convolution for small integer value spans using NTT.
192///
193/// # Panics
194///
195/// Panics if the encoded range cannot be represented or requires a transform
196/// longer than `2^23`. Arithmetic overflow is the caller's responsibility.
197pub fn min_plus_convolution_bounded_ntt<T>(a: &[T], b: &[T]) -> Vec<T>
198where
199 T: Signed + TryFrom<usize>,
200 T::Unsigned: TryInto<usize>,
201{
202 let output_len = output_len(a.len(), b.len());
203 if output_len == 0 {
204 return Vec::new();
205 }
206 let (Some(a_extrema), Some(b_extrema)) = (finite_extrema(a), finite_extrema(b)) else {
207 return vec![T::maximum(); output_len];
208 };
209 let requirements = bounded_requirements_from_extrema(a.len(), b.len(), a_extrema, b_extrema)
210 .expect("bounded min-plus convolution encoding must fit the 2^23 NTT limit");
211 let mut left = vec![MInt998244353::from(0_u32); a.len() * requirements.base];
212 let mut right = vec![MInt998244353::from(0_u32); b.len() * requirements.base];
213 for (index, &value) in a.iter().enumerate() {
214 if !value.is_maximum() {
215 let normalized: usize = value
216 .abs_diff(requirements.a_min)
217 .try_into()
218 .ok()
219 .expect("bounded min-plus convolution value span must fit usize");
220 left[index * requirements.base + normalized] = MInt998244353::from(1_u32);
221 }
222 }
223 for (index, &value) in b.iter().enumerate() {
224 if !value.is_maximum() {
225 let normalized: usize = value
226 .abs_diff(requirements.b_min)
227 .try_into()
228 .ok()
229 .expect("bounded min-plus convolution value span must fit usize");
230 right[index * requirements.base + normalized] = MInt998244353::from(1_u32);
231 }
232 }
233 let coefficients = Convolve998244353::convolve(left, right);
234 let encoded_len = output_len
235 .checked_mul(requirements.base)
236 .expect("bounded min-plus convolution encoded length must fit usize");
237 let mut result = Vec::with_capacity(output_len);
238 for chunk in coefficients[..encoded_len].chunks_exact(requirements.base) {
239 let value = if let Some(normalized) = chunk.iter().position(|&value| u32::from(value) != 0)
240 {
241 requirements.a_min
242 + requirements.b_min
243 + T::try_from(normalized)
244 .ok()
245 .expect("bounded min-plus convolution value must fit the output type")
246 } else {
247 T::maximum()
248 };
249 result.push(value);
250 }
251 result
252}crates/competitive/src/math/min_plus_convolution/concave.rs (line 69)
63 fn insert_from_left(&mut self, left: usize) {
64 let mut right = left + self.concave.len();
65 let block = 1_usize << (left ^ right).ilog2();
66 right &= !(block - 1);
67 let mut depth = bit_width(right - left - 1);
68 let mut node = (self.leaf_count + left) >> depth;
69 let mut pending = (!self.arbitrary[left].is_maximum()).then_some(left);
70 while depth != 0 {
71 let Some(curve) = pending else {
72 break;
73 };
74 depth -= 1;
75 let middle = ((node << 1 | 1) << depth) - self.leaf_count - 1;
76 if middle < left {
77 node = node << 1 | 1;
78 } else if self.node_curves[node]
79 .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
80 {
81 node <<= 1;
82 } else {
83 std::mem::swap(&mut self.node_curves[node], &mut pending);
84 node = node << 1 | 1;
85 }
86 }
87 if let Some(curve) = pending {
88 let output = node - self.leaf_count;
89 self.result[output] = self.result[output].min(self.value(curve, output));
90 }
91 }
92
93 #[inline]
94 fn insert_from_right(&mut self, right: usize) {
95 let curve = right - self.concave.len();
96 let block = 1_usize << (curve ^ right).ilog2();
97 let left = right & !(block - 1);
98 if left == right {
99 return;
100 }
101 let mut depth = bit_width(right - left - 1);
102 let mut node = (self.leaf_count + left) >> depth;
103 let mut pending = (!self.arbitrary[curve].is_maximum()).then_some(curve);
104 while depth != 0 {
105 let Some(curve) = pending else {
106 break;
107 };
108 depth -= 1;
109 let middle = ((node << 1 | 1) << depth) - self.leaf_count;
110 if middle >= right {
111 node <<= 1;
112 } else if self.node_curves[node]
113 .is_some_and(|old| self.value(old, middle) < self.value(curve, middle))
114 {
115 node = node << 1 | 1;
116 } else {
117 std::mem::swap(&mut self.node_curves[node], &mut pending);
118 node <<= 1;
119 }
120 }
121 if let Some(curve) = pending {
122 let output = node - self.leaf_count;
123 self.result[output] = self.result[output].min(self.value(curve, output));
124 }
125 }
126
127 fn convolve(mut self) -> Vec<T> {
128 // Curve i is valid on [i, i + concave.len()). The two passes insert
129 // opposite sides of each validity interval into the segment envelope.
130 for left in 0..self.arbitrary.len() {
131 self.insert_from_left(left);
132 self.query(left);
133 }
134 for output in self.arbitrary.len()..self.result.len() {
135 self.query(output);
136 }
137
138 self.node_curves.fill(None);
139 let mut right = self.result.len();
140 while right >= self.concave.len() {
141 self.insert_from_right(right);
142 right -= 1;
143 self.query(right);
144 }
145 for output in 0..self.concave.len() {
146 self.query(output);
147 }
148 self.result
149 }
150}
151
152/// Computes convolution when one finite input is concave using offline envelopes.
153///
154/// The running time is `O((n + m) log(n + m))`. The arbitrary input may
155/// contain `T::maximum()`.
156///
157/// # Panics
158///
159/// Panics unless at least one input is finite and concave, or if the
160/// interval-tree size cannot be represented.
161pub fn min_plus_convolution_concave_envelope<T>(a: &[T], b: &[T]) -> Vec<T>
162where
163 T: Signed,
164{
165 let len = output_len(a.len(), b.len());
166 if len == 0 {
167 return Vec::new();
168 }
169 let a_is_concave = !a.iter().any(T::is_maximum) && is_concave(a);
170 let b_is_concave = !b.iter().any(T::is_maximum) && is_concave(b);
171 let (arbitrary, concave) = if b_is_concave {
172 (a, b)
173 } else if a_is_concave {
174 (b, a)
175 } else {
176 panic!("at least one min-plus convolution input must be finite and concave")
177 };
178 concave_envelope(arbitrary, concave)
179}
180
181pub(super) fn concave_envelope<T>(arbitrary: &[T], concave: &[T]) -> Vec<T>
182where
183 T: Signed,
184{
185 if concave.len() == 1 {
186 return arbitrary
187 .iter()
188 .map(|&value| {
189 if value.is_maximum() {
190 T::maximum()
191 } else {
192 value + concave[0]
193 }
194 })
195 .collect();
196 }
197 if arbitrary.len() == 1 {
198 return if arbitrary[0].is_maximum() {
199 vec![T::maximum(); concave.len()]
200 } else {
201 concave.iter().map(|&value| arbitrary[0] + value).collect()
202 };
203 }
204
205 ConcaveEnvelope::new(arbitrary, concave).convolve()
206}crates/competitive/src/math/min_plus_convolution/piecewise_linear.rs (line 81)
69fn convolve_piece<T>(arbitrary: &[T], piece: LinearPiece<T>, result: &mut [T])
70where
71 T: Signed + TryFrom<usize>,
72{
73 let mut deque = VecDeque::with_capacity(arbitrary.len());
74 let mut next_to_add = 0;
75 for (output, slot) in result.iter_mut().enumerate() {
76 if output < piece.start {
77 continue;
78 }
79 let upper = (output - piece.start).min(arbitrary.len() - 1);
80 while next_to_add <= upper {
81 if !arbitrary[next_to_add].is_maximum() {
82 let index = T::try_from(next_to_add)
83 .ok()
84 .expect("piecewise-linear index must fit the value type");
85 let transformed = arbitrary[next_to_add] - piece.slope * index;
86 while deque.back().is_some_and(|&(_, value)| value >= transformed) {
87 deque.pop_back();
88 }
89 deque.push_back((next_to_add, transformed));
90 }
91 next_to_add += 1;
92 }
93 let lower = output.saturating_sub(piece.end);
94 while deque.front().is_some_and(|&(index, _)| index < lower) {
95 deque.pop_front();
96 }
97 if let Some(&(_, minimum)) = deque.front() {
98 let output = T::try_from(output)
99 .ok()
100 .expect("piecewise-linear output index must fit the value type");
101 *slot = (*slot).min(piece.slope * output + piece.intercept + minimum);
102 }
103 }
104}crates/competitive/src/math/min_plus_convolution/squared_distance.rs (line 49)
39pub fn min_plus_convolution_with_squared_distance<T>(values: &[T]) -> Vec<T>
40where
41 T: Signed + TryFrom<usize>,
42{
43 if values.is_empty() {
44 return Vec::new();
45 }
46 let mut sources = Vec::with_capacity(values.len());
47 let mut first_positions = Vec::with_capacity(values.len());
48 for (new_source, &value) in values.iter().enumerate() {
49 if value.is_maximum() {
50 continue;
51 }
52 let mut first_position = T::zero();
53 while let Some(&previous_source) = sources.last() {
54 first_position = first_position_of_new_source(values, previous_source, new_source);
55 if first_position > first_positions[first_positions.len() - 1] {
56 break;
57 }
58 sources.pop();
59 first_positions.pop();
60 }
61 if sources.is_empty() {
62 first_position = T::zero();
63 }
64 if first_position < index_as_value(values.len()) {
65 sources.push(new_source);
66 first_positions.push(first_position.max(T::zero()));
67 }
68 }
69 if sources.is_empty() {
70 return vec![T::maximum(); values.len()];
71 }
72 let mut active_source_index = 0;
73 let mut result = Vec::with_capacity(values.len());
74 for position in 0..values.len() {
75 while active_source_index + 1 < sources.len()
76 && first_positions[active_source_index + 1] <= index_as_value(position)
77 {
78 active_source_index += 1;
79 }
80 let source = sources[active_source_index];
81 let distance: T = index_as_value(source.abs_diff(position));
82 result.push(values[source] + distance * distance);
83 }
84 result
85}crates/competitive/src/math/min_plus_convolution/selector.rs (line 60)
41fn analyze<T>(values: &[T]) -> InputCharacteristics<T>
42where
43 T: Signed,
44{
45 let Some(&first) = values.first() else {
46 return InputCharacteristics {
47 finite_count: 0,
48 finite_prefix_len: 0,
49 finite_entries: Vec::new(),
50 run_entries: Some(Vec::new()),
51 extrema: None,
52 is_convex: true,
53 is_concave: true,
54 is_nondecreasing: true,
55 is_nonincreasing: true,
56 run_count: 0,
57 piece_count: 0,
58 };
59 };
60 if first.is_maximum() {
61 return analyze_with_infinity(values, 0, None);
62 }
63
64 let mut minimum = first;
65 let mut maximum = first;
66 let mut is_convex = true;
67 let mut is_concave = true;
68 let mut is_nondecreasing = true;
69 let mut is_nonincreasing = true;
70 let mut run_count = 1;
71 let mut run_entries = Some(vec![(0, first)]);
72 let mut piece_count = 1;
73 let mut previous_value = first;
74 let mut previous_slope = None;
75
76 for (index, &value) in values.iter().enumerate().skip(1) {
77 if value.is_maximum() {
78 return analyze_with_infinity(values, index, Some((minimum, maximum)));
79 }
80 minimum = minimum.min(value);
81 maximum = maximum.max(value);
82 is_nondecreasing &= previous_value <= value;
83 is_nonincreasing &= previous_value >= value;
84 if previous_value != value {
85 run_count += 1;
86 if let Some(entries) = &mut run_entries {
87 if entries.len() == MAX_CACHED_RUNS {
88 run_entries = None;
89 } else {
90 entries.push((index, value));
91 }
92 }
93 }
94 let slope = value - previous_value;
95 if let Some(previous_slope) = previous_slope {
96 is_convex &= previous_slope <= slope;
97 is_concave &= previous_slope >= slope;
98 piece_count += usize::from(previous_slope != slope);
99 }
100 previous_slope = Some(slope);
101 previous_value = value;
102 }
103 InputCharacteristics {
104 finite_count: values.len(),
105 finite_prefix_len: values.len(),
106 finite_entries: Vec::new(),
107 run_entries,
108 extrema: Some((minimum, maximum)),
109 is_convex,
110 is_concave,
111 is_nondecreasing,
112 is_nonincreasing,
113 run_count,
114 piece_count,
115 }
116}
117
118fn analyze_with_infinity<T>(
119 values: &[T],
120 first_infinity: usize,
121 mut extrema: Option<(T, T)>,
122) -> InputCharacteristics<T>
123where
124 T: Signed,
125{
126 let mut finite_entries = Vec::new();
127 for (offset, &value) in values[first_infinity + 1..].iter().enumerate() {
128 if !value.is_maximum() {
129 finite_entries.push((first_infinity + offset + 1, value));
130 extrema = Some(extrema.map_or((value, value), |(minimum, maximum)| {
131 (minimum.min(value), maximum.max(value))
132 }));
133 }
134 }
135 InputCharacteristics {
136 finite_count: first_infinity + finite_entries.len(),
137 finite_prefix_len: first_infinity,
138 finite_entries,
139 run_entries: None,
140 extrema,
141 is_convex: false,
142 is_concave: false,
143 is_nondecreasing: false,
144 is_nonincreasing: false,
145 run_count: 0,
146 piece_count: 0,
147 }
148}fn is_minimum(&self) -> bool
fn set_maximum(&mut self)
fn set_minimum(&mut self)
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety".