33OJ
登录 注册

#P17494. [ICPC 2026 Wuhan I] Sequence Operations

    ID: 20222 远端评测题 2000ms 512MiB 尝试: 0 已通过: 0 显示难度普及+/提高− 上传者: 标签>Special JudgeICPC2026Ad-hoc省赛/邀请赛湖北

[ICPC 2026 Wuhan I] Sequence Operations

题目描述

给定一个长度为 nn 的非负整数序列 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n,以及两个长度为 mm 的序列 c1,c2,⋯ ,cmc_1,c_2,\cdots,c_m 和 x1,x2,⋯ ,xmx_1,x_2,\cdots,x_m。保证 xix_i 均为正整数。

你需要从 11 到 mm 依次顺序执行 mm 次操作。在第 ii 次操作中,你可以根据 cic_i 的值对当前的序列 aa 进行修改:

  • 若 ci=1c_i=1,那么你只能对所有的 aja_j 执行 aj←mex⁡(aj,xi)a_j\leftarrow\operatorname{mex}(a_j,x_i)。
  • 若 ci=2c_i=2,那么你只能对所有的 aja_j 执行 aj←gcd⁡(aj,xi)a_j\leftarrow\gcd(a_j,x_i)。
  • 若 ci=0c_i=0,你可以自由选择执行上述两种操作中的任意一种。

在所有 mm 次操作执行完毕后,判断最后能不能让序列 aa 中的所有数都相等。

关于运算 mex⁡\operatorname{mex} 和 gcd⁡\gcd 的额外说明如下:

  • 定义二元操作 mex⁡(u,v)\operatorname{mex}(u,v) 表示不等于 uu 且不等于 vv 的最小非负整数。例如:mex⁡(0,1)=2\operatorname{mex}(0,1)=2,mex⁡(2,2)=0\operatorname{mex}(2,2)=0。
  • 对于最大公约数 gcd⁡\gcd,特别定义 gcd⁡(0,x)=x\gcd(0,x)=x。

输入格式

输入包含多组测试数据。第一行包含一个整数 TT(1≤T≤1041 \le T \le 10^4),表示测试数据组数。

对于每组测试数据:

  • 第一行包含两个整数 n,mn,m(1≤n,m≤3×1051 \le n,m \le 3\times10^5),分别表示序列 aa 的长度和操作的次数。
  • 第二行包含 nn 个非负整数 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n(0≤aj≤1090 \le a_j \le 10^9),表示初始序列。
  • 接下来 mm 行,第 ii 行包含两个整数 ci,xic_i,x_i(0≤ci≤20 \le c_i \le 2,1≤xi≤1091 \le x_i \le 10^9),表示第 ii 次操作的类型参数和数值参数。

保证所有测试数据中 ∑n≤3×105\sum n \le 3\times10^5 且 ∑m≤3×105\sum m \le 3\times10^5。

输出格式

对于每组测试数据输出一行。如果在所有操作结束后能让所有数都相等,则输出 “Yes”;否则输出 “No”。

7
8 6
3 1 4 1 5 9 2 6
0 1
0 1
0 4
0 5
0 1
0 4
3 1
0 1 2
1 1
3 1
0 1 2
2 1
4 2
3 3 5 0
1 1
2 3
2 2
3 0
2 4
2 2
4 2
3 0 2 0
1 1
1 3
3 4
1 4 0
1 1
1 1
0 4
2 2
Yes
No
Yes
No
No
No
Yes

提示

对于第一组数据:在第一次操作时,选择执行 gcd⁡\gcd 操作,序列将变为 [1,1,1,1,1,1,1,1][1,1,1,1,1,1,1,1]。在后续的 55 次操作中,你无论选择什么操作,序列元素始终会保持一致,因此输出 “Yes”。

对于第二组数据:唯一的一次操作是 c1=1c_1=1,x1=1x_1=1,你只能选择 mex⁡\operatorname{mex} 操作。

  • a1←mex⁡(0,1)=2a_1\leftarrow\operatorname{mex}(0,1)=2
  • a2←mex⁡(1,1)=0a_2\leftarrow\operatorname{mex}(1,1)=0
  • a3←mex⁡(2,1)=0a_3\leftarrow\operatorname{mex}(2,1)=0

最终序列变为 [2,0,0][2,0,0],无法让所有数字相等,输出 “No”。