学习笔记：操作分块 / 根号重构

感谢校内模拟赛给我强行灌输了这个东西。。。
概述

操作分块 / 根号重构，又名时间轴分块，可以解决需要多次修改和查询的问题，常常难以直接维护。
借鉴序列分块的思想，我们设定一个阈值 \(B\)，将连续 \(B\) 次操作视为一块。考虑一次查询操作，将对它产生影响的修改分为两类：

• 所在块之前的整块的修改；
  
• 所在块中它之前的修改，仅有 \(\mathcal O(B)\) 次。
  

类似序列分块，整体维护一类修改的贡献，并暴力贡献二类修改。具体的，一个块的操作结束后，考虑暴力重构，将这一块算进整体贡献中，仅会重构 \(\mathcal O(\frac{q}{B})\) 次。
我们用几道例题来理解上述思想。
CF342E Xenia and Tree

题意： 给定一棵 \(n\) 个节点的树，初始时 \(1\) 号节点为红色，其余为蓝色。
\(q\) 次询问，两种操作：

• 将一个节点变为红色；
  
• 询问节点 \(u\) 到最近红色节点的距离。
  

\(1\le n, q \le 10^5\)，5s

以阈值 \(B\) 操作分块，考虑一次查询 \(u\)：
对于一个二类修改 \(v\)，暴力贡献 \(dis(u, v)\)，复杂度 \(\mathcal O(B)\)。
对于整块的一类修改，我们需要在每个整块后进行重构。考虑以当前所有红点为起点集合进行多源 bfs，即可 \(\mathcal O(n)\) 求出每个节点 \(x\) 到最近红的的距离 \(f(x)\)，\(\mathcal O(1)\) 贡献。
两部分贡献取 \(\min\) 即为答案。总复杂度 \(O(qB + q + n\cdot\frac{q}{B})\)，视 \(n, q\) 同阶，取 \(B = n ^ {0.5}\)，有最优复杂度 \(\mathcal O(n ^ {1.5})\)，实际上取 \(B = 400\) 跑的并不快，开到 \(1000\) 就很好了。submission.
接下来看一道 DS。
[模拟赛] 浮夸(grandiloquence)

题意： 给定一棵初始 \(n\) 个节点的树，根节点为 \(1\)。再给定颜色数 \(k\)，颜色的编号为 \([0, k)\)，最开始所有点都没有被染色。
接下来进行以下三种操作共 \(m\) 次

• 1 u c 对于 \(u\) 子树内的节点 \(v\)，将 \(v\) 染色为 \((c + dis(u, v)) \bmod k\)；
  
• 2 u c 询问 \(u\) 子树内颜色为 \(c\) 的节点个数；
  
• 3 u \(~~~\)插入一个编号为 \(\lvert V\rvert + 1\) 的节点，其父亲为 \(u\)，没有被染色。其中 \(V\) 是当前点集。
  

\(1\le n, m \le 2\times10^5\)，\(0\le c \lt k \le 10\)，强制在线。

假设没有操作 \(3\)，直接用 dfs 序拍平，转换成区间操作。颜色数很少，直接暴力维护。观察 \(1\) 操作，颜色可以拆成 \((c - dep_u + dep_v)\)，考虑区间打 \((c - dep_u)\) 的标记，按 dep 和 col 统计即可。线段树随便维护。
有操作 \(3\) 的话，考虑操作分块，每次操作 \(3\) 满 \(B\) 个，就新开一块，对于 \(1,2\) 操作，分两类：

• \(u\) 不是块内新增节点（即二类修改）：算完前面的整块节点后，枚举所有块二类修改，若其在 \(u\) 子树内，则暴力计算贡献，\(\mathcal O(B)\)，这是平凡的；
  
• \(u\) 是块内新增节点：那么 \(u\) 子树内均为新增节点，于是 \(siz_u \lt B\)，直接暴力 dfs 算答案，\(\mathcal O(B)\)。
  

满 \(B\) 个后无重建线段树。话说为啥大家都写的分块啊。
再来一道？
[模拟赛] 序列查询(query)

题意： 给定一长为 \(n\) 的非负整数序列 \(a\)，你需要支持以下两种操作共 \(q\) 次：

• 区间翻转；
  
• 区间询问 \(\text{mex}\)。
  

\(1 \le n, q \le 2 \times 10 ^ 5\)，4s

