日记

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

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

T1 # Link to T1

大模拟。

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

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

T2 # Link to 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 # Link to T3 & T4

不睡觉也做不出来。

后日谈 # Link to 后日谈

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

以后不准睡了哦！