#P18393. Infinite Parenthesis Sequence
Infinite Parenthesis Sequence
Infinite Parenthesis Sequence
BaoBao 在左口袋里找到一个长度为 的括号序列 ,每个元素都是左括号 ( 或右括号 )。他不喜欢短序列,于是将这个序列向两边无限重复,得到序列 。
设 是 的第 个元素。下标 可以是正数、零或负数,定义为:
$$b_i=\begin{cases}a_i,&0\le i<n,\\b_{i-n},&i\ge n,\\b_{i+n},&i<0.\end{cases}$$接着他制作了一个生成器。令 为第 次生成的无限序列, 为它的第 个元素;定义 。对所有整数下标 ,同时按照下面的规则,从 得到 :
$$b_i^k=\begin{cases}b_{i+1}^{k-1},&b_i^{k-1}=\texttt{(},\\b_{i-1}^{k-1},&b_i^{k-1}=\texttt{)}.\end{cases}$$所有位置都读取上一轮的序列,不能把本轮已经更新的位置用于计算其它位置。
给定若干询问 ,请计算 中左括号 ( 的数量。
输入格式
第一行包含整数 ,表示测试用例数量。
对于每个测试用例:
- 第一行包含字符串 (),仅由
(和)组成,表示 。字符串第 个字符对应 。 - 第二行包含整数 ()。
- 接下来 行,每行包含三个整数 (,)。
保证所有测试用例的 之和不超过 ,所有测试用例的 之和不超过 。原题未单独限制 ;由上述限制可知 。
输出格式
每个询问输出一行一个整数,表示 的闭区间 内左括号的数量。
样例
3
(())
3
0 -3 2
1 -2 3
2 0 0
))()(
3
0 -3 4
2 1 3
3 -4 -1
))()(()(
4
1234 -5678 9012
123 -456 789
12 -34 56
1 -2 3
3
3
0
4
1
1
7345
623
45
3
样例说明
第一个测试用例中,以从下标 开始的一个周期表示序列, 的周期是 (()), 的周期是 ()(), 的周期是 )()(。对应三个询问的答案为 。
第二个测试用例中, 从下标 开始的周期分别为 ))()(、())()、)())(、()())。对应答案为 。这些有限字符串都表示向正、负两个方向无限重复,不能将周期边界当作序列边界。