分数: 500 点
问题陈述
你的长度是-N 整数序列 A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N),每个由 0 和 1。 让 A[i,j] 表示连续子序列 A 来自 i-th 通过 j- 第一个元素。如果 i>j,然后 A[i,j] 是一个长度-0 序列。 您可以执行以下操作 A 任意次数:
- 选择四个整数 a,b,c,d 满足以下两个条件:
- 1 \leq a \leq b < c \leq d \leq N
- \sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}
- 交换 A[a,b] 和 A[c,d]。更准确地说,替换 A 与通过连接形成的序列 A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] 按此顺序。
判断是否 A 可以匹配 B.
解决 T 每个输入文件的测试用例。
约束
- 1 \leq T \leq 10^5
- 2 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 1
- 0 \leq B_i \leq 1
- 总和 N 所有测试用例最多 2\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个案例均按以下格式给出:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
总共输出答案 T 行。
的 t- 第行应包含 Yes if A 可以匹配 B 为 t- 第一个测试用例,以及 No 否则。
示例输入 1
3 6 1 1 1 0 0 1 0 1 1 0 1 1 2 0 0 1 0 3 1 1 1 1 1 1
示例输出 1
Yes No Yes
在第一个测试用例中, A 最初是 (1,1,1,0,0,1).
通过选择 (a,b,c,d)=(1,2,3,6) 并执行操作, A 变为 (1,0,0,1,1,1).
接下来,通过选择 (a,b,c,d)=(1,2,3,4) 并执行操作, A 变为 (0,1,1,0,1,1),匹配 B.
在第二个测试用例中, A 无法匹配 B.
在第三个测试用例中, A 已匹配 B 从头开始。