问题 3347 --括号

3347: 括号

时间限制: 1 Sec  内存限制: 256 MB
提交: 1  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

圆给了你一个长度为n的字符串S，S仅由 ( 和 ) 构成。

她会对其做 m 次操作，操作有两种类型：

、 1 、l r，她会翻转 l 到 r 的括号，即 ( 变 )，) 变 (。  

  2、 2 l r，她想知道区间 [l,r] 中最长合法括号子序列的长度除以 2 的答案。

圆认为以下的括号序列是合法的：

  1. 空序列是一个合法序列。

  2. 如果 A 是一个合法序列，则 (A) 也是一个合法序列。

  3. 如果 A 和 B 都是合法序列，则 AB 也是一个合法序列。

圆认为，序列 a 的子序列是满足 1≤i1<i2<⋅⋅⋅<ik≤n 的序列 [ai1,ai2,...aik]。

由于操作太多了，她算不过来，请你帮帮她吧。

输入

第一行一个整数 n。

第二行一个长度为 n 的字符串 S，保证仅由 ( 和 ) 构成 。

第三行一行一个整数 m。

接下来 m 行，每行三个数 op，l，r，对应上面的两种操作。

输出

对于每一个 op=2 的操作，输出一行一个整数，表示答案。

样例输入

6
(()())
5
2 2 3
1 1 3
2 2 3
2 4 6
2 3 6

样例输出

1
0
1
2

提示


说明/提示





【样例解释】




  • 第一次截取的字符串是 ()，答案为 1。


  • 翻转后字符串变为 ))(())。


  • 第二次截取的字符串是 )(，答案为 0。


  • 第三次截取的字符串是 ())，答案为 1。


  • 第四次截取的字符串是 (())，答案为 2。



【数据范围】




  • 对于 10% 的数据，1≤n,m≤500；


  • 对于 20% 的数据，1≤n,m≤5000；


  • 对于 40% 的数据，1≤n,m≤2×10^5；


  • 另有 10% 的数据，满足 op=2 且数据随机生成；


  • 另有 15% 的数据，满足 op=2 但不保证数据随机生成；



对于所有数据，保证 1≤n≤5×10^5，1≤m≤5×10^5，1≤l≤r≤n，op∈{1,2}。数据有梯度。



来源

线段树 

[提交][状态]