← 返回题目列表

AtCoder · joi2023ho_e

E. 现代机器

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

配点: 100 点

問題文

Bitaro收到了一台JOI机器作为生日礼物。 JOI机器是1 的 您可以创建一个包含 球,N 的 您可以创建一个包含 轻质瓷砖 它由,M 的 您可以创建一个包含 按钮 组成。 每个灯瓦都有 它们的编号最大为 1 减去 N 。 当您打开电源时,灯光平铺 i (1 \leqq i \leqq N) 是颜色 C_i (青 (B),赤 (R))。 另外,每个按钮都有一个 它们的编号最大为 1 减去 M 。 按钮 当您按 j (1 \leqq j \leqq M)时,会发生以下情况: 球被放置在

  1. 轻质瓷砖 它由 A_j 的顶部。
  2. 轻质瓷砖 它由 A_j 的颜色变为红色(无论其原始颜色如何)。
  3. 重复以下操作,直到球被移除。

    当前放置球的灯块的编号。 p 。

    轻质瓷砖 它由 p 的颜色是蓝色
    轻质瓷砖 它由 p 的颜色变为红色。之后,如果 如果 p=1 则球被移除,否则球被移动到光块上。 移至 p-1 上方。 如果
    轻质瓷砖 它由 p 的颜色为红色
    轻质瓷砖 它由 p 的颜色变为蓝色。之后,如果 p=N 则球被移除,否则球被移动到光块上。 移至 p+1 上方。 如果

Bitaro,对JOI机器感兴趣, 我们正在计划Q 实验。 在 k 回目 (1 \leqq k \leqq Q)实验中,打开JOI机后,按下按钮 按此顺序按 L_k, L_k+1, \ldots, R_k 。 但是,您必须等待,不要按下一步按钮,直到球被移除。

给定JOI机器信息和实验信息, 对于每个实验,编写一个程序来查找实验结束后颜色为红色的光砖的数量。


入力

输入是按以下格式从标准输入给出的。

N M
C_1C_2 \cdots C_N
A_1 A_2 \cdots A_M
Q
L_1 R_1
L_2 R_2
\vdots
L_Q R_Q

出力

到标准输出 输出 Q 输出行。 k 行目 (1 \leqq k \leqq Q)有k 输出第一个实验结束后颜色为红色的光块的数量。


制約

  • 3 \leqq N \leqq 120\,000.
  • 1 \leqq M \leqq 120\,000.
  • C_i (1 \leqq i \leqq N) 是 B 或 至少 R 。
  • 1 \leqq A_j \leqq N (1 \leqq j \leqq M).
  • 1 \leqq Q \leqq 120\,000.
  • 1 \leqq L_k \leqq R_k \leqq M (1 \leqq k \leqq Q).
  • N, M, A_j, Q, L_k, R_k 是整数。

小課題

  1. (3 点) N \leqq 300,M \leqq 300,Q = 1.
  2. (12 点) N \leqq 7\,000,M \leqq 7\,000,Q = 1.
  3. (10 点) Q \leqq 5.
  4. (11 点) N = 10,C_i 是 您也可以写 R (1 \leqq i \leqq N).
  5. (26 点) i \leqq t 如果 C_i 是 在 R 和i > t 如果 C_i 是 在 B 一个整数使得 t (0 \leqq t \leqq N)存在。
  6. (17 点) A_j \leqq 20 或 至少 A_j > N - 20 (1 \leqq j \leqq M).
  7. (21 点)没有额外的限制。

入力例 1

5 1
RBRRB
4
1
1 1

出力例 1

1

1 实验进行如下。 按下

  1. 按钮 1 ,球就会移动到右侧的方块上。 放置在 4 上方。
  2. 轻质瓷砖 它由 4 的颜色变为红色。然而,它本来就是一块轻质瓦。 由于 4 的颜色是红色,因此它是浅色瓷砖。 4 的颜色没有改变。
  3. 然后发生以下情况。
    1. 当前光砖 4 的颜色是红色,因此它是浅色瓷砖。 4 颜色变为蓝色,球移动到浅色方块上。 5 上方。 如果
    2. 当前光砖 5 的颜色是蓝色,因此它是浅色瓷砖。 5 颜色变为红色,球移动到浅色方块上。 4 上方。 如果
    3. 当前光砖 4 的颜色是蓝色,因此它是浅色瓷砖。 4 颜色变为红色,球移动到浅色方块上。 3 上方。 如果
    4. 当前光砖 3 的颜色是红色,因此它是浅色瓷砖。 3 颜色变为蓝色,球移动到浅色方块上。 4 上方。 如果
    5. 当前光砖 4 的颜色是红色,因此它是浅色瓷砖。 4 颜色变为蓝色,球移动到浅色方块上。 5 上方。 如果
    6. 当前光砖 5 的颜色是红色,因此它是浅色瓷砖。 5 颜色变为蓝色,球被移除。

实验结束时,颜色为红色的光砖称为光砖。 1 可以得到第 1 因为只有1 。 你只需要砍掉

此输入示例是一个小作业。 1, 2, 3, 6, 7 满足约束。


入力例 2

5 3
RBRBR
1 3 4
2
2 3
1 3

出力例 2

5
0

1 第二个实验,实验结束时,颜色为红色的光砖就是光砖。 1, 2, 3, 4, 5 可以得到第 5 因为它是5 。 你只需要砍掉

2 对于第二个实验,实验结束时不存在颜色为红色的光块,因此0 。 你只需要砍掉

此输入示例是一个小作业。 3, 6, 7 满足约束。


入力例 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

出力例 3

2

此输入示例是一个小作业。 1, 2, 3, 6, 7 满足约束。


入力例 4

10 10
RRRRRRRRRR
3 1 4 1 5 9 2 6 5 3
5
1 7
2 8
3 9
4 10
1 10

出力例 4

4
8
10
0
9

此输入示例是一个小作业。 3, 4, 5, 6, 7 满足约束。


入力例 5

10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6

出力例 5

2
6
0
10
7

此输入示例是一个小作业。 3, 5, 6, 7 满足约束。


入力例 6

30 10
RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR
3 28 2 29 1 30 6 14 7 7
10
1 10
2 3
2 5
2 8
3 3
3 6
4 5
4 7
5 9
10 10

出力例 6

21
15
15
4
17
16
14
20
12
23

此输入示例是一个小作业。 6, 7 满足约束。