D - Bbubel oSrt
Darjeeling
2
s
1024
MB
500
点
問題文
長さ $N$ の整数列 $A = (A_1, A_2, \ldots , A_N), B = (B_1, B_2, \ldots , B_N)$ があります。
以下の操作を好きな回数( $0$ 回でもよい)繰り返すことで、$A$ を $B$ に一致させることが可能か判定してください。
- $1\leq i\leq N-1$ かつ $A_i > A_{i+1}$ であるような整数 $i$ を選び、$A_i$ と $A_{i+1}$ を入れ替える
$T$ 個のテストケースについて答えてください。
制約
- $1 \leq T$
- $2\leq N\leq 2 \times 10^5$
- $1\leq A_i \leq N$
- $1\leq B_i \leq N$
- $1$ つの入力に含まれるテストケースについて、$N$ の総和は $2 \times 10^5$ 以下
- 入力はすべて整数
この問題には部分点が設定されている。
- $A_i \leq 3$, $B_i \leq 3$ をみたすデータセットに正解した場合は、400点が与えられる。
入力
入力は、以下の形式で標準入力から与えられる。
$T$
$case_1$
$case_2$
$\vdots$
$case_T$
各ケースは以下の形式で与えられる。
$N$
$A_1; A_2; \cdots; A_N$
$B_1; B_2; \cdots; B_N$
出力
$T$ 行出力せよ。
$i$ 行目には、$i$ 番目のテストケースについて、一致させることが可能な場合 Yes を、不可能な場合は No を出力せよ。
入力例 1
4
5
3 1 1 2 3
1 1 2 3 3
4
3 1 2 3
3 2 1 3
3
2 1 1
3 2 2
5
1 1 1 2 2
1 1 1 2 2
出力例 1
Yes
No
No
Yes
この入力は部分点の制約をみたします。
- ケース $1$ つ目は、$i = 1, 2, 3$ の順に操作を行うことで、$A$ は順に $(1, 3, 1, 2, 3), (1, 1, 3, 2, 3), (1,1,2, 3, 3)$ と変化し、$B$ に一致させることが可能です。
- $2$ つ目、$3$ つ目はどのように操作をしても一致させることができません。
- $4$ つ目は $1$ 度も操作しなくても一致しています。