LOJ535 「LibreOJ Round #6」花火

$\mathcal{Link}$

思路

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

设交换之前的逆序对数量为 $A$。则交换 $h_i, h_j(h_i > h_j, i < j)$ 后逆序对数量变成：$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'+1$。

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

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

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

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

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

代码

https://loj.ac/s/1863642