#P6428. 「JOI 2023 Final」现代机器

    ID: 5917 传统题 2500ms 1024MiB 尝试: 7 已通过: 2 难度: 10 上传者: 标签>难度分类NOI/NOI+/CTS构造与建模不变量分析势能分析排序与序列处理一维前缀和二分查找数据结构可持久化线段树普通线段树线性代数与代数幺半群区间聚合CF3300

「JOI 2023 Final」现代机器

「JOI 2023 Final」现代机器

题目描述

Bitaro 生日这天收到了一个 JOI 机作为生日礼物。JOI 机由一个球,NN 条光带和 MM 个按钮组成。光带从 11 到 NN 编号。当 Bitaro 打开开关时,光带 i (1≤i≤N)i\ (1\le i\le N) 会发出颜色 CiC_i 的光(蓝光 (B\texttt{B}) 或红光 (R\texttt{R}))。按钮从 11 到 MM 编号。如果 Bitaro 按下按钮 j (1≤j≤M)j\ (1\le j\le M),将发生如下事情。

  1. 把球放置在光带 AjA_j 上。
  2. 光带 AjA_j 变成红色(不管它原来是什么颜色)
  3. 进行如下操作,直到球被移除。
    令 pp 为球目前所在的光带编号。
    • 如果光带 pp 是蓝色,
      光带 pp 变为红色。在此之后,如果 p=1p=1,这个球就被移除。否则,球移向光带 p−1p-1。
    • 如果光带 pp 是红色,
      光带 pp 变为蓝色。在此之后,如果 p=Np=N,这个球就被移除。否则,球移向光带 p+1p+1。

Bitaro 对 JOI 机十分感兴趣。他计划进行 QQ 次实验。在第 k (1≤k≤Q)k\ (1\le k\le Q) 次实验中,在 Bitaro 开启电源后,他将按 Lk,Lk+1,…RkL_k,L_k+1,\ldots R_k 的顺序按下这些开关。在 Bitaro 按下一个开关后,他将等到球被移除后再按下下一个开关。

给定 JOI 机和实验的情况,写一个程序计算对于每个实验,当实验结束后红色的光带有多少。

每次实验都从初始颜色串 CC 重新开始;同一次实验内,各次按按钮造成的颜色变化会保留。不同按钮可以把球放到同一条光带上。按按钮时先强制把 AjA_j 变红,再执行移动规则,因此这一轮第一次处理该光带时,会将其变蓝并向右移动或在右端移除。

输入格式

第一行两个整数 N,MN,M。

第二行一个长度为 NN 的字符串 CC,字符串中仅包含字符 R\texttt{R} 和 B\texttt{B}。

第三行 MM 个整数 AjA_j。

第四行一个整数 QQ。

接下来 QQ 行,每行两个整数 Lk,RkL_k,R_k。

输出格式

输出 QQ 行,第 k (1≤k≤Q)k\ (1\le k\le Q) 行输出一个整数,表示当第 kk 个实验结束后红色的光带有多少。

样例输入 1

5 1
RBRRB
4
1
1 1

样例输出 1

1

样例输入 2

5 3
RBRBR
1 3 4
2
2 3
1 3

样例输出 2

5
0

样例输入 3

10 3
BBRRBRBRRB
2 10 5
1
1 3

样例输出 3

2

样例输入 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

样例输入 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

样例输入 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

样例 1 说明

按下按钮 11 后,球从光带 44 开始,其颜色先被设为红色。随后球依次经过 4→5→4→3→4→54\to5\to4\to3\to4\to5,再从右端移除。颜色依次变为

$$\texttt{RBRRB}\to\texttt{RBRBB}\to\texttt{RBRBR}\to\texttt{RBRRR}\to\texttt{RBBRR}\to\texttt{RBBBR}\to\texttt{RBBBB}.$$

最后只有光带 11 为红色,答案为 11。

数据范围与提示

对于全部数据,满足

  • 3≤N≤1.2×1053\le N\le 1.2\times 10^5
  • 1≤M≤1.2×1051\le M\le 1.2\times 10^5
  • Ci (1≤i≤N)C_i\ (1\le i\le N) 不是 B\texttt{B} 就是 R\texttt{R}
  • 1≤Aj≤N (1≤j≤M)1\le A_j\le N\ (1\le j\le M)
  • 1≤Q≤1.2×1051\le Q\le 1.2\times 10^5
  • 1≤Lk≤Rk≤M (1≤k≤Q)1\le L_k\le R_k\le M\ (1\le k\le Q)

详细子任务附加限制及分值如下表。

子任务编号 附加限制 分值
11 N≤300,M≤300,Q≤1N\le 300,M\le 300,Q\le 1 33
22 N≤7 000,M≤7 000,Q=1N\le 7\ 000,M\le 7\ 000,Q=1 1212
33 Q≤5Q\le 5 1010
44 N=10N=10 且 Ci (1≤i≤N)C_i\ (1\le i\le N) 是 R\texttt{R} 1111
55 存在一个整数 t (0≤t≤N)t\ (0\le t\le N),使得对于每个 i≤ti\le t 都有 CiC_i 是 R\texttt{R},对于每个 i>ti>t 都有 CiC_i 是 B\texttt{B} 2626
66 Aj≤20A_j\le 20 或 Aj>N−20 (1≤j≤M)A_j>N-20\ (1\le j\le M) 1717
77 无附加限制 2121