腾飞计划寒假第六课——莫队 2025/2/7

$suf_i$ 是算出来的后缀 $i$ 位 $\mod p$ 的值。

后缀差分，查区间 $[l,r]$ 有多少个 $(i,j)$ 满足 $suf_r-suf_l=0$，类似小 z 的袜子，莫队板子。

特判 $2$ 和 $5$ 的情况，因为 $2$ 和 $5$ 是 $10$ 的因数，$2$ 就是对每个偶数求到左端点的距离，$5$ 就是对每个 $0$ 或 $5$ 的位置求，前缀和一下即可。

比较聪明。把字母转化一下。

$a\rarr2^0,b\rarr2^1,c\rarr2^2,\dots,z\rarr2^{25}$。

将区间的数异或起来，最终数字二进制位 $1$ 的个数小于等于 $1$，即异或和等于 $0,1,2,4,\dots,2^{25}$。

开一个桶存状态，莫队插入时枚举 $0,1,2,4,\dots,2^{25}$，看原来的数异或和异或插入的数等于哪个，统计答案。类似 P4462，莫队维护区间异或等于 $x$ 的。

用堆存储出现次数。

维护一个数据结构。

$O(1)$ 插入删除，$O(1)$ 修改，$O(\sqrt n)$ 查询最大值。

值域分块。

如果某个块 $1$ 的个数等于 $0$，找下一个块，否则在块内暴力找。

莫队增删时直接更改值域分块的值，查的时候上述方法查。

如果出现过就标记为 $1$，值域分块，从第一个块开始，如果 $1$ 的个数等于块的长度，就找下一个，否则块内找，套个莫队。

这个题特别聪明。

把第二类标记成 $-1$，第一类标记成 $1$，求和等于 $k$ 就行了。

给定一个序列，每次给出 $k$ 个区间，求 $k$ 个区间的并有多少个不同的颜色。

$n,m,k\le10^5$，时限 $3s$。

bitset 合并，每个区间有一个 01 串（用 bitset 存），表示这个颜色有没有出现过。合并就是将 bitset 或起来。

莫队处理每个区间的 bitset。

循环利用空间，把询问分成前一半后一半，只用开一半的 bitset。

莫队会慢一点，但是只慢一点。

有点聪明

删掉三个区间中出现次数最少的那次的个数。

每次查询每个区间维护一个长度为 $n$ 的 bitset，原序列中有几个该数字，就占几位。（这个我不会语言描述，举个例子）

比如 1 1 1 1 1 1 4 4 5 5 8 9 9。

如果有区间中的 $1$ 从第一个位置开始往后放，有 4 就从 第 $7$ 个位置开始放，有 $5$ 就从第9个位置开始放。

这样就可以保证数字的位置是一致的，此时把 bitset 与起来就是共同出现的数字及个数。

这种题莫队的作用是搞出 bitset，查询时把 bitset 与起来就行了。

比较聪明

差的情况，开值域大小的 bitset，如果有这个值就是 $1$，将 bitset 左移（右移也一样）$x$ 位，与上原来的，如果 bitset 中有 $1$，就说明有。

和的情况只需要建一个负作差的就行了。

乘的情况：查询的数 $x$ 将它分解成两个数的乘积，查这两个数有没有就行，分解出来的数对数量小于 $\sqrt n$。

bitset 用莫队处理。

拓扑排序过程中维护一个 bitset 表示能到的点。

发现如果 $x$ 能到 $y$，$x$ 能到 $z$，$z$ 能到 $y$，则 $x$ 到 $y$ 能删。

枚举每条边两端的点，bitset 与起来，如果有 $1$ 那么这条边可以删。

维护具有可减性的信息时（如区间最大值），尽管我们可以快速扩展区间，但无法高效地缩短区间，考虑如何不删除地回答询问。这看似是不可能的，但即使是不可减的信息可可以快速撤销。

仍然维护两个指针 $l,r$，对于每个块，初始左指针l指向下一个块的开头，这样左指针不会影响当前的答案，并且可以记录历史答案，右指针 $r=l-1$ 表示当前区间为空，对于右端点，由于其有序，我们可以直接扩展。右端点扩展完毕后，再扩展左端点直到目标位置并记录答案。需要维护一个历史答案。

每次询问完撤销左端点对信息的影响，再进行下一个询问。

排序后右端点递增，只会往后扩展，不会删除，左端点可能会删除，记历史答案，查询时先将左端点置于当前查询的位置，再扩展右端点。

强行加上一维修改时间戳，然后排序方式按照左端点所在块、右端点所在块和时间来排。导致块内的修改时间都是单调递增的。

这类问题块的大小一般是 $B=n^{\frac{2}{3}}$。

回滚莫队板子题。

先把询问离线，然后还是按照左端点所在的排序，块内右端点排序。

对于左端点再某个块内的所有查询，具体可以分为两种。

对原序列分个块，如果询问的左右端点再同一个块内，暴力查询。

根据之前的排序，保证了左端点为同一个块是右端点的单调递增，这时我们只需要让左端点进行回滚。暴力一点，每次把左端点赋成所在块的右边界，然后往左扫，单次扫是根号的，而且右端点是单调的，总体是 $O(n\sqrt n)$。

带修莫队板子题

对于某个询问，用 $(l,r,t)$ 来表示。其中 $l$，$r$ 表示询问在序列上的区间，$t$ 表示当前询问的时间，即在此询问之前进行了多少次修改操作。

首先类似普通莫队，对询问排序，不同的是 $l$ 和 $r$ 都要按照块排序，然后再把 $t$ 从小到大排序。

这样普通莫队的操作就变成了三维莫队。我们每次询问前进行对于时间维度的修改操作即可。