配点: 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