2023-ho-t5_Modern_Machine — JOI JOI
Task type: batch | Time limit: 2.5 s | Memory limit: 1024 MB | Difficulty: 27
Algorithms: dynamic programming, case analysis, data structures, implementation, segment tree

![](_page_0_Picture_0.jpeg)

![](_page_0_Picture_2.jpeg)

# 5 Modern Machine

Bitaro is given JOI machine as a birthday present. JOI machine consists of one ball, $N$ light tiles, and $M$ buttons. The light tiles are numbered from 1 to $N$. When Bitaro turns the power on, Light tile $i$ $(1 \le i \le N)$ emit light of color $C_i$ (blue (B) or red (R)). The buttons are numbered from 1 to $M$. If Bitaro pushes Button $j$ $(1 \le j \le M)$, the following happen.

1.  The ball is placed on Light tile $A_j$.
2.  Light tile $A_j$ becomes red (regardless of its original color).
3.  The following operations are performed until the ball is removed.

    Let $p$ be the index of the light tile where the ball is currently placed.

    If Light tile $p$ is blue,

    Light tile $p$ becomes red. After that, if $p = 1$, the ball is removed. Otherwise, the ball moves to Light tile $p - 1$.

    If Light tile $p$ is red,

    Light tile $p$ becomes blue. After that, if $p = N$, the ball is removed. Otherwise, the ball moves to Light tile $p + 1$.

Bitaro is interested in JOI machine. He plans to perform $Q$ experiments. In the $k$-th experiment $(1 \le k \le Q)$, after Bitaro turns the power on, Bitaro pushes Buttons $L_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 experiment, the number of light tiles whose colors are red when the experiment finishes.

![](_page_1_Picture_0.jpeg)

### Input

Read the following data from the standard input.

```
N M
C1 C2 ... CN
A1 A2 ... AM
Q
L1 R1
L2 R2
...
LQ RQ
```

### Output

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

### Constraints

*   $3 \le N \le 120\,000$.
*   $1 \le M \le 120\,000$.
*   $C_i$ $(1 \le i \le N)$ is either B or R.
*   $1 \le A_j \le N$ $(1 \le j \le M)$.
*   $1 \le Q \le 120\,000$.
*   $1 \le L_k \le R_k \le M$ $(1 \le k \le Q)$.
*   $N, M, A_j, Q, L_k, R_k$ are integers.

![](_page_2_Picture_0.jpeg)

### Subtasks

*   1. (3 points) $N \le 300$, $M \le 300$, $Q = 1$.
*   2. (12 points) $N \le 7\,000$, $M \le 7\,000$, $Q = 1$.
*   3. (10 points) $Q \le 5$.
*   4. (11 points) $N = 10$, and $C_i$ is R $(1 \le i \le N)$.
*   5. (26 points) There exists an integer $t$ $(0 \le t \le N)$ such that $C_i$ is R for every $i \le t$, and $C_i$ is B for every $i > t$.
*   6. (17 points) $A_j \le 20$ or $A_j > N - 20$ $(1 \le j \le M)$.
*   7. (21 points) No additional constraints.

![](_page_3_Picture_0.jpeg)

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 5 1            | 1              |
| RBRRB          |                |
| 4              |                |
| 1              |                |
| 1 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. This sample input satisfies the constraints of Subtasks 1, 2, 3, 6, 7.

![](_page_4_Picture_0.jpeg)

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 5 3            | 5              |
| RBRBR          | 0              |
| 1 3 4          |                |
| 2              |                |
| 2 3            |                |
| 1 3            |                |

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.

This sample input satisfies the constraints of Subtasks 3, 6, 7.

| Sample Input 3     | Sample Output 3 |
| :----------------- | :------------- |
| 10 3               | 2              |
| BBRRBRBRRB         |                |
| 2 10 5             |                |
| 1                  |                |
| 1 3                |                |

This sample input satisfies the constraints of Subtasks 1, 2, 3, 6, 7.

| Sample Input 4      | Sample Output 4 |
| :------------------ | :------------- |
| 10 10               | 4              |
| RRRRRRRRRR          | 8              |
| 3 1 4 1 5 9 2 6 5 3 | 10             |
| 5                   | 0              |
| 1 7                 | 9              |
| 2 8                 |                |
| 3 9                 |                |
| 4 10                |                |
| 1 10                |                |

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6, 7.

![](_page_5_Picture_0.jpeg)

| Sample Input 5      | Sample Output 5 |
| :------------------ | :------------- |
| 10 10               | 2              |
| RRRBBBBBBB          | 6              |
| 3 1 4 1 5 9 2 6 5 3 | 0              |
| 5                   | 10             |
| 1 10                | 7              |
| 2 9                 |                |
| 3 8                 |                |
| 4 7                 |                |
| 5 6                 |                |

This sample input satisfies the constraints of Subtasks 3, 5, 6, 7.

| Sample Input 6                 | Sample Output 6 |
| :----------------------------- | :------------- |
| 30 10                          | 21             |
| RRRBBRBBBRBBBRBRBRRRRRBBBBRBRR | 15             |
| 3 28 2 29 1 30 6 14 7 7        | 15             |
| 10                             | 4              |
| 1 10                           | 17             |
| 2 3                            | 16             |
| 2 5                            | 14             |
| 2 8                            | 20             |
| 3 3                            | 12             |
| 3 6                            | 23             |
| 4 5                            |                |
| 4 7                            |                |
| 5 9                            |                |
| 10 10                          |                |

This sample input satisfies the constraints of Subtasks 6, 7.

Starter code: