题解：P7711 [Ynoi2077] 3dmq

ylzqwq · 2025-01-20 14:15:59 · 题解

三维偏序，未必需要二维分块。

直接上对应的数据结构，就是处理高维信息的 k-dtree 解决即可，如果被卡常了，可以操作分块降一维，另外两维用数据结构 kdt 维护即可。

所以时间复杂度为 O(n \sqrt n)，可过，多卡卡常。

重点讲解卡常技巧：

1. 快读快写，这个其实不用说。

2. 操作分块，将操作序列分块，可去除一维限制，将其变成二维偏序，时间复杂度变为了 O(n \sqrt n)。

3. 可以使用指令集优化，但实测没有必要，还有可能负优化。

代码想要可以私信。