OI

给大家表演一个一场下青

CodeForces Round 770 Div.2 Problem D – Finding Zero

一道非常有意思的交互和构造题。

考虑能否固定两个数$x, y$，通过它们的相对大小关系，确定其他数中是否存在$0$或最大值$a_{\text{max}}$。

经过一番推导，我们发现，设$x \geq y$的情况下，对于三元组$(a_i=x, a_j=y, a_k=z)$，有$$g(i, j, k)\newline =\max(a_i, a_j, a_k) – \min(a_i, a_j, a_k)= \begin{cases}z-y, & z > x \\ x-y, & z \in [y, x]\\ x-z, & z < y\end{cases}$$。所以，设$x=6, y=4$以上式结果为因变量，$z$为自变量，应有以下图像：

（更多…）

终于体会到了“看了题解都可能写不出来”的绝望了——CF925E May Holidays。

自以为已经对“分块”的思想有了一定掌握，到头来发现自己还只会最基本的、应用最广泛的值域分块。只是题见得不够多罢了。

考虑一种实际操作中不会使用的求区间第$k$大的算法。设块长为$S$，我们将序列分成$\mathrm{O}(\dfrac{n}{S})$块，每一块内直接对元素排序。对于一个询问$[l, r]$，我们二分答案。猜测答案为$d$，在中间的每一整块内二分出$\leq d$的元素数量，两侧暴力查找。这样的复杂度是$\mathrm{O}(\dfrac{len}{S} \log^2 n+S \log n)$的，其中$len$代表区间长。

这告诉我们，分块的目的不仅可以让较大的值域范围内的统计变得更高效，还可以使得元素（部分）有序，适用范围更加广泛。就连分块这种暴力数据结构使用时都需灵活变通，其他算法又何尝不是如此。

（更多…）