P17848 豚豚和兔兔的配对问题

今天是个特别的日子。无数只豚豚和兔兔结伴来到字串符的世界玩耍。每只兔兔会和最近的豚豚配对然后找上一个未配对的豚豚和与他匹配的兔兔一起玩。这实在太复杂了，于是我们把这个配对问题抽象成一个括号字串符交由屏幕前聪明的你来解决！ :::align{center}  严肃的豚豚和兔兔 ::: 给定一个长度为 $n$ 的括号字符串 $S$，其中每个字符都是 `(` 或 `)`。**字符串 $S$ 一定合法括号序列**。字符串中的位置从 $1$ 开始编号。 一个括号序列是合法的，当且仅当它满足以下两个条件： - 左括号与右括号的数量相同； - 任意前缀中，左括号的数量都不少于右括号的数量。 原字符串中的匹配关系按以下规则确定：从左到右扫描字符串，每个右括号与它之前最近的、尚未匹配的左括号匹配。如果不存在这样的左括号，则该右括号未匹配。因为保证原括号串合法，每个括号必定存在匹配。 每个位置 $i$ 有一个非负整数权值 $a_i$。另外，给定一个非负整数外部权值 $w_0$。 **子串的价值** 考虑一个非空合法括号子串 $S[x \ldots y]$。 如果原字符串中存在一对匹配括号，其左右端点分别为 $p$ 和 $k$，且满足: $$p < x \le y < k,$$ 则称这对括号严格包围该子串。 如果存在严格包围该子串的匹配括号对，则选择其中最内层的一对，即左端点 $p$ 最大的一对。该子串的价值为: $$a_p \oplus a_k,$$ 其中 $\oplus$ 表示按位异或。 如果不存在严格包围该子串的匹配括号对，则该子串的价值为 $w_0$。 **匹配关系始终以原字符串为准。包围子串的括号可以位于查询区间外，不合法的括号子串不提供贡献。** 例如，对于字符串 `(()())`： - 子串 $S[2 \ldots 3]$ 为 `()`，其价值为 $a_1 \oplus a_6$； - 子串 $S[2 \ldots 5]$ 为 `()()`，其价值也为 $a_1 \oplus a_6$； - 整个字符串 $S[1 \ldots 6]$ 的价值为 $w_0$。 对于字符串 `(()`，位置 $1$ 的左括号未匹配，因此子串 $S[2 \ldots 3]$，即 `()`，的价值为 $w_0$。 **操作** 你需要处理 $q$ 次操作： - `1 p v`：将位置 $p$ 的权值 $a_p$ 修改为 $v$； - `2 l r`：求所有完全位于区间 $[l,r]$ 内的非空合法括号子串的价值之和。 对于查询操作，需要统计的子串 $S[x \ldots y]$ 必须满足: $$ l \le x \le y \le r. $$

第一行包含三个整数 $n$（$1 \le n \le 10^6$），$q$（$1 \le q \le 10^6$），$w_0$（$0 \le w_0\le 65535$），分别表示字符串长度、操作次数和外部权值。 第二行包含一个长度为 $n$ 的字符串 $S$，其中每个字符都是 `(` 或 `)`。**保证 $S$ 是合法括号序列。** 第三行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，依次表示每个字符位置的初始权值。 接下来 $q$ 行，每行描述一次操作，格式为以下两种之一： - `1 p v`：将位置 $p$（$1 \le p \le n$）的权值修改为 $v$（$0 \le v\le 65535$）； - `2 l r`：查询区间 $[l,r]$（$1 \le l \le r \le n$）内所有非空合法括号子串的价值之和。

对于每次查询操作，输出一行一个整数，表示符合条件的所有非空合法括号子串的价值之和。 如果不存在符合条件的子串，输出 $0$。

初始时，外层匹配括号的左右端点分别为 $1$ 和 $6$，其权值异或为 $$ a_1 \oplus a_6 = 1 \oplus 4 = 5. $$ 所有非空合法括号子串及其价值如下： - 子串 $S[2 \ldots 3]$ 为 `()`，价值为 $5$； - 子串 $S[4 \ldots 5]$ 为 `()`，价值为 $5$； - 子串 $S[2 \ldots 5]$ 为 `()()`，价值为 $5$； - 子串 $S[1 \ldots 6]$ 为 `(()())`，没有被任何匹配括号对严格包围，价值为 $w_0=2$。 因此，第一次查询的答案为: $$ 5+5+5+2=17. $$ 第二次查询的区间为 $[2,5]$，只统计前三个子串，答案为 $15$。虽然包围它们的括号位于查询区间外，但仍然决定这些子串的价值。 将 $a_6$ 修改为 $7$ 后，外层匹配括号的权值异或变为: $$ a_1 \oplus a_6 = 1 \oplus 7 = 6. $$ 此时，查询整个字符串得到的答案为: $$ 6+6+6+2=20. $$ 区间 $[3,4]$ 对应的子串为 `)(`，不存在非空合法括号子串，因此答案为 $0$。 随后将 $a_1$ 修改为 $3$，外层匹配括号的权值异或变为: $$ a_1 \oplus a_6 = 3 \oplus 7 = 4. $$ 最后一次查询的区间为 $[2,5]$，答案为: $$ 4+4+4=12. $$