← 返回题目列表

AtCoder · nikkei2019_2_final_e

E. 臭名昭著的 B.I.T.

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

配点: 800 点

問題文

潜伏很长 N 的位串 我即将向审查委员会提交 S 。这里,什么是位串? 它表示仅由 0 和 按字典顺序比较 1 组成的字符串。

考试标准是 M 可用,i\ (1 \leq i \leq M) 次筛选标准如下。

  • S 可以得到第 L_i 从第一个字符开始 R_i 在提取到字符的子字符串中 包含 1 。

位串满足的标准数量就是该位串的分数。

Snuke 的竞争对手 Sumeke 使用 Snuke 提交的位串。 我决定将其更改 S 该值应乘以 Q 次。j\ (1 \leq j \leq Q) 第一个改变从头开始。 X_j 第一个字母,0 如果 1 属于1 如果 0 。

你的工作是为了Sumeke君,Q 查找每次更改后产生的位串的分数。 是一个字符串

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • S 是 您也可以写 0, 1 组成的长度 N 除
  • 1 \leq L_i \leq R_i \leq N
  • 1 \leq X_j \leq N
  • S 外,所有输入均为整数

入力

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

N M Q
S
L_1 R_1
:
L_M R_M
X_1
:
X_Q

出力

Q 行。 列出i 行中,i 创建的位串的分数。


入力例 1

3 4 4
011
1 3
2 2
1 2
2 3
3
2
1
3

出力例 1

4
0
2
3
  • 1 第二次查询后,位串为 010 ,满足所有审核条件。
  • 2 第二次查询后,位串为 000 ,不符合任何审核条件。
  • 3 第二次查询后,位串为 100 ,即 满足第 1, 3 个检查条件。
  • 4 第二次查询后,位串为 101 ,即 满足第 1, 3, 4 个检查条件。

入力例 2

50 10 10
10010000000001000000001000000000000000000100000000
2 25
11 33
20 31
21 26
26 50
4 42
23 40
2 8
36 37
15 18
20
1
4
49
14
10
23
37
42
20

出力例 2

8
8
7
7
7
7
5
7
7
5