题意
给定一个长度为 \(n\) 的匹配的括号序列 \(s\)。给出 \(q\) 组询问，每组询问形如：光标从 \(s\) 的第 \(a\) 个字符出发，使用一下三种操作：
- 将光标移到左边的字符。
- 将光标移到右边的字符。
- 将光标移到匹配的括号。
求至少需要多少次操作才能移动到 \(s\) 的第 \(b\) 个字符。
\(n,q \le 4 \times 10^5\)。
题解
这题在考场上想出来了，但是只剩半小时写不出来，挺可惜的。
一种很显然的暴力就是建图跑最短路。观察最短路的形式，可以发现有以下特点。
括号形成森林结构，加个虚点就是树。最短路上光标每次深度最多变化 \(1\)。再加上一些感性的理解，不难发现经过的就是 \(a\) 和 \(b\) 对应括号间的路径上的所有括号，或者仅除去 \(\operatorname{lca}\)。这有些树形 \(\operatorname{dp}\) 的感觉。
树上每个点对应两种状态（因为括号有两边）。分别用 \(fl\) 与 \(fr\) 存。因为有包含关系的两对括号，端点间最短路十分显然，我们可以得到转移式：
\[fl_x=\min_{y \in son_x} fl_y+v_{yl→xl},fr_y+v_{yr→xl}\\ fr_x=\min_{y \in son_x} fl_y+v_{yl→xr},fr_y+v_{yr→xr} \]发现可以用 \(\operatorname{(min,+)}\) 矩阵优化。于是就做完了，复杂度 \(O(q \log n)\)。常数不算太大。
标签：fr,min,题解,ZR2448,括号,fl,光标 From： https://www.cnblogs.com/FishJokes/p/16912956.html