题解：P12083 [Ynoi1998] Marchen

liangbowen · 2025-12-19 16:47:02 · 题解

最近天天被教练阴阳，有点破防，做点魔怔题增长自信。

显然不弱于 P5046，且强制在线，考虑分块。根据 P5046 的经验，大概是要设计一个严格根号的算法才能过题了。

首先回忆 P5046 的做法：分讨 i,j 的位置，可以完成 "散对整" "整对散" "散对散" "整对整" 的计数。

①⑩：i,j,k 均在左散块（绿绿绿）

枚举 j，预处理 a_i<a_j 与 a_j<a_k 的对数，乘起来即可。

UPD：这样常数太大了，在 l,r 同块时还是只能上面这样做，否则形如前缀后缀，可以直接预处理。

②⑨：i,j 在左散块，k 在整块（绿绿红）

枚举 j，算出 a_i<a_j 与 a_j<a_k 的对数乘起来即可，分别是 P5046 的 "散对散" 与 "散对整"。

③⑥：i,j 在左散块，k 在右散块（绿绿蓝）

枚举 j，算出 a_i<a_j 与 a_j<a_k 的对数乘起来即可，都是 P5046 的 "散对散"。

⑤：i 在左散块，j 在整块，k 在右散块（绿红蓝）：

我们没法枚举 j 了，但是还是能枚举 k，因此考虑用图腾的技巧容斥：\text{123}=\text{1??}-\text{132}。前者即要求 a_i<a_j\wedge a_i<a_k，后者即 a_i<a_k<a_j，都可以同上面转 P5046 算。

④⑧：i 在左散块，j,k 在整块（绿红红）

枚举 i，记 v=a_i，那么相当于 p+1\sim q-1 求解 v<a_i<a_j 的 (i,j) 对数量。

考虑预处理 F_{p,q,v} 表示 p\sim q 中 v<a_i<a_j 的 (i,j) 对数量。对于同一个 p，有用的 v 取值只有 O(\sqrt n) 个，因此先枚举 p，将数组离散化为 O(\sqrt n) 值域。从左到右枚举 q，F_{p,q,v} 从 F_{p,q-1,v} 累加，还要额外算上 j\in q 的 (i,j) 贡献。

这样总的复杂度保持为 O(\sqrt n)。

UPD：为了卡常，可以对 F 搞个前缀和状物方便 O(1) 做查询。

⑦：i,j,k 均在整块（红红红）

同 P5046 处理即可：ans_{p,q} 表示块 p\sim q 的答案，用 ans_{p,q-1}+ans_{p+1,q}-ans_{p+1,q-1} 容斥，还要额外算上 i\in p 且 k\in q 的数对 (i,j,k) 贡献，可以类似 ③⑤⑥ 直接完成。

UPD：这样常数太大了，可以改成 ans_{p,q-1} 再加上 ⑧⑨⑩ 直接完成。

结束。上述所有操作都不带 log，时空复杂度均为 O(n\sqrt n)。

然而这个题代码难度远高于思维难度吧？？

首先是卡空间。各种 P5046 的部分应当只用两个 int 的 O(n\sqrt n) 数组。④⑧ 处需要定义两个 long long 的 O(n\sqrt n) 数组，但是都只需要用一半，可以拼一起。这样可以刚好卡进 512MB。

卡时间的话：

• 确保每一部分的做法都比较优，如果某一部分跑得慢就换一个常数小的做法；尽可能将查询里面的复杂度改成 O(1) 的，因为预处理的内存访问比查询的访问快很多。
• cache 问题*太严重了，保证所有 O(n\sqrt n) 数组中固定一维在前面，然后用指针来加速访问，比如 `int FF = F[l]并将所有F[l][i]改成FF[i]`，实测优化巨大。
• 找个快读快写！！这个题输入输出量还是不算小的。
• 我的代码好像有逆天波动，同一份代码交两次差 200ms+，无语。感觉差不多了可以疯狂乱交、换语言交、洗把脸再交。

最后你谷评测机实在有点慢呵，我 QOJ 跑 1.4s 你谷 TLE /fn。不过也无所谓了，最后拼尽全力还是卡过去了，感谢开大实现。