「学习笔记」莫队算法

cyhyyds · 2021-07-22 09:06:11 · 个人记录

0x10 莫队算法的概念

莫队算法是由莫涛提出的算法。莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 ——摘自 Oi-wiki。

0x20 普通莫队算法

• 0x21 形式

  给定一个序列 Q ，我们设 n 和 m 同阶。对于序列上的查询问题，给定查询区间 [L_i,R_i]，我们可以以 O(1) 的速度扩展答案到与查询区间相邻的四个区间，即：[L_{i-1}, R]， [L_{i+1}, R] ，[L_i, R_{i+1}] 和 [L_i,R_{i-1}]。 这样，我们实现的时间复杂度就是 O(n×块长）。而我们通常设的块长为 \sqrt{n} ，那么我们的时间复杂度就是 O(n\sqrt{n})，这对于我们 n 达到 10^5 时，是一个非常快速的做法，且代码实现较易。

  代码模板如下：

  for (int i = 1; i <= m; i ++) {
      while (r < mt[i].r) add (++ r); 
      while (l > mt[i].l) add (-- l); 
      while (l < mt[i].l) del (l ++);
      while (r > mt[i].r) del (r --);
      ans[mt[i].id] = res;
  }

• 0x22 实现

  对于 m 个询问，我们将其先存储起来，然后再排序，最后离线处理这些数据。

• 0x23 排序

  正常来说，我们的排序方法都是以 [L_i, R_i] 所在的块的编号为第一关键字，以右端点为第二关键字从小到大排序。

  代码实现如下：

  inline bool cmp (MOTEAM x, MOTEAM y) {
    if (block[x.l] == block[y.l]) {
        //x和y的左端点都在同一个块中时，按右端点进行排序。 
        return x.r < y.r;
    }
  
    if (block[x.l] != block[y.l]) {
        //x和y的左端点不在同一个块中时，按左端点进行排序。 
        return x.l < y.l;
    }
  }

• 0x24 优化

  在很多时候，我们会盲目的将块长设置为 \sqrt{n}，所以如果遇到 m 和 \sqrt{n} 同阶时，而恰好我们将块长设置为 \sqrt{n} 时，这样我们就有可能被构造出的数据卡掉。

  那我们应该将块长设为什么呢？在随机数据下，设为 \frac{n}{\sqrt{\frac{2}{3} m}} 会快一些，大概能优化 \frac{1}{10} 左右。证明留给读者自行探索。

  我们发现，莫队算法实际上看上去仅仅是暴力的优化。但是为什么使用这种"看似暴力"的做法却可以通过高难度数据结构题目呢？很显然，我们的算法复杂度在离线进行排序的时候被优化了。所以，这一排序节省了我们很多的时间。

  于是又有神仙创造出了一种新的排序方法：奇偶性排序。

  首先，我们原来的排序方法，虽然让右端点的大跳动减少了很多。但是，右端点的跳动依旧存在，使我们的时间复杂度大幅度升高。我们能否创造一种方法排序使其更优化呢？

  我们在选择奇数块时，按照右端点从小到大排序，在偶数块时从大到小排序，这样可以减少右端点进行大跳动的次数。

  而为什么这样排序会快呢？是因为右指针移动到右边后就不需要跳回左边了，而跳回左边后处理下一个块是要跳动到右边的。很明显，这样就会优化近一半的时间复杂度。

  代码实现如下：

  inline bool cmp (MOTEAM x, MOTEAM y) {
    return block[x.l] == block[y.l] ? (block[y.l] & 1) ? x.r < y.r : x.r > y.r : x.l < y.l
  }

0x30 普通莫队算法例题

• 0x31 例题 1

  P1972 [SDOI2009]HH的项链

  很经典的一道题。这道题求 [L_i,R_i] 区间只出现过一次的数字个数。这样我们的 add 和 del 函数就很好设计。

  inline void add (int x) {
      cnt[a[x]] ++;
      if (cnt[a[x]] == 1) {
          res ++;
      }
  }
  
  inline void del (int x) {
      cnt[a[x]] --;
      if (cnt[a[x]] == 0) {
          res --;
      }
  }

  但是这道题的出题人也许特意卡莫队做法，正常写法应该是 65pts ，会 TLE 5个点。

  所以我们需要大力卡常！我们运用上面的优化技巧，修改块长，使用奇偶性排序方法，将 add 和 del 改成位运算，提前预处理左端点所在块，吸口氧就可以通过该题了。

  AC CODE

• 0x32 例题 2

  SP3267 DQUERY - D-query

  这道题和上道题几乎相同，我们只需要用正常的莫队做法就可以通过。

  核心代码如下：

  inline void add(int x, int &res) {
    if (num[a[x]] == 0) {
        //次数未增加前该数次数出现次数为0，就没有出现过，即不重复。 
        res ++;
    }
    num[a[x]] ++;
  }
  
  inline void del(int x, int &res) {
    num[a[x]] --;
    if (num[a[x]] == 0) {
        //次数减少后该数次数出现次数为0，就出现过，个数减少。
        res --;
    }
  }

• 0x33 例题 3

  P2709 小B的询问

  我们看到题目，每个数字贡献为出现次数的平方，这样我们的 add 和 del 函数就不太好编写。

  这样我们就需要用到完全平方的小知识解决此题。

  即：

  (a+1)^2 = a^2+1+2a

  于是我们的 add 函数和 del 函数有这种写法：

  inline void add (int x) {
      ans += cnt[a[x]] * 2 + 1;
      cnt[a[x]] ++;
  }
  
  inline void del (int x) {
      ans -= cnt[a[x]] * 2 - 1;
      cnt[a[x]] --;
  }

  但是不要忘记，莫队是暴力美学，当然我们的 add 函数和 del 函数也可以暴力模拟。

  核心代码如下：

  inline void add (int x) {
      memo -= cnt[a[x]] * cnt[a[x]];
      cnt[a[x]] ++;
      memo += cnt[a[x]] * cnt[a[x]]; 
  }
  
  inline void del (int x) {
      memo -= cnt[a[x]] * cnt[a[x]];
      cnt[a[x]] --;
      memo += cnt[a[x]] * cnt[a[x]];
  }

• 0x34 例题 4

  CF86D Powerful array

• 0x35 例题 5

  P3901 数列找不同

  模板题要做吐了qwq。

  同样是统计区间内出现次数为 1 的数字个数，最后判断出现次数为 1 的数字个数是否为该区间所有数字个数就可以了。 核心代码如下：

  for (int i = 1; i <= q; i ++) {
      while (l < mt[i].l) del (l ++);
      while (r < mt[i].r) add (++ r);
      while (l > mt[i].l) add (-- l);
      while (r > mt[i].r) del (r --);
  
      if (res == mt[i].r - mt[i].l + 1) {
          ans[mt[i].id] = 1;
      }
  }

• 0x36 例题 6

  CF617E XOR and Favorite Number

  需要稍微了解异或的性质，其实还是一道普通莫队模板题。

  题目要求求异或为 k 的子区间个数，我们可以先做一个前缀异或和，运用前缀和的性质，我们求的答案就是 R-(L-1)的答案，为了方便我们可以存储左端点的时候就将其减一。

  我们进行 add 和 del 函数的时候操作的是异或 k 后的答案，这样查询的答案也是异或 k 后的，就得到了题目要求的答案。

  核心代码如下：

  inline void add (int x) {
    res += num[(a[x]^k)];
    num[a[x]] ++;
  }
  
  inline void del (int x) {
    num[a[x]] --;
    res -= num[(a[x]^k)];
  }

• 0x37 例题 7

  P4462 [CQOI2018]异或序列

  这是上道题的双倍经验，依旧是存储答案异或 k 后的数字，查询次数也需要查询异或 k 的次数，就可以了。

• 0x38 例题 8

  CF220B Little Elephant and Array

  普通莫队操作。add 和 del 时判断次数是否与元素相同即可。

  核心代码如下：

  inline void add (int x) {
    if (num[a[x]] == a[x]) {
        res --;
    }
  
    num[a[x]] ++;
  
    if (num[a[x]] == a[x]) {
        res ++;
    }
  }
  
  inline void del (int x) {
  
    if (num[a[x]] == a[x]) {
        res --;
    }
  
    num[a[x]] --;
  
    if (num[a[x]] == a[x]) {
        res ++;
    }
  } 

0x40 带修莫队