P8099 [USACO22JAN] Minimizing Haybales P 题解

直接硬做。考虑每次插入一个点。设这个点是 $arr$ 同时现在是第 $i$ 个点，前面已经排好序的序列是 $p$。那么你需要找到一个后缀区间 $[q,i]$ 使得所有区间内的 $p_j$ 都属于 $[arr-k,arr+k]$。

那么你就随便在 $[q,i]$ 里面插就好了。但是要最优的话就要最靠前。但如果本来有 $p_j \le p_i$ 你还放它前面那不更劣了吗。于是找到第一个 $p_j > p_i$ 的位置把 $arr$ 插到 $j$ 后面就可以了。

然后你考虑在区间上做。我们发现区间平衡树这种操作太牛了，不太会。（这种做法可以参考 @panyf 和 @Alex_wei 的题解）

于是考虑上值域。在 [l,r] 中维护所有当前 $l\le a_i \le r$ 中最小和最大的 $i$。这个显然是可以动态开点的。然后查询的话，对于找 $q$ 我们分别查找 $[1,arr-k)$ 和 $(arr+k,inf)$ 中的最大 $i$（记作 $x$），这个东西的后面就全部满足要求了。所以 $q=x+1$。

然后你发现要找在 $(a_i,inf)$ 中的最小下标并且 $\ge q$ 的一颗线段树好像做不了，于是可持久化，对于每个点都新建一个版本。然后直接做二分，具体类比静态第 $k$ 小的那个问题，用第 $i-1$ 棵线段树和第 $q$ 棵线段树整体作差就行了。

时空复杂度都是 $O(n \log V)$。然后如果你用平衡树的话是 $O(n \log n)$ 的，但是 fhq-treap 的话常数比较大。其他平衡树又不是很好支持分裂这种东西。