自动搬运

查看原文

来自洛谷，原作者为

	KingPowers 重开了

搬运于2025-08-24 22:38:56，当前版本为作者最后更新于2025-01-06 16:08:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑一个重排后的排列应该长什么样子，不妨固定住一对 $l,r$ 满足 $l<r$，要求就是不能同时存在 $l<k_1,k_2<r$ 使得 $p_{k_1}<\min(p_l,p_r)$ 和 $p_{k_2}>\max(p_l,p_r)$，换句话说也就是 $p_l,p_r$ 里至少要有一个是区间 $[l,r]$ 的最值。

换个角度看，假设一开始有 $1$ 到 $n$ 这些数，要把它们排成一个合法的排列，就要求每次必须把当前的最大值/最小值插到当前没被插入数的最靠前/最靠后的位置，排列合法当且仅当每一步都满足这个条件，而我们希望最大化插入过程中与原排列重合的位置数量。

然后就有个暴力的区间 dp 做法，可以设 $f_{l,r,x}$ 表示区间 $[l,r]$ 以外的部分已经填完，当前剩下的最大值为 $x$ 时区间内最大的重合位置数量，转移直接枚举在左右端点填最大/最小值四种情况是 $O(1)$ 的，所以得到了一个 $O(n^3)$ 的做法，可以通过 $70$ 分。

继续优化，考虑在二维平面的角度上看这个问题。因为新排列一个区间内的数在值域上肯定是连续的，把 $p_i$ 看成平面上的点 $(i,p_i)$，那么对于 $p$ 的一个区间 $[l,r]$ 能包住区间内的点的最小矩形就是 $x\in[l,r],y\in[d,u]$ 的这么一个矩形，其中 $d,u$ 分别是区间内的最小值和最大值。而因为每次只会填左右端点的一个最值， 那么填完之后剩下的子区间对应的矩形 $u,d$ 的变化量只有 $1$，也就是说每次会删去当前矩形边缘的一个 L 形。而初始时整个排列对应的矩形显然是 $x\in[1,n],y\in[1,n]$ 这么个大正方形，所以每个区间对应的矩形也都应当是个正方形。

对于一个 $p_i$ 来说，它与新的排列重合相当于是 $(i,p_i)$ 作为了某个区间对应正方形的四个顶点之一。考虑到所有以 $(i,p_i)$ 为顶点的正方形其对应的另一个顶点坐标都形如 $(i\pm len,p_i\pm len)$（正负号对应了四个方向），对每个 $(i,p_i)$ 都把这种正方形找出来，发现问题其实可以转化为：平面内有 $O(n^2)$ 个正方形，你需要选择尽可能多的正方形使得它们之间是严格包含的关系。这是因为对于选出来的这些正方形，因为只有包含关系，我们一定能构造出一组方案使得这些正方形同时出现过，每出现过一个就多一个位置不需要交换，所以答案就是 $n$ 减去最多选出的正方形个数。

设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向延伸出的长度为 $j$ 的正方形（$dir\in\{0,1,2,3\}$），最多包含几个其它的正方形，转移考虑从满足 $k<i\And l< j$ 的 $f_{k,l,*}$ 转移，分类讨论不同方向之间的正方形成包含关系的条件，能够把转移限制表示成二维偏序，这个 dp 能够做到 $O(n^2\log n)$，但是本身 $n$ 就 $8000$ 而且常数太大了肯定过不去。

发现题目里还有随机排列的条件没有用，可以感受到随机排列的情况下能够选出的正方形不会太多，改成设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向的正方形要包含 $j$ 个其它的正方形，最小的边长是多少，转移同样可以分类讨论变成二维偏序。一个结论就是 $j$ 这一维的大小是 $O(\sqrt n)$ 级别的，大概就是与随机排列的 LIS 长度是同阶的，所以这样就能做到 $O(n\sqrt n\log n)$，可以通过。

这里补充下具体怎么把转移写成二维偏序，假设我们现在要对 $f_{i,j,0}$ 进行转移，考虑之前 $j'=j-1$ 时的一个矩形 $x\in[l,r],y\in[d,u]$，那么首先要满足的条件就是 $i<l$ 且 $p_i<d$，转移过来后正方形的长度当 $d-p_i\le l-i$ 也就是 $d-l\le p_i-i$ 的时候是 $r-i$，否则是 $u-p_i$。注意到，如果满足 $i<l$ 那么当 $d-p_i> l-i$ 时就天然满足了 $p_i<d$，同理如果满足 $p_i<d$ 那么当 $d-p_i\le l-i$ 的时候也天然满足了 $i<l$，因此转移的贡献也是可以确定住的，跑两遍二维偏序即可。对于 $dir$ 为其它数的情况可以类似的讨论处理，这样对每层 $j$ 转移是跑八遍二维偏序，比较唐，但是我也不会其它更好的做法。

代码是贺的，不放了。