← 返回题目列表

AtCoder · ttpc2024_2_d

D. 奇数异或

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

分数: 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