以阈值 \(B\) 操作分块，单独考察每一块操作。
先对序列按受操作情况划分颜色段，每个颜色段受到的操作相同。操作均为区间操作，最多使其头、尾所在颜色段分裂，增加 \(\mathcal O(1)\) 个颜色段，于是颜色段仅有 \(\mathcal O(B)\) 个。ODT 维护，翻转可以考虑暴力在 ODT 上翻转并打上翻转标记，单次翻转复杂度 \(\mathcal O(B)\)。
询问 \(\text{mex}\) 很不好维护，考虑离线下来枚举答案。具体的，维护出每个颜色段受到的询问的集合，离线下来遍历 ODT，算出包含值 \(x\) 的询问的集合 \(S_x\)，压位存储。再枚举 \(\text{mex}\)，枚举到 \(i\) 时，还没确定答案且属于 \(S_i\) 的询问的答案即为 \(i\)。
重构直接遍历 ODT 进行重构即可。实现上，为了让 ODT 支持翻转，直接用 std::vector 存储，定位时暴力往后找，复杂度即为颜色段个数 \(\mathcal O(B)\)；对于插入，我们选择相信 insert 的超小常数（雾
复杂度分析非常困难，在以下条件下：

• 压位写法，视位运算复杂度为 \(O(1)\)，
  
• 视 \(n, q\) 同阶
  
• 视 insert 复杂度 \(\mathcal O(1)\)
  

，复杂度为 \(O(\frac{n ^ 2}{B})\)，若使用 __uint128_t 进行压位，令 \(B = w = 128\)，复杂度 \(O(\frac{n ^ 2}{w})\)。
P5443 [APIO2019] 桥梁

题意： 给定一张 \(n\) 点 \(m\) 边的无向图，第 \(i\) 条边带权 \(w_i\)，有 \(q\) 次如下两种操作：

• \(w_x \gets y\)
  
• 查询从 \(x\) 开始，只通过 \(\ge y\) 的边，可达点数量。
  

\(1 \le n \le 5\times10^4\)，\(0 \le m \le 10^5\)，\(1 \le q \le 10^5\)，\(w_i, y \le 10^9\).

若没有修改操作，可以使用 Kruskal 重构树，也可以离线，将询问按 \(y\) 从大到小排序，并查集维护即可。
有修改，不妨考虑操作分块，将 \(B\) 次操作划为一块。Kruskal 重构树的形态受修改操作影响，难以动态维护，于是我们考虑并查集，随之而来的问题是：我们怎么同时处理时间轴和边权序？
对于前面的块的修改，对每一条边维护出其最后一次修改，首先肯定是以边权序对询问排序，那么对块内无修改的边，它最后一次修改在当前块前，直接随边权序加入并查集即可。
再考虑块内有修改（二类修改）的边：仅有 \(B\) 条，考虑可撤销并查集，对于询问 \((t, x, y)\)，加入满足以下条件的边 \((t_0, x_0, y_0)\)：

• \(y_0 \ge y\)；
  
• 是满足 \(t_0 \lt t\) 之前对 \(x_0\) 的最后一次修改。
  

，算出答案后再撤销即可，这部分单次询问是 \(\mathcal O(B)\) 的。
由于要支持撤销，并查集不能路径压缩，使用启发式合并，总复杂度 \(\mathcal O((m\log m + B\log B)\cdot\frac{q}{B} + qB\log n)\)，视 \(n, m, q\) 同阶，取 \(B = q^{0.5}\) 时，有最优复杂度 \(\mathcal O(q\log q\sqrt{q})\)，实测块长取 \(900\) 为最优，给出实现：
[code]const int N = 1e5 + 5, B = 900;int n, m, q, rk[N], vis[N], ans[N];struct Edge{ int u, v, w, id; } E[N];struct Query{ int t, x, y; };vector M, Q, V;namespace DSU {    int fa[N], siz[N], stk[N], tp, cur;    void init(){ for(int i = 1; i  siz[v]) swap(u, v);            fa = v, siz[v] += siz, stk[++tp] = u;        }    }    void rec(){ cur = tp; }    void undo(){        while(tp > cur){            int u = stk[tp];            siz[fa] -= siz, fa = u, tp--;        }    }} using namespace DSU;void solve(){    sort(E + 1, E + m + 1, [](Edge x, Edge y){ return x.w > y.w; });    for(int i = 1; i  y.y; });    for(int i = 1; i  t) break;            vis[rk[_x]] = _t;        }        for(auto [_t, _x, _y] : V){            if(_t > t) break;            if(_t < vis[rk[_x]]) continue; // 不是最新修改            if(_y >= y) merge(E[rk[_x]].u, E[rk[_x]].v);        }        ans[t] = siz[find(x)], undo();    }    for(auto [t, x, y] : V) E[rk[x]].w = y;}int main() {    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);    for(int i = (cin >> n >> m, 1); i > E.u >> E.v >> E.w, E.id = i;    for(int i = (cin >> q, 1), op, x, y; i > op >> x >> y, op == 1 ? M.eb((Query){i, x, y}) : Q.eb((Query){i, x, y});        if(M.size() + Q.size() >= B) solve(), M.resize(0), Q.resize(0);    } if(Q.size()) solve();    for(int i = 1; i

这个有用。