Link\mathcal{Link}

思路

如果只能交换相邻的两项,那么答案就是逆序对数量。于是就可以有最裸的暴力枚举第一次可以交换不相邻的两个位置。时间复杂度 O(n3logn)\mathcal{O(n^3 \log n)}。这样子很慢,有一个显然的事情就是我们交换的两项一定满足:i>j,hi<hji > j, h_i < h_j。如果不构成逆序对肯定不优秀。

设交换之前的逆序对数量为 AA。则交换 hi,hj(hi>hj,i<j)h_i, h_j(h_i > h_j, i < j) 后逆序对数量变成:A=A1k=i+1j1([hk>hj]+[hk<hi][hk<hj][hk>hi])=A12k=i+1j1[hj<hk<hi]A' = A -1 - \sum_{k=i+1}^{j-1}([h_k > h_j] + [h_k < h_i] - [h_k < h_j] - [h_k > h_i]) = A - 1 - 2\sum_{k=i+1}^{j-1}{[h_j < h_k < h_i]}。答案就是 A+1A'+1

(i,hi)(i,h_i) 看成二维平面上的一个点,答案就可以通过数左上角为 (i,hi)(i,h_i),右下角为 (j,hj)(j,h_j) 的矩阵中点的数量,时间复杂度 O(n2)\mathcal{O}(n^2)

可以发现,我们选择的 i,ji,j 必然满足 (i,hi)(i,h_i) 左上方没有东西,(j,hj)(j,h_j) 右下方没有东西,这样肯定不劣。这样已经可以分治 + 主席树平凡在 O(nlog2n)\mathcal{O}(n \log^2 n) 时间内求解了。但是非常不好写而且常数大

考虑每一个点 (x,hx)(x,h_x) 被哪些矩阵覆盖。设 ll 表示最小的 ii 满足 hi>hxh_i > h_xrr 表示最大的 jj 满足 hj<hxh_j < h_x。那么有 i[l,x1],j[x+1,r]i \in [l, x - 1], j \in [x + 1, r] 表示的以 (i,hi)(i, h_i) 作为左上角,以 (j,hj)(j, h_j) 作为右下角的矩形都是可行解。那么我们将这个矩形重新看做平面上的点 (i, j)。所有可以覆盖 xx 的矩阵就在平面上形成了一个矩形,以 (l,x+1)(l, x + 1) 为左下角,以 (x1,r)(x - 1, r) 为右上角。

这样问题就转化为求一个被最多矩阵覆盖的点的覆盖次数的最大值。扫描线维护即可。

复杂度是优美的 O(nlogn)\mathcal{O}(n \log n)

代码

https://loj.ac/s/1863642