P17799 [CXOI R7-C] 晴天

当知道真正的我的时候，你还会用司空见惯的笑脸和我说话吗？

Luminescent 有一个长度为 $n$ 的只由左括号 `(` 和右括号 `)` 组成的括号序列 $s$，下标从 $1$ 开始。 现在你可以在 $s$ 串的基础上构建一张 $n$ 个点，编号为 $1\sim n$ 的无向图 $G$。在图 $G$ 上，两个点 $u,v(u

第一行两个整数 $n,Q$。 然后一行一个长度为 $n$，只由 `(` 和 `)` 两个字符组成的括号序列 $s$。注意不保证 $s$ 是合法的括号序列。 然后 $Q$ 行，一行三个整数，格式形如： + `1 l r`：Luminescent 对字符串 $s$ 进行了一次修改操作：对于 $s_l,s_{l+1},\ldots,s_r$ 中的每个括号，若该括号为 `(`，则将其修改为 `)`；否则，将其修改为 `(`。 + `2 x y`：Loyalty 想要知道 $s$ 串构建的无向图 $G$ 中，从 $x$ 结点到 $y$ 结点的路径最少需要经过多少条边。特殊的，若不存在任何一条这样的路径，则输出 $-1$。

对于每个 $2$ 操作，一行一个整数表示答案。

**样例解释** 初始字符串为 `()(()())`。 第一次询问：点 $1,2$ 之间存在边，答案为 $1$。 第二次询问：最短路径为 $2\to1\to8\to3$，答案为 $3$。 第三次询问：点 $3,8$ 之间存在边，答案为 $1$。 第一次修改后，字符串变为 `(())()()`。 第四次询问：点 $1,8$ 之间存在边，答案为 $1$。 第五次询问：最短路径为 $4\to1\to8\to5$，答案为 $3$。 第二次修改后，点 $2,7$ 不连通，答案为 $-1$。 #### 【数据范围与约定】 **本题采用捆绑测试。** 对于 $10\%$ 的分数满足 $n,Q\le 100$。 对于 $20\%$ 的分数满足 $n,Q\le 300$。 对于 $30\%$ 的分数满足 $n,Q\le 2000$。 对于另外 $10\%$ 的分数满足没有 $1$ 操作。 对于另外 $10\%$ 的分数满足所有 $1$ 操作均有 $l=r$。 对于另外 $5\%$ 的分数满足没有 $2$ 操作。 对于另外 $15\%$ 的分数满足 $2$ 操作查询的两个点 $x,y$ 在生成的图 $G$ 上一定是连通的。 对于全部的分数满足 $1\le n,Q\le 2\times 10^5,1\le x,y\le n,1\le l\le r\le n$，$s$ 中每个字符都是 `(` 或 `)`。