不多说直接上题
P1903
给定一个颜色序列，支持一下两种操作：
- 给定 $l,r$ 求区间 $[l,r]$ 内颜色数量。
- 单点修改颜色。
带修莫队板子。
考虑在三维空间里移动询问点 $(l,r,t)$ 表示区间左右端点和处理过的询问的个数。那么就可以直接做，显然移动的复杂度都是 $O(1)$。
考虑排序时分块，设块长为 $b$，那么长度上会分为 $\dfrac nb$ 块。我们按照左端点编号第一关键字、右端点编号第二关键字、时间第三关键字来排序。假设询问次数与区间长度同阶，那么在左端点块编号不变时右端点会移动 $\dfrac nb\cdot b=n$ 次，因此右端点一共会移动 $nb$ 次，而左端点一共会移动 $nb$ 次，时间在两个块编号都不变的时候移动 $n$ 次，因此总共移动 $n\cdot\left(\dfrac nb\right)^2=\dfrac{n^3}{b^2}$ 次。我们平衡复杂度得到 $b=O(n^{\frac 23})$ 时复杂度最优，为 $O(n^{\frac53})$。
1 |
|
P4396
给定一个数列，多次给定区间 $[l,r]$ 和区间 $[p,q]$，求 $i\in[l,r]$ 时 $a_i\in[p,q]$ 的 $i$ 数量和 $a_i$ 数量。$n\le10^5$。
考虑朴素的方法是莫队之后转移时用树状数组维护权值区间即可，但是移动指针复杂度是 $O(\log n)$。
用值域分块维护上述过程，因为移动指针是单点修改因此复杂度是 $O(1)$ 的，而查询时虽然是 $O(\sqrt n)$ 但是乘在 $m$ 上不影响复杂度，总时间复杂度是 $O(n\sqrt n+m\sqrt n)$。
1 |
|
SP10707
给定一棵树，每个节点有一个颜色，多次询问一段路径上的颜色种数。
树上莫队。使用括号序转化成序列上的问题。
我们 dfs 整棵树，在访问一个节点的时候将它压入括号序列，在离开它的子树之前再压一次。这样括号序列的长度恰好是 $2n$。记 $u$ 第一次和第二次出现的下标为 $st_u$ 和 $ed_u$。
考虑怎么提取 $u\to v$ 的路径。首先我们钦定 $st_u<st_v$。如果 $v$ 是 $u$ 的后代，那么就可以直接取 $[st_u,st_v]$ 作为计算区间（删除其中重复的元素）；如果不是，那么就可以取 $[ed_u,st_v]\cup\operatorname{lca(u,v)}$ 作为计算区间（因为这一部分中既不包含 $st_l$ 又不包含 $ed_l$。同样要删除重复元素）。
那么就可以直接跑莫队啦，因为一个元素被计算两次就是没有，因此维护一个 $vis_u$ 代表有没有计算 $u$ 的贡献。
1 |
|
P3709
定义一个数组的权值的计算方式如下：
有一个可重集合 $S$，初始为空。还有一个变量 $cnt$ 初始为 $1$。
每一步你可以选择一个数 $x$，在原数组中删除它。如果存在 $y\in S$ 且 $y\ge x$，那么 $cnt\leftarrow cnt+1$ 并且清空 $S$。最后将 $x$ 放入 $S$。
权值是所有放入集合顺序中 $cnt$ 可能的最小值。
有一个长度为 $n$ 的数组和 $m$ 次查询，每次询问子数组 $a_l,a_{l+1},\dots,a_r$ 的价值。
说人话就是区间众数的出现次数。
离线可以莫队。在线就是蒲公英。
首先加数是好做的，直接维护每个数出现的次数和 $ans$ 取 max 即可。删除的时候需要维护 $sum_i$ 表示出现次数为 $i$ 的个数。如果删除的那个权值出现次数不是最大的那么没有影响；如果是且是唯一的那么 $ans$ 要减 $1$，否则没有影响。
1 |
|
P5906
给定一个数组和 $m$ 次询问，每次询问查询区间内两个相同的数的最远距离，定义为下标差的绝对值。
增加点非常好做，我们维护每个数出现的最左最右两个位置，然后直接修改并更新答案即可。
删除非常难做，但是我们可以利用回滚莫队规避删除操作。
我们枚举当前操作左端点的块编号并且在到达一个新块 $[L,R]$ 的时候重置左端点 $l=R+1$、右端点 $r=R$（是个空区间）。如果当前询问两个端点块编号相同那么直接暴力求答案；否则我们先将右端点扩展到对应的端点，然后记录下来当前的状态，然后将左端点向左扩展到对应位置，记录答案，再将之前记录的状态全部还原（称为回滚），并将 $l$ 重置为 $R+1$。
显然回滚的复杂度也是块长的，因此复杂度还是 $O(m\sqrt n)$。
1 |
|