Mo's Algorithm

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