P14638 [NOIP2025] 序列询问

251Sec · 2025-12-01 14:03:15 · 题解

我做法怎么好像和大家不太一样。

首先如果确定了区间必须经过序列的中点，那么对于另一个给定的点，区间是否覆盖它只和区间左右端点里的一个有关，枚举这个端点，对另一个端点单调队列即可。

于是我们得到了 O(nq\log n) 的做法，就是直接分治套上面的算法，但是这没啥用。

回忆经典题目 P9877 做法定长分块。按 R 分块，那么合法区间一定不会跨过一整块。在相邻块的就是确定必须经过一点的问题。在同一块内的，再次按 L 分块，那么跨过一整块的区间必合法，经过相邻块的区间仍然用相同办法处理，一块内的区间必不合法。于是就做到了 O(nq)，而且不需要任何预处理。