Luogu6578 [Ynoi2019] 魔法少女网站

发表于 2025-03-13 分类于算法竞赛，题，洛谷阅读次数：

第十分块。

题意：给出一个序列，支持：

允许离线，，时限，空限。

离线

若考虑分块，由于是 pair 贡献，难以够对每个整块分别计算，那么就无法使用离线逐块处理的办法降空间。

离线而空间小的做法，不妨思考一下莫队。

我们有四个维度：操作时间，，，以及。

本题的数据范围较大，根据经验，最简单的带修莫队也极限只能在内处理。本题更为复杂，常数进一步增大，跑估计没戏。

想要做到的复杂度，我们只能使用莫队维护两个维度，剩下的就交给其他数据结构。

时间这一维处理起来最困难，是必然要维护的（否则也就可能可以在线了？）。而左右端点维护难度应是相同的，要么都维护，要么都不维护。

这样看来，我们最好尝试在莫队中维护（时间，）两维，而将交给支持区间查询的数据结构。

维护一个序列，表示某个位置是否，答案就是区间内极长区间的的和。

考虑如何实现一个修改查询的数据结构。

我们发现较为容易，相当困难，于是不考虑后者。

使用分块，对每块记录块内权值和，极长前/后缀长度。

查询时，对边界散块暴力算出上述信息，然后将各个块合并，复杂度为。

修改时，对每个块分别维护。对于每个段,在其两端维护段的另一端（类似双向链表），这样就能支持将段合并。

然后还需特判是否扩展了前/后缀。

由于我们不支持，需要使用回滚莫队。

让时间维乱跳，维块内单调。当指针增加时，只会在序列中把一些位置。

将可能被回滚影响到的个位置打上标记，在指针移动时不处理，回滚时才处理。

时间维回滚时会撤回操作，用栈记录撤回信息即可。

综上，时间复杂度为，空间复杂度为。

考虑分块。

询问时将的位置记为，其余记为。

散块暴力。对于整块只需要得到左侧连续，右侧连续，块中答案。

注意到对于每个块只产生个本质不同的序列，且的分界点正是块中元素。

利用插入排序，重构一个块容易做到。

查询时需要二分。用分散层叠可以优化到。