P10513 括号

圆给了你一个长度为 $n$ 的字符串 $S$，$S$ 仅由 ```(``` 和 ```)``` 构成。 她会对其做 $m$ 次操作，操作有两种类型： 1. ```1 l r```，她会翻转 $l$ 到 $r$ 的括号，即 ```(``` 变 ```)```，```)``` 变 ```(```。 1. ```2 l r```，她想知道区间 $\left[ l,r\right]$ 中最长合法括号子序列的长度除以 $2$ 的答案。 圆认为以下的括号序列是合法的： 1. 空序列是一个合法序列。 1. 如果 ```A``` 是一个合法序列，则 ```(A)``` 也是一个合法序列。 1. 如果 ```A``` 和 ```B``` 都是合法序列，则 ```AB``` 也是一个合法序列。 圆认为，序列 $a$ 的子序列是满足 $1\le i_1

无

无

**【样例解释】** - 第一次截取的字符串是 ```()```，答案为 $1$。 - 翻转后字符串变为 ```))(())```。 - 第二次截取的字符串是 ```)(```，答案为 $0$。 - 第三次截取的字符串是 ```())```，答案为 $1$。 - 第四次截取的字符串是 ```(())```，答案为 $2$。 **【数据范围】** - 对于 $10\%$ 的数据，$1 \leq n,m \leq 500$； - 对于 $20\%$ 的数据，$1 \leq n,m \leq 5000$； - 对于 $40\%$ 的数据，$1 \leq n,m \leq 2\times 10^5$； - 另有 $10\%$ 的数据，满足 $op=2$ 且数据随机生成； - 另有 $15\%$ 的数据，满足 $op=2$ 但不保证数据随机生成； 对于所有数据，保证 $1\le n \le 5\times 10^5$，$1\le m \le 5 \times 10^5$，$1 \le l \le r \le n$，$op \in \{1,2\}$。数据有梯度。