Function nekolib::algo::mo

pub fn mo<S>(
    slice: S,
    q: Vec<(Range<usize>, S::Salt)>,
    b: Option<usize>
) -> Vec<S::Hashed>where
    S: ElasticSlice + ExpandFront + ExpandBack + ShrinkFront + ShrinkBack + SliceHash,
    S::Hashed: Clone,

Mo’s algorithm。

オフラインのクエリを $q$ 個処理する。 $i$ 番目のクエリは「区間 $[l_i, r_i)$ と値 $x_i$ によって計算される値を求めよ」 ということを意味する。

Complexity

区間の全長 $n$、クエリ数 $q$、パラメータ $b$ に対して、 shrink_front と expand_front を高々 $q\cdot b$ 回、 shrink_back と expand_back を高々 $n^2/b$ 回行う。

Hints

相加・相乗平均の等号成立条件から $b = n\cdot q^{-1/2}$ とするのがよさげに思えるが、実際には手でパラメータを調整したくなることも多い。 そのため、引数に None を渡した場合は上記の値を用い、Some(b) を渡した場合はその b を用いる実装にしている。

定数での除算は最適化により乗算などに置き換えられることが期待されるので、 予め最大ケースにおける $b$ を計算するなどして、その値を渡す方がいいかも。 個人的には $224$ から $384$ くらいの大きさの $32$ の倍数に祈ることが多い。

Examples

use std::collections::BTreeMap;

use nekolib::traits::{
    ElasticSlice, ExpandBack, ExpandFront, ShrinkBack,
    ShrinkFront, SliceHash,
};
use nekolib::algo::mo;

struct RangeDistinct {
    buf: Vec<i32>,
    start: usize,
    end: usize,
    count: BTreeMap<i32, usize>,
}

impl From<Vec<i32>> for RangeDistinct {
    fn from(buf: Vec<i32>) -> Self {
        Self { buf, start: 0, end: 0, count: BTreeMap::new() }
    }
}

impl ElasticSlice for RangeDistinct {
    fn reset(&mut self) {
        self.start = 0;
        self.end = 0;
        self.count.clear();
    }
    fn full_len(&self) -> usize { self.buf.len() }
    fn start(&self) -> usize { self.start }
    fn end(&self) -> usize { self.end }
}

/// 区間 `start..end` に含まれる整数の集合と、`x` のみからなる
/// 集合との和集合の要素数を返す。
impl SliceHash for RangeDistinct {
    type Salt = i32;
    type Hashed = usize;
    fn hash(&self, x: i32) -> usize {
        self.count.len()
            + if self.count.contains_key(&x) { 0 } else { 1 }
    }
}

impl ExpandBack for RangeDistinct {
    fn expand_back(&mut self) {
        let k = self.buf[self.end];
        *self.count.entry(k).or_insert(0) += 1;
        self.end += 1;
    }
}

impl ExpandFront for RangeDistinct {
    fn expand_front(&mut self) {
        self.start -= 1;
        let k = self.buf[self.start];
        *self.count.entry(k).or_insert(0) += 1;
    }
}

impl ShrinkBack for RangeDistinct {
    fn shrink_back(&mut self) {
        self.end -= 1;
        let k = self.buf[self.end];
        match self.count.get_mut(&k) {
            Some(x) if x == &1 => { self.count.remove(&k); }
            Some(x) => *x -= 1,
            None => unreachable!(),
        }
    }
}

impl ShrinkFront for RangeDistinct {
    fn shrink_front(&mut self) {
        let k = self.buf[self.start];
        match self.count.get_mut(&k) {
            Some(x) if x == &1 => { self.count.remove(&k); }
            Some(x) => *x -= 1,
            None => unreachable!(),
        }
        self.start += 1;
    }
}

let rd: RangeDistinct = vec![1, 4, 1, 4, 2, 1, 3, 5, 6].into();
let qs = vec![(0..4, 1), (0..4, 2), (2..6, 1), (3..9, 2)];
assert_eq!(mo(rd, qs, Some(4)), vec![2, 3, 3, 6]);