题解 CF765F 【Souvenirs】

· · 题解

我来一发比较难写但是好想的做法。

首先此题可以直接上只减不加的回滚莫队，在过程中维护当前区间的数值按大小排序的链表，由于是找到两个数相减的绝对值最小，那么这个最小值一定是链表上相邻的两个数之间的差。

链表删除是 \mathcal{O(1)} 的，那么考虑如何维护删除后的最小值，可以发现删去一个数相当于把旁边两个数的差值合并，可以用值域线段树/堆维护，但是加上莫队总复杂就会达到 \mathcal{O(n\sqrt{n}\log n)} ，大概率无法通过此题。

比较好入手的方向是修改是 \mathcal{O(n\sqrt{n})} 级别的，但是查询却是 \mathcal{O(n)} 级别的，不难想到根号分治一下，使得修改可以做到 \mathcal{O(1)} ，通用方法是值域分块，维护每一块的包含在内的个数，修改可以通过普通的加减 \mathcal{O(1)} 维护，查询从第一块向后找到第一个包含个数不为 0 的块，然后暴力找整个块求最小值。

但是这题的值域范围很大，直接分块可定不行，所以还要一些处理。

由于这些值都是链表上两个相邻的数的差值，也就是说是总和小于等于 10^9 ，那么根据抽屉原理，如果目前有 x 个数，那么最小值就小于等于 \frac{10^9}{x} 。

那么考虑再来一次根号分治，设一个阙值 B ，对于对于大于 B 的个数可以上值域分块的方法，修改效率 \mathcal{O(n\sqrt{n})} ，查询效率 \mathcal{O(n\sqrt{\frac{10^9}{B}})} ，小于 B 的个数可以直接上值域线段树/堆，修改效率 \mathcal{O(B\sqrt{n}\log n)} ，查询效率 \mathcal{O(n\log n)} 。

数学不太行，大概 B 取到 2000 左右比较好吧。。。

但是回滚莫队查询时要暴力删除小块在小于 B 的个数时是 \mathcal{O(nB\log n)} 的，只调 B 的大小无法获得更优的复杂度，那么考虑调莫队的块的大小，设莫队的块的大小为 A 。

查询操作和 m 的大小以及 B 的大小挂钩，所以只看修改，大于 B 时是 \mathcal{O(\frac{n^2}{A})} ，小于 B 是 \mathcal{O(\frac{nB\log n}{A})} 和 \mathcal{O(AB\log n)} ，取 A=\frac{n}{\sqrt{n\log n}} 时总复杂近似于 \mathcal{O(n\sqrt{n\log n})} ，大概率可以通过此题。