莫队

Part -1 前言

本文为莫队学习笔记，如果有错误，请提出，谢谢捏。

Part 0 目录

• 普通莫队

  • 1.形式
  • 2.算法流程
  • 3.小trik
  • 3.例题

Part 1 普通莫队

1.形式

假如说通过区间 \([l,r]\) 的答案可以 \(O(1)\) 求出 \([l - 1,r]\)，\([l + 1,r]\)，\([l,r - 1]\) 和 \([l,r + 1]\) 的答案那么我们求可以在 \(O(n \sqrt n)\) 的时间内解决问题。

相当于在平面直角坐标系上有 \(n\) 个散点，然后我们用莫队来串起这 \(n\) 个散点。

2.算法流程

先把所有的问题离线下来，然后以 \(l\) 所在的块的编号为第一关键字，以 \(r\) 为第二关键字。

然后求答案即可。放一个移动求答案的代码。

void solve()
{
    sort(q + 1,q + m + 1);
    for(int i = 1;i <= m;i+++)
    {
        query &now = q[i];
        while(l > now.l)
        {
            move(--l,1);
        }
        while(r < now.r)
        {
            move(++r,1);
        }//先扩大区间，防止区间变为负的
        while(l < now.l)
        {
            move(l++,-1);
        }
        while(r > now.r)
        {
            move(r--,-1);
        }//缩小区间
    }
}

3.小trik

我们知道如果按照 \(l\) 为关键字的话，莫队会走完这一行，然后回到最开头，向上走一格，然后继续走这一行。

但是我们可以直接到尽头时向上走，然后倒退回去，这样这两行只需要两次就可以遍历完。但是不这样就需要四次。

所以我们可以在奇数行的时候按照普通的，否则我们倒着排序。

4.例题

1.小Z的袜子

莫队模板题。

对于 \([l,r]\) 区间取到两个相同颜色的袜子的情况数为 \(\sum^{i\le n}_{i=1} cnt_i \times(cnt_i - 1)\)。总情况数就是 \((r - l + 1) \times (r - l)\)。

然后我们用莫队维护 \(cnt\) 即可。

code