CF1039E Summer Oenothera Exhibition

发表于 分类于 ， ， 阅读次数：

题意：给定一个长度为 的序列。

组询问，每次给出一个常数 。求最少把序列分为多少段使得每段序列中数的极差不超过 。

允许离线，，时限 。

首先不难针对单组询问想到暴力：每次贪心划分，能不分就不分。正确性较为显然。

似乎难以得出更强的性质，考虑优化这个过程。

设 为第 个位置分出一段，最远能到达哪里。

这样，若在 之间连边， 就是答案。

这些边会新成一棵树，不难想到使用 来维护。

接下来，将询问离线，按极差约束从小到大来回答。

显然 会逐渐变大，但是总变化次数可能高达 ，不能承受。

考虑根号分治。

若 才使用 维护。

由于 只会增加，这部分的总变化次数为 。

这样会形成森林而非单棵树，可以发现，由于超过 的边才会导致断开，森林中树的总数不超过 。

我们利用 每次跳过一棵树。

接下来，就是 个单点求解 的询问。

这里使用 表配合二分，写成倍增常数会小一些。

总复杂度 。

实现细节：

  • 的 次变化如何找到。

    每次 变化后，二分出下一次变化所需的极差,然后用 std::vector 来分配给每个询问。

  • 怎么用 每次跳过一棵树。

    中编号大的点总是为父亲，这样 access 一下就得到我们想要的路径了。