competitive/algorithm/
mo_algorithm.rs

1/// solve with Mo's algorithm
2///
3/// arg:
4/// - lr: slice of pair of usize
5/// - (l, r): ident of current pair
6/// - incl: |i| expr: del i, l+=1 (post)
7/// - decl: |i| expr: add i, l-=1 (pre)
8/// - incr: |i| expr: add i, r+=1 (post)
9/// - decr: |i| expr: del i, r-=1 (pre)
10/// - answer: |i| expr: answer i-th pair of lr
11///
12/// incr and decr can be omitted, if simultaneous
13#[macro_export]
14macro_rules! mo_algorithm {
15    (
16        $lr:expr,
17        ($l:ident, $r:ident),
18        |$i:tt| $inc:expr,
19        |$d:tt| $dec:expr,
20        |$a:tt| $answer:expr $(,)?
21    ) => {{
22        $crate::mo_algorithm!(
23            $lr,
24            ($l, $r),
25            |$i| $inc,
26            |$d| $dec,
27            |$d| $dec,
28            |$i| $inc,
29            |$a| $answer
30        );
31    }};
32    (
33        $lr:expr,
34        ($l:ident, $r:ident),
35        |$il:tt| $incl:expr,
36        |$dl:tt| $decl:expr,
37        |$ir:tt| $incr:expr,
38        |$dr:tt| $decr:expr,
39        |$a:tt| $answer:expr $(,)?
40    ) => {{
41        fn hilbert_curve_order(mut x: usize, mut y: usize, m: usize) -> usize {
42            let n = 1usize << m;
43            let mut ord = 0usize;
44            for k in (0..m).rev() {
45                let rx = x >> k & 1;
46                let ry = y >> k & 1;
47                ord += (1 << k * 2) * (3 * rx ^ ry);
48                if ry == 0 {
49                    if rx == 1 {
50                        x = n - x - 1;
51                        y = n - y - 1;
52                    }
53                    ::std::mem::swap(&mut x, &mut y);
54                }
55            }
56            ord
57        }
58        let lr: &[(usize, usize)] = $lr;
59        let q = lr.len();
60        let maxv = lr.iter().map(|&(l, r)| l.max(r)).max().unwrap_or_default();
61        let mut m = 0usize;
62        while maxv >= 1 << m {
63            m += 1;
64        }
65        let mut idx: Vec<usize> = (0..q).collect();
66        let ord: Vec<_> = lr
67            .iter()
68            .map(|&(l, r)| hilbert_curve_order(l, r, m))
69            .collect();
70        idx.sort_unstable_by_key(|&i| ord[i]);
71        let (mut $l, mut $r) = (0usize, 0usize);
72        for &$a in idx.iter() {
73            let (nl, nr) = lr[$a];
74            while $l > nl {
75                $l -= 1;
76                let $dl: usize = $l;
77                $decl;
78            }
79            while $r < nr {
80                let $ir: usize = $r;
81                $incr;
82                $r += 1;
83            }
84            while $l < nl {
85                let $il: usize = $l;
86                $incl;
87                $l += 1;
88            }
89            while $r > nr {
90                $r -= 1;
91                let $dr: usize = $r;
92                $decr;
93            }
94            $answer;
95        }
96    }};
97}
competitive/algorithm/mo_algorithm.rs

competitive/algorithm/
mo_algorithm.rs
