← 返回题目列表

Codeforces · 1847/D

D. 东方教授

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

仗助厌倦了他在杜王市的平静生活。他追随侄子承太郎的脚步,决定努力学习,成为一名计算机科学教授。在网上查找编程竞赛题时,他遇到了以下问题:

令 $$$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$$$,这是您可以实现的按字典顺序排列的最大字符串。