日记 - 伊埃斯的博客站

你怎么敢在草神面前睡觉的？？？！！！

还好还骗了 $105$ 分，不然今天就挂了。

T1

大模拟。

$55$ 分做法：
暴力枚举，时间复杂度 $O(n^2 m^2 k)$ 。

$100$ 分做法：
发现只有有重叠的情况才需要特殊考虑。而这种情况又只有 $k^2$ 个，我们枚举这 $k^2$ 种特殊情况就行，复杂度 $O(nmk^2)$ 。

T2

感性理解：交换的 $i,j$ 一定是 $i < j$ 且 $a_i > a_j$ 的。我们设在 $(i,j)$ 区间内，大于 $a_i$ 的数有 $ma_i$ 个，小于 $a_i$ 的数有 $mi_i$ 个， $ma_j,mi_j$ 同理。那么交换 $i,j$ 会使逆序对数量减少 $mi_i - ma_i + ma_j - mi_j + 1$ 。移一下项变成 $mi_i - mi_j + ma_j - ma_i + 1$ 。我们发现这玩意就是区间 $k \in (i,j)$ 且 $a_k \in (a_j,a_i)$ 的个数乘 $2$ 。

我们把每个点塞到平面直角坐标系上面。第 $i$ 个额点的坐标是 $(i,a_i)$ 。那么上面的柿子就相当于：取一个左上角的点和一个右下角的点，它们框出来的矩形的里的点的数量（不包括边界）。使用扫描线维护。

如何使用扫描线维护？我们首先发现一个性质：如果有 $i < j$ 且 $a_i > a_j$ ，那么显然 $i$ 比 $j$ 优， $j$ 就不会成为“左上角的点”。言外之意：只有 $a_i = \max_{j = 1}^{i}a_j$ ， $i$ 才可能成为最优解里的“左上角的点”。同理可得，只有当 $a_i = \min_{j = i}^{n} a_j$ 时才可能成为“右下角”的点。我们把这些点分类：不能成为边界点的叫贡献点。考虑从左往右扫描：

遇到一个贡献点
我们维护一个 $r$ 表示当前的这个点能对值在 $[a_i,r]$ 区间内的“左上角的点” ，于是我们直接权值线段树区间加 $1$ 。
遇到一个“左上角的点”
更新 $r = a_i$ 即可。
遇到“右下角的点”。
我们对于每个贡献点都记录一个 $d_i$ 表示它对 $[i,d_i]$ 区间内的作了贡献。由于我们维护的“右下角的点”也该是单增的，这个点下面的贡献点都不会有贡献，所以我们就把 $i \in [l + 1,a_i]$ 的每个 $[i,d_i]$ 区间减 $1$ （此时 $l$ 还没有更新），然后更新 $l$ ，并统计答案。当前的答案就是全局最大值。

T3 & T4

不睡觉也做不出来。

后日谈

睡觉的原因是昨天晚上睡不着，导致早上困死。

以后不准睡了哦！

Thanks for reading!

日记

周三 5月 07 2025

660 字 · 3 分钟

life 日记