题解：P17741 [ICPC 2019 Xuzhou R] K-rectangle

IkunTeddy · 2026-10-23 18:25:17 · 题解

题目分析

我们显然能够列出一个转移 f_{i}=\min\limits_{j=1}^{i}w(j,i)+f_{j-1}，其中 w(j,i)=(x_i-x_j+k)\times \max\limits_{p=j}^{i}y_p ，直接做是 O(n^2) 的。

接下来介绍两种做法。

法一：

考虑 CDQ 分治优化转移，对于当前区间 [l,r] 和区间中点 mid，我们对 [l,mid] 预处理出后缀 y 的最大值 mx_j，对 [mid+1,r] 预处理出前缀 y 的最大值 mx_i。那么现在对于跨越点对 w(j,i)=(x_i-x_j+k)\times \max(mx_j,mx_i)。

考虑分讨 mx_j,mx_i 的大小关系：

时间复杂度 O(n\log n)，空间线性。

法二：

转移中带一个后缀最大值，考虑用单调栈。

显然单调栈把整个序列分成了若干段，对于同一段元素，我们显然只用保留 -x_j\times mx+f_{j-1} 最大的元素，我们为每一段开一棵李超线段树，把 (-x_{j},f_{j- 1}) 当作点就可以求出这个东西了。考虑单调栈操作有什么影响，相当于就是合并一个后缀的所有段，所以我们直接用李超合并即可。

考虑查询，我们把所有段的最优元素再插进一个李超中，这样就可以查询了。还是考虑单调栈操作有什么影响，就相当于撤销掉一个后缀的所有修改，然后在末尾加一个元素，所以我们维护一个可持久化李超就可以支持撤销操作了。

时空复杂度均为 O(n\log n)。

虽然说还存在一些 O(n\log^2 n)/O(n\sqrt n) 的做法，但是本质思路是一样的。代码显然是没写的，有什么问题可以评论。