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

HMF-have much fun Site

文章标签

✎首页

☰归档

★标签

☎关于

♚推荐

说说

友人帐

载入天数...

载入时分秒...

总访问量: | 访问人数:

阅

2022-03-25

3 min read

WC 题解算法

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

热度: loading...

泪洒考场的一道题...

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

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

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