Luogu5692 [MtOI2019]手牵手走向明天

第四分块·改。

题意：维护长度为 的序列 。

每次操作给定 ，执行下列两项之一 ：

• 将 区间内的 都改为 。

• 找出 满足 且 ，使得 最小。求这个最小值。

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

---

分块。

不考虑修改

维护 表示第 个块内 之间的最小距离。

因为 均为 ，故总状态量为 。

查询时，查看每个块内的答案。块间答案只可能和块中最靠前和最靠后的 有关。

这样，在每个整块中取出 个，再取出整个散块。

按顺序得到一系列 的出现位置之后，显然可以线性扫描求得答案。

考虑修改

考虑 的修改。

对于散块，暴力重新计算所有关于 的 ，可以在线性内完成。

对于整块，还是类似最初分块的套路，分类讨论 ：

• 不存在：忽略。

• 不存在：将 映射为 。

• 都存在：类似暴力线性计算。

这需要为每个块维护一个映射表。

第三种情况触发的总次数是 的，因此也可以类似散块进行暴力重构。

复杂度 ，若离线后逐块处理可以做到空间 。

好像比原版还好写……最优解了。