解题思路
01 串的权值定义为:只由字符 '1' 构成的非空连续子串数量。
如果一段连续的 '1' 的长度为 len,那么这段内部能产生的全 '1' 子串数量为:
1+2+⋯+len=2len(len+1)
P4954.第3题- 小红的01串操作
题目内容
小红定义一个仅由字符 '0' 和 '1' 组成的字符串(简称 01 串)的权值为:
现给定一长为 n 的 01 串,小红会对其进行 q 次操作,每次操作选取 01 串的一位将其反置(若原字符为 '1',反置后为 '0';若原字符为 '0',反置后为 '1')。
你需要计算每次操作后 01 串的权值是多少。
【名词解释】
连续子串:从原字符串中,连续的选择一段字符(可以全选、可以不选)得到的新字符串。
输入描述
第一行输入两个整数 n,q (1≤n≤2×105,1≤q≤2×105)。
第二行输入一个长为 n 的 01 串。
之后 q 行,每行输入一个整数 k (1≤k≤n) 代表一次操作,将 01 串的第 k 位反置。
输出描述
输出 q 行,每行包含一个整数,代表此次操作后 01 串的权值。
样例1
输入
5 2
10010
2
3
输出
4
10