日记

日记

Wed May 07 2025
3 分钟

你怎么敢在草神面前睡觉的???!!!

还好还骗了 105105 分,不然今天就挂了。

T1 Link to T1

大模拟。

5555 分做法:
暴力枚举,时间复杂度 O(n2m2k)O(n^2 m^2 k)

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

T2 Link to T2

感性理解:交换的 i,ji,j 一定是 i<ji < jai>aja_i > a_j 的。我们设在 (i,j)(i,j) 区间内,大于 aia_i 的数有 maima_i 个,小于 aia_i 的数有 miimi_i 个,maj,mijma_j,mi_j 同理。那么交换 i,ji,j 会使逆序对数量减少 miimai+majmij+1mi_i - ma_i + ma_j - mi_j + 1。移一下项变成 miimij+majmai+1mi_i - mi_j + ma_j - ma_i + 1。我们发现这玩意就是区间 k(i,j)k \in (i,j)ak(aj,ai)a_k \in (a_j,a_i) 的个数乘 22

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

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

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

T3 & T4 Link to T3 & T4

不睡觉也做不出来。

后日谈 Link to 后日谈

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

以后不准睡了哦!