题解

Kano_zyc · 2024-01-31 16:46:40 · 题解

闲话

看到大家都用的线段树或者差分，就连唯一一篇分块也极其抽象。就让本蒟蒻来详细讲解一下（笑）。

分块の介绍

首先，什么是分块呢？我来引用一下 wiki 上的话：“通过对原数据的适当划分，并在划分后的每一个块上预处理部分信息，从而较一般的暴力算法取得更优的时间复杂度。”

那么具体如何划分呢？对于一个长度为 n 的序列，我们一般以 \sqrt{n} 的长度为一整块，和一些散块，最后暴力处理每个块即可。放张图辅助理解一下。

相信大家都已经发现分块的本质了吧，他就是一个度数为 \sqrt{n}，只有三层的树（记住这一点，后面学线段树时更好理解）。我再来放张图。

分块的基本代码

既然已经理解了分块，让我们来看一下代码实现。

首先，我们需要建立分块序列（为了防止某些人复制粘贴，这里放图片）。

然后，执行修改操作即可。这里讲个思路，只有两点要讲。

• 每次修改只有更新 \sqrt{n} 个 size 为 1 的节点以及几个 size 为 \sqrt{n} 的节点。

• 注意我们不用维护那个 size 为 n 的根节点的信息。

代码实现呢也非常简单，如果你看懂了上面的内容，相信你一定会写此题。我就不贴代码了。

再见！