luogu#P9353. [JOI 2023 Final] Modern Machine

[JOI 2023 Final] Modern Machine

题目描述

Bitaro is given JOI machine as a birthday present. JOI machine consists of one ball, NN light tiles, and MM buttons. The light tiles are numbered from 11 to NN. When Bitaro turns the power on, Light tile ii (1iN1 \leq i \leq N) emit light of color CiC_i (blue (B\texttt B) or red (R\texttt R)). The buttons are numbered from 11 to MM. If Bitaro pushes Button jj (1jM1 \leq j \leq M), the following happen.

  1. The ball is placed on Light tile AjA_j.
  2. Light tile AjA_j becomes red (regardless of its original color).
  3. The following operations are performed until the ball is removed.
    Let pp be the index of the light tile where the ball is currently placed.
    • If Light tile pp is blue,
      Light tile pp becomes red. After that, if p=1p = 1, the ball is removed. Otherwise, the ball moves to Light tile p1p − 1.
    • If Light tile pp is red,
      Light tile pp becomes blue. After that, if p=Np = N, the ball is removed. Otherwise, the ball moves to Light tile p+1p + 1.

Bitaro is interested in JOI machine. He plans to perform QQ experiments. In the kk-th experiment (1kQ1 \leq k \leq Q), after Bitaro turns the power on, Bitaro pushes Buttons Lk,Lk+1,,RkL_k, L_{k + 1},\dots , R_k in this order. After Bitaro pushes a button, he will not push the next button and wait until the ball is removed.

Given information of JOI machine and the experiments, write a program which calculates, for each experi- ment, the number of light tiles whose colors are red when the experiment finishes.

输入格式

Read the following data from the standard input.

NN MM
C1 C2CNC_1\ C_2 \dots C_N
A1 A2AMA_1\ A_2 \dots A_M
QQ
L1 R1L_1\ R_1
L2 R2L_2\ R_2
\dots
LQ RQL_Q\ R_Q

输出格式

Write QQ lines to the standard output. In the kk-th line (1kQ1 \leq k \leq Q), the output should contain the number of light tiles whose colors are red when the kk-th experiment finishes.

5 1
RBRRB
4
1
1 1
1
5 3
RBRBR
1 3 4
2
2 3
1 3
5
0
10 3
BBRRBRBRRB
2 10 5
1
1 3
2
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
8
10
0
9
10 10
RRRBBBBBBB
3 1 4 1 5 9 2 6 5 3
5
1 10
2 9
3 8
4 7
5 6
2
6
0
10
7
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
21
15
15
4
17
16
14
20
12
23

提示

【样例解释 #1】

The first experiment proceeds as follows.

  1. Bitaro pushes Button 1, and ball is placed on Light tile 4.
  2. Light tile 4 becomes red. Since the original color of Light tile 4 is red, the color of Light tile 4 does not change.
  3. After that, the following operations are performed.
    (1)Since the current color of Light tile 4 is red, Light tile 4 becomes blue, and the ball moves to Light tile 5.
    (2)Since the current color of Light tile 5 is blue, Light tile 5 becomes red, and the ball moves to Light tile 4.
    (3)Since the current color of Light tile 4 is blue, Light tile 4 becomes red, and the ball moves to Light tile 3.
    (4)Since the current color of Light tile 3 is red, Light tile 3 becomes blue, and the ball moves to Light tile 4.
    (5)Since the current color of Light tile 4 is red, the color of Light tile 4 becomes blue, and the ball moves to Light tile 5.
    (6)Since the current color of Light tile 5 is red, the color of Light tile 5 becomes blue, and the ball is removed.

After the experiment, Light tile 1 is the only light tile whose current color is red. Therefore, output 1.

本样例满足子任务 1,2,3,6,7 的限制。

【样例解释 #2】

For the first experiment, Light tiles 1, 2, 3, 4, 5 are the light tiles whose current colors are red after the experiment. Since there are five such light tiles, output 5.

For the second experiment, there is no light tile whose current color is red after the experiment. Therefore, output 0.

本样例满足子任务 3,6,7 的限制。

【样例解释 #3】

本样例满足子任务 1,2,3,6,7 的限制。

【样例解释 #4】

本样例满足子任务 3,4,5,6,7 的限制。

【样例解释 #5】

本样例满足子任务 3,5,6,7 的限制。

【样例解释 #6】

本样例满足子任务 6,7 的限制。

【数据规模】

对全部的测试点,保证:

  • 3N1.2×1053 \leq N \leq 1.2 \times 10^5
  • 1M1.2×1051 \leq M \leq 1.2 \times 10^5
  • Ci{B,R}C_i \in \{\texttt{B},\texttt{R}\}
  • 1AjN1 \leq A_j \leq N
  • 1Q1.2×1051 \leq Q \leq 1.2 \times 10^5
  • 1LkRkM1 \leq L_k \leq R_k \leq M
  • N,M,Aj,Q,Lk,RkN, M, A_j, Q, L_k, R_k 均为整数。

【子任务】

本题采用捆绑测试

  1. (3 points) N,M300N,M \leq 300Q=1Q = 1
  2. (12 points) N,M7000N, M \leq 7000Q=1Q = 1
  3. (10 points) Q5Q \leq 5
  4. (11 points) N=10N = 10Ci=RC_i = \texttt R
  5. (26 points) 存在一个整数 t[0,N]t \in [0, N],满足对 1it1 \leq i \leq tCi=RC_i = \texttt R;且对 t<iNt < i \leq NCi=BC_i = \texttt B
  6. (17 points) Aj20A_j \leq 20Aj>N20A_j > N - 20
  7. (21 points) 无特殊约定。