P13065 [GCJ 2020 #2] Emacs++

在 2016 年的 **Distributed Code Jam** 中，我们为偏爱更高密度括号的 Lisp 爱好者推出了 **Lisp++** 语言。以下是该语言语法规则的回顾： 一个 Lisp++ 程序是一个由平衡括号组成的字符串。更正式地说，Lisp++ 程序由以下任意一种形式构成（在此规范中，$C$ 代表某段程序代码——每次出现时不一定相同）： - `()`：字面上仅包含一个左括号和一个右括号。我们说这个 `(` 匹配这个 `)`，反之亦然。 - `(C)`：被一对括号包裹的程序。我们说这个 `(` 匹配这个 `)`，反之亦然。 - $CC$：两个程序（不一定相同）连续拼接。 今年，我们很高兴推出 **Emacs++**，一款专为 Lisp++ 设计的文本查看器。Emacs++ 将长度为 $K$ 的 Lisp++ 程序显示为一行长文本，并带有一个可移动的光标。光标是一个“块光标”，始终位于程序的 $K$ 个字符之一上，而非字符之间。 在任何时刻，你可以执行以下三种操作之一来移动光标（$i$ 表示光标的当前位置，从最左侧位置开始计数为 1）： - 将光标向左移动一个字符（若光标已在最左侧字符则不做任何操作）。此操作耗时 $L_i$ 秒。 - 将光标向右移动一个字符（若光标已在最右侧字符则不做任何操作）。此操作耗时 $R_i$ 秒。 - 将光标传送到与第 $i$ 个字符的括号（如上所述）匹配的括号处。此操作耗时 $P_i$ 秒。 我们认为 Emacs++ 对高级用户来说很简单，但仍需了解其效率。我们有一个 Lisp++ 程序和关于该程序的 $Q$ 个查询；每个查询包含一个起始位置 $S_j$ 和一个目标位置 $E_j$。为了回答第 $j$ 个查询，你需要确定在最优决策下，将光标从位置 $S_j$ 移动到位置 $E_j$ 所需的最小时间 $N_j$（以秒为单位）。 请输出所有 $N_j$ 值的总和。

输入的第一行包含测试用例的数量 $T$。随后是 $T$ 个测试用例。每个测试用例的第一行包含两个整数 $K$（表示 Lisp++ 程序的长度）和 $Q$（表示查询的数量）。 每个测试用例的第二行包含一个长度为 $K$ 的字符串 $P$，每个字符为 `(` 或 `)`，表示一个 Lisp++ 程序（平衡括号字符串），如上所述。 每个测试用例的第三、第四和第五行各包含 $K$ 个整数。这些行的第 $i$ 个整数分别为上述的 $L_i$、$R_i$ 和 $P_i$。 每个测试用例的第六和第七行各包含 $Q$ 个整数。这些行的第 $j$ 个整数分别为上述的 $S_j$ 和 $E_j$。

对于每个测试用例，输出一行 `Case #x: y`，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是上述所有 $N_j$ 值的总和。

**样例解释** 在样例中（符合测试集 1 的限制），所有移动的时间成本相同（每次移动 1 秒）。各查询的最短时间如下： 1. 从 $7$ 向右移动五次到 $12$，耗时 $5$ 秒。 2. 从 $4$ 传送到 $11$，耗时 $1$ 秒。 3. 从 $4$ 传送到 $11$，再向左移动到 $10$，耗时 $2$ 秒。 4. 从 $12$ 传送到 $1$，耗时 $1$ 秒。 5. 从 $5$ 向右移动到 $6$，耗时 $1$ 秒。 因此，查询时间的总和为 $5 + 1 + 2 + 1 + 1 = 10$ 秒。 **数据范围** - $1 \leq T \leq 100$。 - 对于最多 9 个测试用例，$K = 10^5$ 且 $Q = 10^5$。 - 其他所有情况下，$2 \leq K \leq 1000$ 且 $1 \leq Q \leq 1000$。 - 字符串 $P$ 的长度为 $K$，且 $P$ 是一个平衡括号字符串，如上所述。 - 对于所有 $j$，$1 \leq S_j \leq K$。 - 对于所有 $j$，$1 \leq E_j \leq K$。 **测试集 1（12 分，可见判定）** - 对于所有 $i$，$L_i = 1$。 - 对于所有 $i$，$R_i = 1$。 - 对于所有 $i$，$P_i = 1$。 **测试集 2（23 分，隐藏判定）** - 对于所有 $i$，$1 \leq L_i \leq 10^6$。 - 对于所有 $i$，$1 \leq R_i \leq 10^6$。 - 对于所有 $i$，$1 \leq P_i \leq 10^6$。 翻译由 DeepSeek V3 完成