Mo's Algorithm

romophic-library

用途

オフラインクエリかつクエリ区間の伸縮が簡単に出来る時高速に処理する.

計算量

$ O(Q\sqrt{N}) $

使い方(WIP)

実装(WIP)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct Mo { int width; vector<int> left, right, order; vector<bool> v; Mo(int N, int Q) : width((int)sqrt(N)), order(Q), v(N) {
    iota(begin(order), end(order), 0);
  }
  void add(int l, int r) {
    left.emplace_back(l);
    right.emplace_back(r);
  }
  void run(const auto &add, const auto &del, const auto &rem) {
    assert(left.size() == order.size());
    sort(begin(order), end(order), [&](int a, int b) {
      int ablock = left[a] / width, bblock = left[b] / width;
      if (ablock != bblock)
        return ablock < bblock;
      if (ablock & 1)
        return right[a] < right[b];
      return right[a] > right[b];
    });
    int nl = 0, nr = 0;
    auto push = [&](int idx) {
      v[idx].flip();
      if (v[idx])
        add(idx);
      else
        del(idx);
    };
    for (auto idx : order) {
      while (nl > left[idx])
        push(--nl);
      while (nr < right[idx])
        push(nr++);
      while (nl < left[idx])
        push(nl++);
      while (nr > right[idx])
        push(--nr);
      rem(idx);
    }
  }
};

Verify

//TODO

Licensed under CC BY-NC-ND 4.0
All rights reserved.
Built with Hugo
Theme Stack is designed by Jimmy