胸和钥匙 无敌做法

PosVII · 2025-01-05 18:44:34 · 题解

前言

upd: bitset 做法假了，改成根号分治了。

[AHOI2022] 钥匙

有朋友说看不懂，那我修改下文风。这个新文风我是煮了又煮，希望大家喜欢喵喵！！

AHOI 的大师出的题，果然是相当的规范！我很喜欢哈！好题难得！大家一定要珍惜咩！

嘴巴一个不需要对钥匙数量限制的做法咩。需要使用到根号分治咩。

做法

为了表达方便，我们设每种钥匙数量的最大值为 c 咩。

考虑到此类信息的合并是困难的，抛弃常规的 O(\log n) 或 O(\sqrt{n}) 次合并的做法。使用点分治或启发式合并将最终的路径划成两半咩。

每次询问 (x,y) 变成了 (x,rt) 与 (rt,y) 的过程，考虑这种括号合并的问题在序列上分治的时候是怎么处理的咩：

记录 (x,rt) 的答案及剩下的钥匙数量，记录 (rt,y) 的答案及剩下的胸数量，对于每种颜色，取剩下的钥匙和胸的较小值计入答案即可咩。

那么如此，考虑如何维护两者的较小值。一种比较显然的方法是，直接对于每种颜色算贡献。

但是这样的话复杂度仍然是 O(n^2 \log n) 的咩！

考虑优化，可以使用经典的根号分治套路，设阈值为 B 咩：