$\rm{0x01}$ 关于莫队

对于这种区间询问不修改的题目,可能首先联想到的就是暴力 / 线段树求解。

但是这些方法效率很低,于是莫队算法由此产生。我个人看来,莫队就是一种较快速的暴力求解,也就是优雅的暴力。

莫队是用于解决一类离线区间询问问题的算法。假设 $n \ = \ m$ ,如果从 $[l,r]$ 的答案可 $\mathcal{O(1)}$ 地扩展到与 $[l,r]$ 相邻的区间,那么就能在 $\mathcal{O(n\sqrt{n})}$ 的复杂度内求出所有询问答案。

这里引用一段某管理大爷的讲解:

莫队是啥?

对于这题和大多数莫队题而言,可以离线处理区间的询问.

莫队算法要满足的必要条件是我必须O(1)移动相邻区间

我们考虑用两个指针维护我们要找的区间

很显然我们移动的越少 跑得就越快是吧?

所以我们把询问抽象成点

就是要求曼哈顿距离的最小生成树。

这个直接跑普通最小生成树算法很爆炸

一般人就都是分块求的。

看不懂是吧?那就对了233。通过这道例题,我们来感性认知一下莫队到底是个啥子

$\rm{0x02}$ 一些操作

莫队的实现其实很好理解。如果是普通暴力可能会在询问区间内移动、计数算出答案,可是如果在序列的首尾询问的话移动就吃不消了。

我们考虑离线,经过排序后顺序处理询问,再从上一个区间移动到下一个区间。如何排序?对于 $[l,r]$ 区间,我们以 $l$ 所在的块的编号作为第一关键字排序, $r$ 作为第二关键字排序。

裸莫队其实差不多,代码后面会详细讲,基本长这样:

    for(register int i = 1; i <= m; ++i)
    {
        while(l < q[i].l) dec(l++);
        while(l > q[i].l) add(--l);
        while(r < q[i].r) add(++r);
        while(r > q[i].r) dec(r--);
        //do something...
    }

关于块的大小 $S$ 通常设为 $\frac{n}{\sqrt{m*\frac{2}{3}}}$ ,来自 lxl 的毒瘤推荐。

排序我们使用奇偶性排序,即两块编号相同时,奇数编号则 $r$ 升序,偶数编号则 $r$ 降序。

$\rm{0x03}$ 关于此题

前面说了很多前置芝士,这道题也是一道很好的莫队练手题。我的思路和其他题解有所不同,可能更便于理解(毕竟是蒟蒻 yy 的

题目大意是小 Z 现在有一排妹子,给出一堆询问

哦,不,是袜子。

要求的是在 $[l,r]$ 中抽到一整双袜子的概率。

$ $

首先我们得想想,这 $[l,r]$ 里到底有多少对袜子(不考虑颜色相同)

![](01)

这不小学奥数题嘛,第一只袜子可以和后面四只组队,第二只和后面三只... ... 以此类推,我们得到总数 $tot\ =\ 1+2+..+k+(r-l) \ =\ (1+r-l)×\frac{r-l}{2}$ 。r是序列最后一只的编号,l是序列第一只的编号,k是式子中的某一项

同样的,我们设第 $i$ 只袜子在序列 $[l,r]$ 里有 $cnt_i$ 只,可以和它配对的袜子有几只呢?机智的你一定想出了答案,第 $i$ 只的可配对总数 $ret_i \ = \ 1+2+..+k+cnt_i-1 \ = \ (1+cnt_i-1)×\frac{cnt_i-1}{2} \ = \ \frac{cnt_i×(cnt_i-1)}{2}$

可以手推想一下,我们假设袜子相同的情况:

![](02)