nekolib/algo/
hilbert_mo_.rs

1//! Hilbert curve に基づく Mo's algorithm。
2
3use super::super::traits::elastic_slice;
4
5use std::ops::Range;
6
7use elastic_slice::{
8    ElasticSlice, ExpandBack, ExpandFront, ShrinkBack, ShrinkFront, SliceHash,
9};
10
11/// Hilbert curve に基づく Mo's algorithm。
12///
13/// <style>
14/// .label {
15///     cursor: default;
16///     user-select: none !important;
17///     display: inline;
18///     padding: 0.2em 0.6em 0.3em;
19///     font-size: 60%;
20///     line-height: 1;
21///     color: #fff;
22///     text-align: center;
23///     white-space: nowrap;
24///     vertical-align: baseline;
25///     border-radius: 0.25em;
26///     font-family: Lato;
27/// }
28/// .label-warning {
29///     background-color: #f0ad4e;
30/// }
31/// </style>
32///
33/// See <https://codeforces.com/blog/entry/61203>。
34/// [Range Set Query](https://atcoder.jp/contests/abc174/tasks/abc174_f)
35/// に投げたら <span class="label label-warning">TLE</span> したのでつらい。
36pub fn hilbert_mo<S>(
37    mut slice: S,
38    q: Vec<(Range<usize>, S::Salt)>,
39) -> impl Iterator<Item = S::Hashed>
40where
41    S: ElasticSlice
42        + ExpandFront
43        + ExpandBack
44        + ShrinkFront
45        + ShrinkBack
46        + SliceHash,
47    S::Hashed: Clone,
48{
49    let qn = q.len();
50    let n = slice.len();
51    let k = n.next_power_of_two().trailing_zeros();
52    let mut q: Vec<_> = q
53        .into_iter()
54        .enumerate()
55        .map(|(i, (Range { start, end }, x))| {
56            (i, (start..end, x), ord(start, end, k))
57        })
58        .collect();
59    q.sort_unstable_by_key(|&(.., o)| o);
60
61    let mut res = vec![None; qn];
62    slice.reset();
63    for (i, (Range { start: ql, end: qr }, x), _) in q {
64        while slice.end() < qr {
65            slice.expand_back();
66        }
67        while slice.start() > ql {
68            slice.expand_front();
69        }
70        while slice.start() < ql {
71            slice.shrink_front();
72        }
73        while slice.end() > qr {
74            slice.shrink_back();
75        }
76        res[i] = Some(slice.hash(x));
77    }
78    res.into_iter().map(std::option::Option::unwrap)
79}
80
81fn ord(i: usize, j: usize, k: u32) -> usize { ord_internal(i, j, k, 0) }
82
83fn ord_internal(i: usize, j: usize, pow: u32, rot: usize) -> usize {
84    if pow == 0 {
85        return 0;
86    }
87    let hpow = 1 << (pow - 1);
88    let seg = if i < hpow {
89        if j < hpow { 0 } else { 3 }
90    } else {
91        if j < hpow { 1 } else { 2 }
92    };
93    let seg = (seg + rot) & 3;
94    let drot = [3, 0, 0, 1];
95    let nx = i & (i ^ hpow);
96    let ny = j & (j ^ hpow);
97    let nrot = (rot + drot[seg]) & 3;
98    let sub = 1 << (2 * pow - 2);
99    let res = seg * sub as usize;
100    let add = ord_internal(nx, ny, pow - 1, nrot);
101    res + if seg == 1 || seg == 2 { add } else { sub - add - 1 }
102}
nekolib/algo/hilbert_mo_.rs

nekolib/algo/
hilbert_mo_.rs
