$$\text T1\ : \text{Rolling Girl}$$

题目描述 :

$$\max_{l \leq i,j \leq r , \text A(num_i)-\text A(num_j) \leq \text K} \text A(num_i)$$

• 做法 $1$ :

考虑回滚莫队 , 每一次 $\text A(num_i)$ , 直接在线段树里面插入。查询的时候直接弄就可以了 , 复杂度 $O(NM^{\frac{1}{2}} \log N)$。

• 做法 $2$ :

我们设一个 $\text{recf}$ 数组 , $\text{recf}_i$ 表示存在的 $[i-\text K \leq j \leq i-1][j=\text A(num_d)]$ 的个数。那么很显然 , 如果这个东西被单点修改了 , 那么是可以做到 $O(1)$ 维护的。那么我们可以继续设一个 $\text{appe}_i$ 代表 $[i=\text A(num_d)]$ 的个数 。 如果 $[\text{appe}_i>0][\text{recf}_i>0]$ 的话就是有贡献的 , 我们再用 $\text{tech}$ 存 $[\text{appe}_i>0][\text{recf}_i>0]$ 就可以了。对于 $\text{tech}$ 数组 , 我们进行分块就可以了。查询的时候就直接从后往前查询 , 查询到第一个有 $1$ 的位置就是答案。

复杂度 $O(NM^{\frac{1}{2}}+N^{\frac{3}{2}})$.

---

$$\text T2\ : \text{Angel of Sin}$$

题目描述 :

$$\sum\limits_{l \leq i,j \leq r} [num_i\ \text{mod}\ num_j=k]$$

• 做法 $1$ :

暴力 $O(N^2M)$ 飞过。

考虑莫队 , 由于 $num_i\ \text{mod}\ num_j$ 可以在 ${\max num_i}^{\frac{1}{2}}$ 以搜索状态 , 所以可以做到 $O(NM^{\frac{1}{2}}{\max num_i}^{\frac{1}{2}})$。

顺带一提 , 如果各位找到了代码短且足够暴力 $O(NM)$ 的做法可以跟我说 , 我至今未能找到。

• 做法 $2$ :

二次离线莫队 , 套路题。

首先我们上一个莫队 , 那么就只剩转移 , 注意贡献分两类 :

随后我们用链式前向星连一下即可。时间复杂度 $O(NM^{\frac{1}{2}}+N\ {\max num_i}^{\frac{1}{2}}+\frac{N^2}{k})$。空间复杂度 : $O(NM^{\frac{1}{2}}+\max num_i)$ , 出题人卡了一点空间 , 靠人品吧。

最后膜拜 $\text{lxl}$ , 太巨了。