分数: 100 点
问题陈述
你有一个字符串 s=s_0s_1...s_{N-1} 长度 N 组成 A 和 B。
你必须处理 Q 查询。
考虑 i- 第一个查询 ( 1 \leq i \leq Q )。
在此查询中,您将获得整数 l_i 和 r_i。
然后,对于每个 x ( l_i \leq x \leq r_i ), s_x 改为另一个字母,即 A 变为 B 和 B 变为 A.
每次查询后,您必须计算 f(B + s + A)。
在这里, f(t) 是一个函数,给定一个字符串 t,返回一个非负整数。
的价值 f(t) 定义如下:
- 考虑以下事项 步骤.
- 步骤:对于 t 与
BA,将其替换为AB。 所有更换均同时完成。
- 步骤:对于 t 与
- f(t) 是直到没有子串为止需要执行的步骤数 t 与
BA.
例如, f(ABAB) = 1, f(BBAA) = 3,和 f(AAA) = 0.
约束
- 1 \leq N \leq 200000
- |s| = N
- s 包括
A和B. - 1 \leq Q \leq 200000
- 0 \leq l_i \leq r_i \leq N-1
- N,Q,l_i,r_i 是整数。
输入
输入由标准输入按以下格式给出:
N s Q l_1 r_1 l_2 r_2 : l_Q r_Q
输出
每次查询后,打印以下值 f(B + s + A),每行一个。
示例输入 1
5 BAABA 2 1 3 0 2
示例输出 1
6 6
第一次查询后,字符串 s is BBBAA,因此打印值 f(BBBBAAA) 在第一行。
第二次查询后,字符串 s is AAAAA,因此打印值 f(BAAAAAA) 在第二行。
示例输入 2
1 A 2 0 0 0 0
示例输出 2
2 2