competitive/algorithm/syakutori.rs
1/// arg:
2/// - n: length of array
3/// - (l, r): ident of left-bound and right-bound
4/// - addable: |index| expr: return is addable element
5/// - add: |index| expr: add element
6/// - remove: |index| expr: remove element
7/// - show: call n times for l in 0..n, with rightmost r
8///
9/// ```
10/// # use competitive::syakutori;
11/// let (a, w) = ([1, 2, 3, 4], 6);
12/// let (mut ans, mut acc) = (0, 0);
13/// syakutori!(
14/// a.len(),
15/// (l, r),
16/// |i| acc + a[i] <= w,
17/// |i| acc += a[i],
18/// |i| acc -= a[i],
19/// ans += r - l
20/// );
21/// assert_eq!(ans, 7);
22/// ```
23#[macro_export]
24macro_rules! syakutori {
25 (
26 $n:expr,
27 ($l:ident, $r:ident),
28 |$i:ident| $addable:expr,
29 |$j:ident| $add:expr,
30 |$k:ident| $remove:expr,
31 $show:expr $(,)?
32 ) => {{
33 let n: usize = $n;
34 let mut $r: usize = 0;
35 for $l in 0..n {
36 while $r < n && {
37 let $i: usize = $r;
38 let cond: bool = $addable;
39 cond
40 } {
41 let $j: usize = $r;
42 $add;
43 $r += 1;
44 }
45 $show;
46 if $l == $r {
47 $r += 1;
48 } else {
49 let $k: usize = $l;
50 $remove;
51 }
52 }
53 }};
54}
55
56#[cfg(test)]
57mod tests {
58 use crate::{rand, tools::Xorshift};
59
60 #[test]
61 fn test_syakutori() {
62 let mut rng = Xorshift::default();
63 for _ in 0..50 {
64 rand!(rng, n: 1..50, a: [1i64..1000; n], w: 1i64..10000);
65 let mut ans = 0;
66 let mut acc = 0;
67 syakutori!(
68 a.len(),
69 (l, r),
70 |i| acc + a[i] <= w,
71 |i| acc += a[i],
72 |i| acc -= a[i],
73 ans += r - l
74 );
75 let mut exp = 0;
76 for l in 0..n {
77 for r in l..n {
78 if a[l..=r].iter().sum::<i64>() <= w {
79 exp += 1;
80 }
81 }
82 }
83 assert_eq!(ans, exp);
84 }
85 }
86}