【题解】P8078 [WC2022] 秃子酋长

LinkyChristian · 2022-03-19 11:56:37 · 题解

泪洒考场的一道题...

首先是莫队的 O(n \sqrt n logn) 做法。具体实现就是在做普通莫队的过程中用一个set来实时维护排序后的序列。在插入一个数时加上它与其前驱和后继的贡献，在删除一个数时去掉它的贡献并把原前驱后缀的贡献补上。通过此法可以拿到 50pt （我考场上以为能拿60）。

然后我在考场上也想过优化，我想到了只加版本的回滚莫队，但是觉得只加的复杂度与普通莫队差不多，就把回滚莫队pass了。结果考后听同学说可以用只删回滚莫队，就可以把 log 去掉。

考虑一下只加回滚莫队和普通莫队的复杂度瓶颈。没错，就是查找前驱后继。在一般的情况下，查找前驱后继的复杂度是一个不可省略的 log 。但是我们可以预先把前驱后继维护好。具体而言，我们将只加回滚莫队的 l 指针从当前块右端点向左扫到当前询问左端点，改为从当前块左端点向右扫到当前询问左端点。在将指针复位到当前块左端点时直接将整个块的元素加入链表，并在扫到当前询问左端点的过程中将元素从链表中一一删除。对于右端点同理，排序询问时我们将左端点在同一个块内的询问按右端点降序排序，将当前块右端点到 n 的元素加入链表，之后 r 指针从 n 往当前询问右端点扫，并执行删除操作。由于我们一开始就将所有元素加入了链表，因此在删除一个元素时查询元素的前驱后继的复杂度是 O(1) 的。总复杂度 O(n \sqrt n)，可以通过本题。

总结一下流程：

• 将 1 \sim n 的元素加入链表

• 处理当前块的询问

对一个块内的所有询问而言

• 将 l 指针恢复到当前块左端点，并消除上一个询问 l 指针造成的贡献。

• 将当前块的贡献消除，处理下一个块的贡献。

本题到此完全解决其实这个做法不是lxl的正解代码咕咕了。