唉唉是谁赛时唐到用分块写硬条1h40min没调出来最后发现忘处理小块破防了 蒟蒻码字不易,路过的留个赞呗 本文并没有同步发布于我的博客,因为懒 提供一种分块做法: 分析题目易知,我们只需要维护每个水池所在连通块的左右端点即可,平均值可用前缀和求. 先考虑如何维护 假设我们已经知道本次修改的左右端点,设 为点 的值, 表示点 左侧有挡板,同时以 为块长分块,对于散块暴力处理,对于整块直接打上标记.这样操作的时间复杂度是的 性质:如果一个整块被打上了标记,那么它内部的散块一定不会再被更新. 很容易证明:被打上标记的整块内部点的 左端点一定在块的左侧,右端点一定在块的右侧 这个性质我们查...