P8099 [USACO22JAN] Minimizing Haybales P 题解

lovely_qiqi · 2025-12-21 23:44:41 · 题解

直接硬做。考虑每次插入一个点。设这个点是 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 的话常数比较大。其他平衡树又不是很好支持分裂这种东西。