/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
0 と 1 からなる長さ N の整数列 A=(A_1,A_2,\dots,A_N),\; B=(B_1,B_2,\dots,B_N) が与えられます。 数列 A の i 番目から j 番目の連続部分列を A[i,j] と表すことにします。ただし、i>j のとき、A[i,j] は長さ 0 の数列とします。 A に対して、以下の操作を何回でも行えます。
- 以下の 2 条件を満たす 4 整数 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 に一致させられるかどうかを判定してください。
1 つの入力ファイルにつき、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 行目には、t 番目のテストケースについて A を B に一致させられるならば Yes を、一致させられないならば 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
1 つ目のテストケースでは、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 に一致します。
2 つ目のテストケースでは、A を B に一致させることはできません。
3 つ目のテストケースでは、A は最初から B に一致しています。
Score : 500 points
Problem Statement
You are given length-N integer sequences A=(A_1,A_2,\dots,A_N) and B=(B_1,B_2,\dots,B_N), each consisting of 0 and 1. Let A[i,j] denote the consecutive subsequence of A from the i-th through the j-th element. If i>j, then A[i,j] is a length-0 sequence. You can perform the following operation on A any number of times:
- Choose four integers a,b,c,d that satisfy the following two conditions:
- 1 \leq a \leq b < c \leq d \leq N
- \sum_{i=a}^{b}{A_i}=\sum_{i=c}^{d}{A_i}
- Swap A[a,b] and A[c,d]. More precisely, replace A with the sequence formed by concatenating A[1,a-1], A[c,d], A[b+1,c-1], A[a,b], A[d+1,N] in this order.
Determine whether A can be made to match B.
Solve T test cases for each input file.
Constraints
- 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
- The sum of N over all test cases is at most 2\times 10^5.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each case is given in the following format:
N A_1 A_2 \dots A_N B_1 B_2 \dots B_N
Output
Output the answers in a total of T lines.
The t-th line should contain Yes if A can be made to match B for the t-th test case, and No otherwise.
Sample Input 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
Sample Output 1
Yes No Yes
In the first test case, A is initially (1,1,1,0,0,1).
By choosing (a,b,c,d)=(1,2,3,6) and performing the operation, A becomes (1,0,0,1,1,1).
Next, by choosing (a,b,c,d)=(1,2,3,4) and performing the operation, A becomes (0,1,1,0,1,1), which matches B.
In the second test case, A cannot be made to match B.
In the third test case, A already matches B from the beginning.