Luogu4118 [Ynoi2018] 末日时在做什么？有没有空？可以来拯救吗？

发表于 分类于 ， ， 阅读次数：

题意 ： 第六分块。

区间加（可加负数），区间最大子段和。

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

  • 前置知识：《Luogu5073 [Ynoi2015] 世上最幸福的女孩》

设块大小为 。套用 Luogu5073 离线之前的做法，在每个块建立线段树。

零散的查询是 的（其实也可以直接暴力），整体查询是 的，查询复杂度即为 。

修改时，整块上是全局加，散块则暴力重构线段树，复杂度是 。

取 可得最优复杂度为 ，无法通过。

发现对于零散块没必要完全重构，对于线段树，可以只重构那些在区间操作中被遍历到的节点，而其余节点可以用标记解决。

由于每层只有 个节点被访问，复杂度即为 。

将所有对内层数据结构的询问按照“标记值”排序（需要基数排序），然后可以将二分替换成线性扫描。

这样，就可以做到 的复杂度。逐块处理即可做到线性空间。