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

· · 个人记录

莫队

P3245 [HNOI2016] 大数

后缀差分，查区间 $[l,r]$ 有多少个 $(i,j)$ 满足 $suf_r-suf_l=0$，类似小 z 的袜子，莫队板子。 特判 $2$ 和 $5$ 的情况，因为 $2$ 和 $5$ 是 $10$ 的因数，$2$ 就是对每个偶数求到左端点的距离，$5$ 就是对每个 $0$ 或 $5$ 的位置求，前缀和一下即可。 ### [P3604 美好的每一天](https://www.luogu.com.cn/problem/P3604) 比较聪明。把字母转化一下。 $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](https://www.luogu.com.cn/problem/P4462)，莫队维护区间异或等于 $x$ 的。 ### 莫队区间众数（可离线） 用堆存储出现次数。 维护一个数据结构。 $O(1)$ 插入删除，$O(1)$ 修改，$O(\sqrt n)$ 查询最大值。 值域分块。 如果某个块 $1$ 的个数等于 $0$，找下一个块，否则在块内暴力找。 莫队增删时直接更改值域分块的值，查的时候上述方法查。 ### [P4137 Rmq Problem / mex](https://www.luogu.com.cn/problem/P4137) 如果出现过就标记为 $1$，值域分块，从第一个块开始，如果 $1$ 的个数等于块的长度，就找下一个，否则块内找，套个莫队。 ### [CF877F Ann and Books](https://www.luogu.com.cn/problem/CF877F) 这个题特别聪明。 把第二类标记成 $-1$，第一类标记成 $1$，求和等于 $k$ 就行了。 --- ### 题 给定一个序列，每次给出 $k$ 个区间，求 $k$ 个区间的并有多少个不同的颜色。 $n,m,k\le10^5$，时限 $3s$。 bitset 合并，每个区间有一个 01 串（用 bitset 存），表示这个颜色有没有出现过。合并就是将 bitset 或起来。 莫队处理每个区间的 bitset。 循环利用空间，把询问分成前一半后一半，只用开一半的 bitset。 莫队会慢一点，但是只慢一点。 --- ### [P4688 [Ynoi2016] 掉进兔子洞](https://www.luogu.com.cn/problem/P4688) 有点聪明 删掉三个区间中出现次数最少的那次的个数。 每次查询每个区间维护一个长度为 $n$ 的 bitset，原序列中有几个该数字，就占几位。（这个我不会语言描述，举个例子） 比如 `1 1 1 1 1 1 4 4 5 5 8 9 9`。 如果有区间中的 $1$ 从第一个位置开始往后放，有 4 就从 第 $7$ 个位置开始放，有 $5$ 就从第9个位置开始放。 这样就可以保证数字的位置是一致的，此时把 bitset 与起来就是共同出现的数字及个数。 这种题莫队的作用是搞出 bitset，查询时把 bitset 与起来就行了。 ### [P3674 小清新人渣的本愿](https://www.luogu.com.cn/problem/P3674) 比较聪明 差的情况，开值域大小的 bitset，如果有这个值就是 $1$，将 bitset 左移（右移也一样）$x$ 位，与上原来的，如果 bitset 中有 $1$，就说明有。 和的情况只需要建一个负作差的就行了。 乘的情况：查询的数 $x$ 将它分解成两个数的乘积，查这两个数有没有就行，分解出来的数对数量小于 $\sqrt n$。 bitset 用莫队处理。 ### [P6134 [JSOI2015] 最小表示](https://www.luogu.com.cn/problem/P6134) 拓扑排序过程中维护一个 bitset 表示能到的点。 发现如果 $x$ 能到 $y$，$x$ 能到 $z$，$z$ 能到 $y$，则 $x$ 到 $y$ 能删。 枚举每条边两端的点，bitset 与起来，如果有 $1$ 那么这条边可以删。 ## 回滚莫队 维护具有可减性的信息时（如区间最大值），尽管我们可以快速扩展区间，但无法高效地缩短区间，考虑如何不删除地回答询问。这看似是不可能的，但即使是不可减的信息可可以快速撤销。 仍然维护两个指针 $l,r$，对于每个块，初始左指针l指向下一个块的开头，这样左指针不会影响当前的答案，并且可以记录历史答案，右指针 $r=l-1$ 表示当前区间为空，对于右端点，由于其有序，我们可以直接扩展。右端点扩展完毕后，再扩展左端点直到目标位置并记录答案。需要维护一个历史答案。 每次询问完撤销左端点对信息的影响，再进行下一个询问。 排序后右端点递增，只会往后扩展，不会删除，左端点可能会删除，记历史答案，查询时先将左端点置于当前查询的位置，再扩展右端点。 ## 带修莫队 强行加上一维修改时间戳，然后排序方式按照左端点所在块、右端点所在块和时间来排。导致块内的修改时间都是单调递增的。 这类问题块的大小一般是 $B=n^{\frac{2}{3}}$。 ### [P5906 【模板】回滚莫队&不删除莫队](https://www.luogu.com.cn/problem/P5906) 回滚莫队板子题。 先把询问离线，然后还是按照左端点所在的排序，块内右端点排序。 对于左端点再某个块内的所有查询，具体可以分为两种。 对原序列分个块，如果询问的左右端点再同一个块内，暴力查询。 根据之前的排序，保证了左端点为同一个块是右端点的单调递增，这时我们只需要让左端点进行回滚。暴力一点，每次把左端点赋成所在块的右边界，然后往左扫，单次扫是根号的，而且右端点是单调的，总体是 $O(n\sqrt n)$。 ### [P1903 [国家集训队] 数颜色 / 维护队列](https://www.luogu.com.cn/problem/P1903) 带修莫队板子题 对于某个询问，用 $(l,r,t)$ 来表示。其中 $l$，$r$ 表示询问在序列上的区间，$t$ 表示当前询问的时间，即在此询问之前进行了多少次修改操作。 首先类似普通莫队，对询问排序，不同的是 $l$ 和 $r$ 都要按照块排序，然后再把 $t$ 从小到大排序。 这样普通莫队的操作就变成了三维莫队。我们每次询问前进行对于时间维度的修改操作即可。