← 返回题目列表

AtCoder · jag2018summer_day2_j

J. AB 排序

中文机器翻译题面 查看原题

分数: 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。 所有更换均同时完成。
  • 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