P14761 [Opoi 2025] CCD 的序列

以下关于括号序列和括号匹配的定义跟其他题没什么区别，知道的可以跳过。 --- 括号序列是一个只包含 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。 定义一个括号序列是合法的，当且仅当它为下列三种之一： 1. 空串是合法的。 1. 如果字符串 $S$ 是合法的，则 $(S)$ 也是合法的。 1. 如果字符串 $S$ 和 $T$ 是合法的，则 $ST$ 也是合法的。 一个合法括号序列中，一个括号是另一个括号所匹配的括号，当且仅当两个括号之间是一个合法的括号序列，且两个括号方向相反。可以证明，一个括号所匹配的括号是唯一的。 --- 定义一个括号的匹配发生变更当且仅当它所匹配的括号变更。 你有一个括号序列 $S$。初始 $S$ 为空，**下标从 $1$ 开始**。 你要进行 $n$ 次操作，**操作之间不独立**。 每次操作给你两个数 $l,r(0\le l\le r\le |S|)$，表示**同时**往 $S$ 的 $l\sim l+1$ 之间插入左括号、往 $S$ 的 $r\sim r+1$ 之间插入右括号（$l$ 或 $r$ 为 $0$ 表示在开头插入，为 $|S|$ 表示在末尾插入，**$l=r$ 时左括号插在右括号前面**）。 可以证明，每次操作完后这个括号序列都是合法的。每次操作完后你需要求这次操作导致匹配发生变更的括号数（不包括新增加的两个括号）。

第一行一个数，表示 $n$。 接下来 $n$ 行，每行两个数 $l_i,r_i$，表示一次操作。

$n$ 行，每行一个整数。第 $i$ 行表示第 $i$ 次操作导致匹配变更的括号数。

### 样例解释 以下标红的表示新增的括号，蓝色表示当次操作导致匹配发生变更的括号。 - 第一次操作后括号序列变为 $\texttt{\red{()}}$。 - 第二次操作后括号序列变为 $\texttt{\red{()}()}$。 - 第三次操作后括号序列变为 $\texttt{\red(()\red)()}$。 - 第四次操作后括号序列变为 $\texttt{\blue{((\red())(\red))}}$。 - 第五次操作后括号序列变为 $\texttt{(\red(\blue(\red)()\blue)())}$。 ### 数据范围与约定 **本题采用捆绑测试。** $$ \def\arraystretch{1.2} \begin{array}{|c|c|c|} \hline \begin{array}{c} \tt{subtask}\\\hline 1\\\hline 2\\\hline 3\\\hline \end{array} & \begin{array}{c} n\\\hline \le 10\\\hline \le 10^{3}\\\hline \le 2\times10^{5}\\ \end{array} & \begin{array}{c} \tt{pts}\\\hline 20\\\hline 30\\\hline 50\\\hline \end{array} \\\hline \end{array} $$ 对于所有数据，$0\le n \le 2\times10^{5}$，$\forall i \in [1,n],0\le l_i,r_i\le 2\times i-2$。