pub(super) fn monotone_runs<T>(a: &[T], b: &[T], increasing: bool) -> Vec<T>where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/monotone.rs (line 45)
24pub fn min_plus_convolution_monotone_runs<T>(a: &[T], b: &[T]) -> Vec<T>
25where
26 T: Signed,
27{
28 let len = output_len(a.len(), b.len());
29 if len == 0 {
30 return Vec::new();
31 }
32 assert_finite(a);
33 assert_finite(b);
34 let increasing = if a.windows(2).all(|window| window[0] >= window[1])
35 && b.windows(2).all(|window| window[0] >= window[1])
36 {
37 false
38 } else if a.windows(2).all(|window| window[0] <= window[1])
39 && b.windows(2).all(|window| window[0] <= window[1])
40 {
41 true
42 } else {
43 panic!("both inputs must be monotone in the same direction")
44 };
45 monotone_runs(a, b, increasing)
46}More examples
crates/competitive/src/math/min_plus_convolution/selector.rs (line 336)
293pub fn min_plus_convolution<T>(a: &[T], b: &[T]) -> Vec<T>
294where
295 T: Signed + TryFrom<usize>,
296 T::Unsigned: TryInto<usize>,
297{
298 if (a.len() as u128) * (b.len() as u128) <= SMALL_PAIR_COUNT {
299 return min_plus_convolution_naive(a, b);
300 }
301 let a_characteristics = analyze(a);
302 let distinct_b_characteristics = (!std::ptr::eq(a, b)).then(|| analyze(b));
303 let b_characteristics = distinct_b_characteristics
304 .as_ref()
305 .unwrap_or(&a_characteristics);
306 match select_algorithm(a.len(), b.len(), &a_characteristics, b_characteristics) {
307 Algorithm::Naive => min_plus_convolution_naive(a, b),
308 Algorithm::Sparse => {
309 let a_entries = a[..a_characteristics.finite_prefix_len]
310 .iter()
311 .copied()
312 .enumerate()
313 .chain(a_characteristics.finite_entries.iter().copied());
314 let b_entries = b[..b_characteristics.finite_prefix_len]
315 .iter()
316 .copied()
317 .enumerate()
318 .chain(b_characteristics.finite_entries.iter().copied());
319 sparse(a_entries, b_entries, output_len(a.len(), b.len()))
320 }
321 Algorithm::BoundedNtt => min_plus_convolution_bounded_ntt(a, b),
322 Algorithm::ConvexDivideAndConquerLeft => convex::convex_divide_and_conquer(b, a),
323 Algorithm::ConvexDivideAndConquerRight => convex::convex_divide_and_conquer(a, b),
324 Algorithm::ConvexMerge => convex::convex_merge(a, b),
325 Algorithm::ConcaveEnvelopeLeft => concave::concave_envelope(b, a),
326 Algorithm::ConcaveEnvelopeRight => concave::concave_envelope(a, b),
327 Algorithm::ConcaveBoth => concave::concave_both(a, b),
328 algorithm @ (Algorithm::MonotoneRunsIncreasing | Algorithm::MonotoneRunsDecreasing) => {
329 let increasing = algorithm == Algorithm::MonotoneRunsIncreasing;
330 if let (Some(a_runs), Some(b_runs)) = (
331 &a_characteristics.run_entries,
332 &b_characteristics.run_entries,
333 ) {
334 monotone::monotone_runs_from_entries(a_runs, b_runs, a.len(), b.len(), increasing)
335 } else {
336 monotone::monotone_runs(a, b, increasing)
337 }
338 }
339 Algorithm::LinearLeft => piecewise_linear::linear(b, a),
340 Algorithm::LinearRight => piecewise_linear::linear(a, b),
341 Algorithm::PiecewiseLinearLeft => piecewise_linear::piecewise_linear(b, a),
342 Algorithm::PiecewiseLinearRight => piecewise_linear::piecewise_linear(a, b),
343 }
344}