#P18393. Infinite Parenthesis Sequence

Infinite Parenthesis Sequence

Infinite Parenthesis Sequence

BaoBao 在左口袋里找到一个长度为 nn 的括号序列 A=a0,a1,…,an−1A=a_0,a_1,\ldots,a_{n-1},每个元素都是左括号 ( 或右括号 )。他不喜欢短序列,于是将这个序列向两边无限重复,得到序列 BB。

设 bib_i 是 BB 的第 ii 个元素。下标 ii 可以是正数、零或负数,定义为:

$$b_i=\begin{cases}a_i,&0\le i<n,\\b_{i-n},&i\ge n,\\b_{i+n},&i<0.\end{cases}$$

接着他制作了一个生成器。令 BkB^k 为第 kk 次生成的无限序列,bikb_i^k 为它的第 ii 个元素;定义 B0=BB^0=B。对所有整数下标 ii,同时按照下面的规则,从 Bk−1B^{k-1} 得到 BkB^k:

$$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}$$

所有位置都读取上一轮的序列,不能把本轮已经更新的位置用于计算其它位置。

给定若干询问 (k,l,r)(k,l,r),请计算 blk,bl+1k,…,brkb_l^k,b_{l+1}^k,\ldots,b_r^k 中左括号 ( 的数量。

输入格式

第一行包含整数 TT,表示测试用例数量。

对于每个测试用例:

  • 第一行包含字符串 ss(1≤∣s∣≤1051\le |s|\le10^5),仅由 ( 和 ) 组成,表示 AA。字符串第 ii 个字符对应 ai−1a_{i-1}。
  • 第二行包含整数 qq(1≤q≤1051\le q\le10^5)。
  • 接下来 qq 行,每行包含三个整数 k,l,rk,l,r(0≤k≤1090\le k\le10^9,−109≤l≤r≤109-10^9\le l\le r\le10^9)。

保证所有测试用例的 ∣s∣|s| 之和不超过 10610^6,所有测试用例的 qq 之和不超过 10610^6。原题未单独限制 TT;由上述限制可知 T≤106T\le10^6。

输出格式

每个询问输出一行一个整数,表示 BkB^k 的闭区间 [l,r][l,r] 内左括号的数量。

样例

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

样例说明

第一个测试用例中,以从下标 00 开始的一个周期表示序列,B0B^0 的周期是 (()),B1B^1 的周期是 ()(),B2B^2 的周期是 )()(。对应三个询问的答案为 3,3,03,3,0。

第二个测试用例中,B0,B1,B2,B3B^0,B^1,B^2,B^3 从下标 00 开始的周期分别为 ))()(、())()、)())(、()())。对应答案为 4,1,14,1,1。这些有限字符串都表示向正、负两个方向无限重复,不能将周期边界当作序列边界。