Mo's

[tipstar0125]

参考1：https://qiita.com/rp523/items/444966255b9a6c8c4c8e 参考2：https://aotamasaki.hatenablog.com/entry/2020/08/04/Mo%27s_algorithm_python

[tipstar0125]

RSQ(Range Set Query) 問題：https://atcoder.jp/contests/abc174/tasks/abc174_f 解答：https://atcoder.jp/contests/abc174/submissions/49411066

struct MoStatus {
    cnt: Vec<isize>,
    num: usize,
}

struct Mo {
    N: usize,
    Q: usize,
    K: usize,
    ls: Vec<usize>,
    queries: Vec<(usize, usize)>,
    l: usize,
    r: usize,
    status: MoStatus,
}

impl Mo {
    fn new(ls: Vec<usize>, queries: Vec<(usize, usize)>) -> Self {
        let N = ls.len();
        let Q = queries.len();
        let mut sqrtQ = 1;
        while sqrtQ * sqrtQ <= Q {
            sqrtQ += 1;
        }
        let K = (N + sqrtQ - 1) / sqrtQ;
        Mo {
            N,
            Q,
            K,
            ls,
            queries,
            l: 0,
            r: 0,
            status: MoStatus {
                cnt: vec![0; N],
                num: 0,
            },
        }
    }
    fn add(&mut self, idx: usize) {
        if self.status.cnt[self.ls[idx]] == 0 {
            self.status.num += 1;
        }
        self.status.cnt[self.ls[idx]] += 1;
    }
    fn remove(&mut self, idx: usize) {
        self.status.cnt[self.ls[idx]] -= 1;
        if self.status.cnt[self.ls[idx]] == 0 {
            self.status.num -= 1;
        }
    }
    fn process(&mut self, l: usize, r: usize) {
        for i in self.r..r {
            self.add(i);
        }
        for i in (r..self.r).rev() {
            self.remove(i);
        }
        for i in self.l..l {
            self.remove(i);
        }
        for i in (l..self.l).rev() {
            self.add(i);
        }
        self.l = l;
        self.r = r;
    }
    fn solve(&mut self) -> Vec<usize> {
        let mut indexes = (0..self.Q).collect::<Vec<_>>();
        indexes.sort_by_cached_key(|&i| {
            let (l, r) = self.queries[i];
            let k = l / self.K;
            if k % 2 == 0 {
                (k, r)
            } else {
                (k, self.N - r)
            }
        });

        let mut ret = vec![0; self.Q];
        for &i in &indexes {
            let (l, r) = self.queries[i];
            self.process(l, r);
            ret[i] = self.status.num;
        }
        ret
    }
}