fn convex_convolution_witnesses<T>(a: &[T], b: &[T]) -> (Vec<T>, Vec<usize>)where
T: Signed,Examples found in repository?
crates/competitive/src/math/min_plus_convolution/near_convex.rs (line 81)
65pub fn min_plus_convolution_near_convex_scan<T>(
66 a: &[T],
67 b: &[T],
68 convex_a: &[T],
69 convex_b: &[T],
70 delta: T,
71) -> Vec<T>
72where
73 T: Signed,
74{
75 let len = output_len(a.len(), b.len());
76 if len == 0 {
77 return Vec::new();
78 }
79 validate_witness(a, convex_a, delta);
80 validate_witness(b, convex_b, delta);
81 let (convex_output, witnesses) = convex_convolution_witnesses(convex_a, convex_b);
82 let tolerance = delta + delta;
83 let relevant = |output: usize, i: usize| {
84 convex_a[i] + convex_b[output - i] <= convex_output[output] + tolerance
85 };
86 let mut result = Vec::with_capacity(len);
87 for output in 0..len {
88 let first = output.saturating_sub(b.len() - 1);
89 let last = output.min(a.len() - 1);
90 let witness = witnesses[output];
91 let mut low = first;
92 let mut high = witness;
93 while low < high {
94 let middle = low + (high - low) / 2;
95 if relevant(output, middle) {
96 high = middle;
97 } else {
98 low = middle + 1;
99 }
100 }
101 let first_relevant = low;
102 low = witness;
103 high = last;
104 while low < high {
105 let middle = low + (high - low).div_ceil(2);
106 if relevant(output, middle) {
107 low = middle;
108 } else {
109 high = middle - 1;
110 }
111 }
112 let mut best = T::maximum();
113 for i in first_relevant..=low {
114 best = best.min(a[i] + b[output - i]);
115 }
116 result.push(best);
117 }
118 result
119}