haar_lib/algo/
static_range_inversions_query.rs

1//! 範囲転倒数取得クエリ
2
3use crate::{algo::bsearch_slice::BinarySearch, ds::fenwick_add::*};
4use std::convert::TryFrom;
5use std::ops::Range;
6
7/// 範囲転倒数取得クエリ
8pub struct StaticRangeInversionsQuery {
9    data: Vec<usize>,
10    qs: Vec<(usize, usize)>,
11}
12
13impl StaticRangeInversionsQuery {
14    /// **Time complexity** $O(n \log n)$
15    pub fn new<T: Clone + Ord>(data: &[T]) -> Self {
16        let mut a = data.to_vec();
17        a.sort();
18        a.dedup();
19
20        let data = data.iter().map(|x| a.lower_bound(x)).collect();
21        Self { data, qs: vec![] }
22    }
23
24    /// 範囲`l..r`で転倒数を求めるクエリを追加する。
25    pub fn add_query(&mut self, Range { start: l, end: r }: Range<usize>) {
26        self.qs.push((l, r));
27    }
28
29    /// クエリに対しての結果を返す。
30    pub fn solve(self) -> Vec<(Range<usize>, u64)> {
31        let n = self.data.len();
32        let width = (n as f64).sqrt() as usize;
33
34        let mut b = FenwickTreeAdd::<i64>::new(n);
35        let mut temp = 0;
36        let mut ret = vec![(0..0, 0); self.qs.len()];
37
38        let mut ord = (0..self.qs.len()).collect::<Vec<_>>();
39
40        ord.sort_by(|&i, &j| {
41            let a = self.qs[i].0 / width;
42            let b = self.qs[j].0 / width;
43
44            if a == b {
45                if a % 2 == 1 {
46                    self.qs[i].1.cmp(&self.qs[j].1)
47                } else {
48                    self.qs[j].1.cmp(&self.qs[i].1)
49                }
50            } else {
51                a.cmp(&b)
52            }
53        });
54
55        let mut l = self.qs[ord[0]].0;
56        let mut r = self.qs[ord[0]].0;
57
58        for id in ord {
59            while l != self.qs[id].0 || r != self.qs[id].1 {
60                if l > self.qs[id].0 {
61                    l -= 1;
62                    temp += b.fold(0..self.data[l]);
63                    b.add(self.data[l], 1);
64                }
65                if l < self.qs[id].0 {
66                    temp -= b.fold(0..self.data[l]);
67                    b.add(self.data[l], -1);
68                    l += 1;
69                }
70                if r < self.qs[id].1 {
71                    temp += b.fold(self.data[r] + 1..self.data.len());
72                    b.add(self.data[r], 1);
73                    r += 1;
74                }
75                if r > self.qs[id].1 {
76                    r -= 1;
77                    temp -= b.fold(self.data[r] + 1..self.data.len());
78                    b.add(self.data[r], -1);
79                }
80            }
81
82            ret[id] = (self.qs[id].0..self.qs[id].1, u64::try_from(temp).unwrap());
83        }
84
85        ret
86    }
87}
88
89#[cfg(test)]
90mod tests {
91    use super::*;
92    use crate::algo::inversion_number::inversion_number;
93    use my_testtools::rand_range;
94    use rand::Rng;
95
96    #[test]
97    fn test() {
98        let mut rng = rand::thread_rng();
99
100        let n = 100;
101        let a: Vec<u64> = std::iter::repeat_with(|| rng.gen()).take(n).collect();
102
103        let mut sriq = StaticRangeInversionsQuery::new(&a);
104
105        let q = 100;
106        for _ in 0..q {
107            let range = rand_range(&mut rng, 0..n);
108            sriq.add_query(range);
109        }
110
111        for (range, res) in sriq.solve() {
112            let mut temp = a[range].to_vec();
113            let ans = inversion_number(&mut temp);
114
115            assert_eq!(res, ans);
116        }
117    }
118}
haar_lib/algo/static_range_inversions_query.rs

haar_lib/algo/
static_range_inversions_query.rs
