操作分块

操作分块是一种简单分块科技，主要适用于有修改查询两种操作的题目，可在线可离线。

如何判断自己需要操作分块？

找到两个（合适的）暴力做法，复杂度分别依赖于询问和修改的次数（或者说，一种在查询少的时候快，另一种在修改少的时候快），然后就可以通过对操作分块来平衡复杂度。

例题：CF342E

简要题意

给一棵树，初始一号点是红色，其余无色，要求支持以下操作：

• 将 节点变成红色；
• 询问离 最近的红色点到 的距离。

。

做法 1

对于每一次询问，我们可以求其与每一个红色点的距离，用树剖求 LCA，或者 ST 表做到 预处理 查询，复杂度是 或者 的。

这个做法单次修改 查询 。

做法 2

对于每一次修改，我们用 BFS 求出当前点到其它点的距离，每个点取最小值存进数组中，然后就可以 查询答案。

这个做法单次修改 查询 。

做法 3

有没有办法可以平衡复杂度呢？

我们注意到，其实做法 2 中 BFS 可以同时对于多个红色点求出答案，我们考虑定期对当前所有的红色点做一次 BFS，求出这些红色点的答案，然后对于没有 BFS 的新加入的红色点，在每一次询问的时候现场使用做法 1 的方法出答案。

于是我们考虑设定一个阈值 ，每 个操作分一个块。在块的开始，对于已经加入的所有红色点进行一次 BFS，求出每一个点到它最近的红色点的距离。每一次 BFS 的时间复杂度是 的，由于只有 个块，这部分的总复杂度是 的。

对于每一个询问，由于当前块以前的红色点的答案已经计算，我们只需要考虑块内红色点造成的贡献，块内只有不超过 个询问与修改，因此复杂度是 的。

综合一下，总复杂度是 的，在 时取最小值 ，可以通过。

总结

这道题中，对操作分块平衡复杂度的原理是缩减每一种暴力的次数，使复杂度可以接受。

例题：P5443

构思细节题。

简要题意

给定一个无向图，边有边权，要求支持一下操作：

• 将某个边的边权修改为 。
• 询问从某点开始，仅通过边权 的边最多可以到达的点数。

。

做法 1

考虑暴力，修改就暴力修改，对于每一个询问，在并查集中加入所有 的边，忽略路压并查集的复杂度，时间复杂度 ，瓶颈在询问。

做法 2

考虑如果没有修改操作，我们可以通过离线所有询问，然后按照 从大到小排序，每次在并查集中加入边权 的边，然后求连通块数量，由于每条边只会加入一次，复杂度 。

但是现在有修改操作，因此这种做法就必须考虑修改边权。我们还是将询问按照 从大到小离线下来，考虑维护这个修改的边。如果一个边没有修改，我们还是按照边权从大到小排序，依次加入这个 的边到并查集中。对于所有修改的边，我们看它当前询问时的权值，如果 就加入并查集，否则不管。处理完每一个询问的时候，再撤销掉临时加入的边。这个做法的复杂度是 ，瓶颈在修改上面。

做法 3

还是考虑对操作分块，每 个操作分一块。注意到每一块内修改边权个数不超过 个，询问次数同理，因此考虑对于不在该块内修改的边，直接固定边权。和做法 2 一样，还是考虑离线询问按 从大到小，但是我们只用离线当前块内的询问，对于每一个询问，看看在该块内修改的边，在这个询问时权值分别是多少，然后加入 的边，询问连通块个数，然后撤销临时加入的边。

每一个块的时间复杂度是 ，总共 个询问，总复杂度是 ，在 的时候取到最小值 。

总结

这道题吧说实话做法 1 对整道题的启发不是很大，但是你依然可以将其看作我们找到的一个暴力，用以推出操作分块的正解。