题解：P8425 [JOI Open 2022] 长颈鹿（Giraffes）

· · 题解

考虑一个重排后的排列应该长什么样子，不妨固定住一对 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 转移是跑八遍二维偏序，比较唐，但是我也不会其它更好的做法。

代码是贺的，不放了。