从我的notion复制过来的，有点失真。
参考1 https://www.hackerearth.com/practice/notes/mos-algorithm/
参考2 https://ei1333.hateblo.jp/entry/2017/09/11/211011

基础莫队

• 模板

        struct Mo {
          int n;
          std::vector<std::pair<int, int> > lr;

          explicit Mo(int n) : n(n) {}

          void add(int l, int r) { /* [l, r) */
            lr.emplace_back(l, r);
          }

          template <typename AL, typename AR, typename EL, typename ER, typename O>
          void build(const AL &add_left, const AR &add_right, const EL &erase_left,
                     const ER &erase_right, const O &out) {
            int q = (int)lr.size();
            int bs = n / std::min<int>(n, sqrt(q));
            std::vector<int> ord(q);
            std::iota(std::begin(ord), std::end(ord), 0);
            std::sort(std::begin(ord), std::end(ord), [&](int a, int b) {
              int ablock = lr[a].first / bs, bblock = lr[b].first / bs;
              if (ablock != bblock) return ablock < bblock;
              return (ablock & 1) ? lr[a].second > lr[b].second
                                  : lr[a].second < lr[b].second;
            });
            int l = 0, r = 0;
            for (auto idx : ord) {
              while (l > lr[idx].first) add_left(--l);
              while (r < lr[idx].second) add_right(r++);
              while (l < lr[idx].first) erase_left(l++);
              while (r > lr[idx].second) erase_right(--r);
              out(idx);
            }
          }

          template <typename A, typename E, typename O>
          void build(const A &add, const E &erase, const O &out) {
            build(add, add, erase, erase, out);
          }
        };

Problem List

• [x] AcWing2492. HH的项链

  • 题意

    给定M个查询，求区间[l, r]内不同数字的个数。

  • 思路

    莫队模板题

  • 代码

        void solve() {
          int n;
          std::cin >> n;
          std::vector<int> A(n);
          for (auto &c : A) std::cin >> c;
          int q;
          std::cin >> q;
          Mo mo(n);
          for (int i = 0; i < q; i++) {
            int l, r;
            std::cin >> l >> r;
            mo.add(l - 1, r);
          }
          std::vector<int> cnt(1000005), ans(q);

          int sum = 0;
          auto add = [&](int i) {
            if (cnt[A[i]]++ == 0) ++sum;
          };
          auto erase = [&](int i) {
            if (--cnt[A[i]] == 0) --sum;
          };
          auto out = [&](int q) { ans[q] = sum; };
          mo.build(add, erase, out);
          for (auto &p : ans) std::cout << p << "\n";
        }

• [x] SPOJ FREQUENT - Frequent values

  • 题意

    给定M个循环，和一个可能带有负数的数组，求区间内出现最多的数字出现的次数。

  • 思路

    首先有负数，要加个offset。

    然后维护三个值

    1. 每个值出现的次数
    2. 每个值出现次数的次数
    3. 当前出现最多数字出现的次数，就是答案

    每次增加新数字的时候，当前值出现的次数的次数- 1，当前值出现的次数 + 1，新次数 + 1

    如果当前值出现的次数大于了now，则更新now。

    每次减少新数字的时候，当前值出现的次数的次数也是-1， 当前值出现的次数 - 1，新次数 + 1

    如果当前值出现的次数小于了now，且当前值出现的次数的次数变成0了，说明now需要减少，已经没有出现这个次数的数了。

    其实有点小绕人，要理解出现的次数的次数的概念。总体不难。

  • 代码

        void solve() {
          int n, q;
          while (std::cin >> n && n) {
            std::cin >> q;
            std::vector<int> A(n);
            for (auto &c : A) {
              std::cin >> c;
              c += 100000;
            }
            Mo mo(n);
            for (int i = 0; i < q; i++) {
              int l, r;
              std::cin >> l >> r;
              mo.add(l - 1, r);
            }
            std::vector<int> cnt(200005); // 数字出现次数
            std::vector<int> reach(200005); // 数字出现次数的次数
            std::vector<int> ans(q);
            int now = 0;
            auto add = [&](int i) {
              reach[cnt[A[i]]]--;
              cnt[A[i]]++;
              reach[cnt[A[i]]]++;
              if (cnt[A[i]] > now) {
                now = cnt[A[i]]; // now ++ 也是一样的 每次移一个
              }
            };
            auto erase = [&](int i) {
              reach[cnt[A[i]]]--;
              if (cnt[A[i]] == now and reach[cnt[A[i]]] == 0) --now;
              cnt[A[i]]--;
              reach[cnt[A[i]]]++;
            };
            auto out = [&](int q) { ans[q] = now; };
            mo.build(add, erase, out);
            for (auto &p : ans) std::cout << p << "\n";
          }
        }

• [x] ABC242G Range Pairing Query

  • 题意

    给定M个询问，问每个区间[l, r]内部有多少个pair，每个pair的数字要相同。

  • 思路

    维护每个数字的count，根据奇偶性进行判断即可。

  • 代码

        void solve() {
          int n, q;

          std::cin >> n;
          std::vector<int> A(n);
          for (auto &c : A) {
            std::cin >> c;
          }
          std::cin >> q;
          Mo mo(n);
          for (int i = 0; i < q; i++) {
            int l, r;
            std::cin >> l >> r;
            mo.add(l - 1, r);
          }

          std::vector<int> cnt(100005);
          std::vector<int> ans(q);

          int now = 0;
          auto add = [&](int i) {
            cnt[A[i]]++;
            if (cnt[A[i]] % 2 == 0) {
              now++;
            }
          };
          auto erase = [&](int i) {
            cnt[A[i]]--;
            if (cnt[A[i]] % 2 != 0) {
              now--;
            }
          };
          auto out = [&](int q) { ans[q] = now; };
          mo.build(add, erase, out);
          for (auto &p : ans) std::cout << p << "\n";
        }