分数: 100 点
问题陈述
给你两个非负整数序列 A 和 B,每个长度 N。最初, A=(A_1, A_2, \ldots, A_N) 和 B=(B_1, B_2, \ldots, B_N).
你将得到 Q 查询。按给定顺序处理它们。
每个查询是以下两种类型之一:
- 类型 1:以格式给出
1 i a b. 更新的值 A_i to a 和的值 B_i to b. - 类型 2:以格式给出
2 Y 0 0。解决以下问题:对于非负整数 S,定义一个非负整数序列 X = (X_0, X_1, \dots, X_N) 使用以下递推关系:
- X_0 = S
- 对于每个 1 \le i \le N, X_i = \begin{cases} X_{i - 1} \oplus A_i & \text{if } X_{i - 1} \equiv 1 \pmod{2} \\ X_{i - 1} \oplus B_i & \text{if } X_{i - 1} \equiv 0 \pmod{2} \end{cases}
判断是否可以设置一个非负整数 S 这样 X_N = Y。如果可能,输出最小的此类 S.
如果没有这样的 S 存在,输出-1.
约束
- 所有输入均为整数。
- 1 \le N \le 2 \times 10^5
- 1 \le Q \le 2 \times 10^5
- 0 \le A_i, B_i < 2^{60} \ (1 \le i \le N)
- 对于一种类型 1 查询, 1 \le i \le N, 0 \le a, b < 2^{60}
- 对于一种类型 2 查询, 0 \le Y < 2^{60}
- 至少有一种类型 2 查询。
部分分数
30 通过满足附加约束的测试集将获得积分 Q=1.
输入
输入按以下格式给出:
N Q
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N
\mathrm{query}_1
\vdots
\mathrm{query}_Q
在这里, \mathrm{query}_i 代表 i-第一个查询,并以下列格式之一给出:
1 i a b
2 Y 0 0
输出
让 q 是类型的数量 2 查询。输出 q 行,其中 i- 第行包含以下问题的答案 i-第类型 2 查询。
示例输入 1
1 3 0 1 2 5 0 0 2 6 0 0 2 7 0 0
示例输出 1
4 -1 6
鉴于 A = (0),\ B = (1)的值 X_N 是:
- X_N = S if S 是奇数。
- X_N = S \oplus 1 if S 是偶数。
对于第一个查询 Y = 5,两者 S = 4 和 S = 5 结果 X_N = 5,所以最小 S is 4.
对于第二个查询 Y = 6,没有 S 这样 X_N = 6,所以输出 -1.
对于第三个查询 Y = 7,两者 S = 6 和 S = 7 结果 X_N = 7,所以最小 S is 6.
示例输入 2
10 1 310214852498133736 505276263682091678 273987911350501637 317207700241861186 878845869214220663 722059890180131902 597424946894933345 74297940232615233 969543184238991085 567669635596262039 760374976835769237 114205047640377864 975115657391620675 659404150340533368 514313531921108960 255579815636209538 1042405225853490071 891193105039531117 1032475514675208675 968262176137127595 2 942999108116930288 0 0
示例输出 2
494185924924343867
示例输入 3
10 5 20 19 18 17 16 15 14 13 12 11 11 12 13 14 15 16 17 18 19 20 2 8 0 0 1 6 100 200 2 12 0 0 1 10 32 662 2 100 0 0
示例输出 3
8 103 -1
示例输入 4
10 5 464468010685205695 652469322679259637 207750579744900414 551282264132274959 477385551779769369 457669217633528368 1124978699497706079 993018743713584412 347799342391956023 253839229959865684 43481420251962425 913779804742334221 721829783836314668 643562100144275666 148532568860178532 348780722732705987 905040003050597634 962374691997649953 160408954061784257 6313574278114070 2 942999108116930288 0 0 1 7 911289147093700219 315969390490734880 2 570806468566359262 0 0 1 5 865153057674787555 127079554510737035 2 71991180131886804 0 0
示例输出 4
167766290121628811 833427363106128513 657636533261400102