仗助厌倦了他在杜王市的平静生活。他追随侄子承太郎的脚步,决定努力学习,成为一名计算机科学教授。在网上查找编程竞赛题时,他遇到了以下问题:
令 $$$s$$$ 为长度为 $$$n$$$ 的二进制字符串。 $$$s$$$ 上的操作定义为选择两个不同的整数 $$$i$$$ 和 $$$j$$$ ($$$1 \leq i < j \leq n$$$),并交换字符 $$$s_i, s_j$$$。
考虑 $$$m$$$ 字符串 $$$t_1, t_2, \ldots, t_m$$$,其中 $$$t_i$$$ 是 $$$s$$$ 从 $$$l_i$$$ 到 $$$r_i$$$ 的子串 $$$^\dagger$$$。将 $$$t(s) = t_1+t_2+\ldots+t_m$$$ 定义为字符串 $$$t_i$$$ 按此顺序的串联。
字符串有 $$$q$$$ 更新。在第 $$$i$$$ 次更新中,$$$s_{x_i}$$$ 被翻转。也就是说,如果 $$$s_{x_i}=1$$$,则 $$$s_{x_i}$$$ 变为 $$$0$$$,反之亦然。每次更新后,找出必须对 $$$s$$$ 执行的最小操作数,以使 $$$t(s)$$$ 按字典顺序尽可能大$$$^\ddagger$$$。
请注意,实际上没有执行任何操作。我们只对操作的数量感兴趣。
帮助仗助解决梦中的问题。
——————————————————————
$$$\dagger$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
$$$\ddagger$$$ 当且仅当以下条件成立时,字符串 $$$a$$$ 按字典顺序大于相同长度的字符串 $$$b$$$:
- 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,字符串 $$$a$$$ 有一个 $$$1$$$,而字符串 $$$b$$$ 有一个 $$$0$$$。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$、$$$q$$$ ($$$1 \leq n,m,q \leq 2 \cdot 10^5$$$)。
下一行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$,仅由数字 $$$0$$$ 和 $$$1$$$ 组成。
接下来的 $$$m$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$)。
接下来的 $$$q$$$ 行中的第 $$$i$$$ 行包含单个整数 $$$x_i$$$ ($$$1 \leq x_i \leq n$$$)。
输出
打印 $$$q$$$ 整数。第 $$$i$$$ 整数是在第 $$$i$$$ 轮中获得按字典顺序最大的可能字符串 $$$t(s)$$$ 所需对 $$$s$$$ 执行的最小操作数。
示例
输入 #1
2 2 4 01 1 2 1 2 1 1 2 2
输出 #1
0 1 0 1
输入 #2
8 6 10 10011010 5 6 2 3 6 8 5 7 5 8 6 8 3 5 6 2 5 2 5 8 4 1
输出 #2
2 3 2 2 1 2 2 2 2 2
注意
在第一个测试用例中,
最初,$$$t(s) = s(1,2) + s(1,2) = 0101$$$。
在 $$$1$$$-st 查询之后,$$$s$$$ 变为 $$$11$$$,因此 $$$t$$$ 变为 $$$1111$$$。您不需要执行任何操作,因为 $$$t(s)$$$ 已经是字典中可能的最大字符串。
在 $$$2$$$-nd 查询之后,$$$s$$$ 变为 $$$01$$$,因此 $$$t$$$ 变为 $$$0101$$$。您需要通过交换$$$s_1$$$和$$$s_2$$$来执行$$$1$$$操作。因此,$$$t(s)$$$ 变为 $$$1010$$$,这是您可以实现的按字典顺序排列的最大字符串。