← 返回题目列表

Codeforces · 1083/F

F. 公平的坚果和有趣的异或

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

Fair Nut 有两个数组 $$$a$$$ 和 $$$b$$$,由 $$$n$$$ 数字组成。他很久以前就发现了它们,以至于没有人知道它们是什么时候找到他的。

公平坚果经常改变他的数组中的数字。他还对每次修改后 $$$a$$$ 和 $$$b$$$ 的相似程度感兴趣。

让我们将两个数组的相似性表示为使数组相等所应用的最小操作数(每个操作都可以应用于两个数组)。如果不可能,相似度将等于$$$-1$$$。

每一次操作可以选择一个长度为 $$$k$$$ 的子数组($$$k$$$ 是固定的),并将属于所选子数组的每个元素 $$$a_i$$$ 更改为 $$$a_i \oplus x$$$ ($$$x$$$ 可以选择),其中 $$$\oplus$$$ 表示按位异或运算。

Nut已经计算了每次修改后数组的相似度。你能做到吗?

请注意,您只需要计算这些值,即不需要应用任何操作。

输入

第一行包含三个数字 $$$n$$$、$$$k$$$ 和 $$$q$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$, $$$0 \le q \le 2 \cdot 10^5$$$) - 数组的长度、应用操作的子数组的长度以及数量的查询。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i < 2^{14}$$$) — 数组 $$$a$$$ 的元素。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i < 2^{14}$$$) — 数组 $$$b$$$ 的元素。

接下来的 $$$q$$$ 行描述查询并包含字符串 $$$s$$$ 和两个整数 $$$p$$$ 和 $$$v$$$ ($$$1 \le p \le n$$$, $$$0 \le v < 2^{14}$$$) — 数组,此查询更改的数组(不带引号的 «a» 或 «b»)、更改元素的索引及其新值。

输出

在第一行打印数组 $$$a$$$ 和 $$$b$$$ 的初始相似性。

在应用第一个 $$$i$$$ 修改后,在以下 $$$q$$$ 行的第 $$$i$$$ 行上打印 $$$a$$$ 和 $$$b$$$ 的相似性。

示例

输入 #1

3 3 1
0 4 2
1 2 3
b 2 5

输出 #1

-1
1

输入 #2

3 2 2
1 3 2
0 0 0
a 1 0
b 1 1

输出 #2

2
-1
2

注意

在第一个示例中,使用 $$$k=3$$$ 不可能创建数组 $$$[0, 4, 2]$$$ 和 $$$[1, 2, 3]$$$。修改后,你可以对整个第一个数组(其长度等于$$$k$$$)进行$$$x=1$$$运算,它将等于第二个数组。

为了使更改前第二个示例中的数组相等,您可以在 $$$a$$$ 的子数组 $$$[1, 2]$$$ 上应用 $$$x=1$$$ 运算,并在 $$$b$$$ 的子数组 $$$[2, 3]$$$ 上应用 $$$x=2$$$ 运算。

所有查询后数组将等于 $$$[0, 3, 2]$$$ 和 $$$[1, 0, 0]$$$。相同的操作使它们等于 $$$[1, 2, 2]$$$。