2718 括号序列

#绿，#差分，#括号序列，#DP

暴力，差分

首先可以写出一个暴力。
$O(n^2)$ 枚举每一个区间，通过栈判断其是否合法。如果合法就对区间内的所有 $ans_i$ 都做出 1 的贡献。
由于区间修改，最后查询一次，因此可以差分解决。
期望得分 30 pts。

还是差分

对于一个合法的括号序列 $[l, r]$，差分数组中 $d_{l} \gets d_l + 1, d_{r+1} \gets d_{r+1} - 1$。

每一次只加减 1，效率显然太慢。

效率太慢？
刚才的差分是工具，现在我们将它当作求解目标。
我们可以直接求出每一个差分值，期望使用线性实现。

回顾差分值的定义 $d_i = a_i - a_{i-1} = st_i - ed_{i-1}$。
$st_i$ 代表以 i 开头的所有贡献。
$ed_{i-1}$ 代表以 i - 1 结尾的所有贡献，不作用于 $i$，需要减去。

将其带入题目语境。
$st_i$ 是包含 $i$ 但不包含 $i-1$ 的括号序列数量，也就是以 $i$ 开头的括号序列数量。
$ed_{i-1}$ 是包含 $i - 1$ 但不包含 $i$ 的括号序列数量，也就是以 $i - 1$ 结尾的括号序列数量。

现在的问题：求解 $\{st_i \}$ 和 $\{ ed_i \}$。
使用 dp 解决。

先说求解 $\{ st_i \}$。

• 括号序列以 $i$ 开头，前提是 $s_{i} = \texttt{(}$。否则 $st_i = 0$。
• 从右向左，动态跟进，维护右括号的栈序列。如果 $i$ 没有匹配的右括号，那么 $st_i = 0$。
• 假设匹配的右括号是 $j$，则 $st_{i} = st_{j + 1} + 1$。序列$[i, j]$ 就是 $+1$。

求解 $\{ ed_i \}$ 也是一样。

• 括号序列以 $i$ 结尾，前提是 $s_{i} = \texttt{)}$。否则 $ed_i = 0$。
• 从左向右，动态跟进，维护左括号的栈序列。如果 $i$ 没有匹配的左括号，那么 $ed_i = 0$。
• 假设匹配的左括号是 $j$，则 $ed_{i} = ed_{j - 1} + 1$。序列$[j, i]$ 就是 $+1$。

时间复杂度是线性的。

算法流程

• 求解 $\{ st_i \}, \{ ed_i \}$。
• 求解差分数组 $d_i = st_i - ed{i-1}$。同时复原 $ans_i$，增加答案。

实现细节

• 题目中提到乘法取模，加法不取模，需要使用 64 位整数。