【MX-X8-T2】「TAOI-3」终有一天,飞向水平线的彼方
题目背景
天与海交界的地方,到底哪边更深呢?
题目描述
Mio 有一个长度为 $n$ 的正整数数列 $a_1, \ldots, a_n$。她会对这个序列进行若干次操作,每次她会选择一对正整数 $l,r$,满足 $1 \le l \le r \le n$,且 $(r-l+1)$ 为偶数,然后进行以下两种操作中的一种:
- 对于所有整数 $i \in [l,r]$,令 $a_i \gets a_i+\left(|i-\frac{r+l}{2}|+\frac{1}{2}\right)$。
- 对于所有整数 $i \in [l,r]$,令 $a_i \gets a_i-\left(|i-\frac{r+l}{2}|+\frac{1}{2}\right)$。
形象化地,你可以把这理解为,选择某区间内最中间的数作为中轴,然后把区间内的所有数加上或减去它与中轴的距离。例如,如果选择 $l=1$,$r=8$,效果就是把数列的前 $8$ 个数分别加上或减去 $4,3,2,1,1,2,3,4$。
在 Mio 的操作中,她希望任意时刻数列里的所有数都是正整数。
现在,Mio 想要知道,能否用这样的操作把数列 $a_1, \ldots, a_n$ 变成目标正整数数列 $b_1, \ldots, b_n$。
输入输出格式
输入格式
**本题有多组测试数据。**
第一行,一个正整数 $T$,表示测试数据组数。对于每组数据:
- 第一行,一个正整数 $n$。
- 第二行,$n$ 个正整数 $a_1, \ldots, a_n$。
- 第三行,$n$ 个正整数 $b_1, \ldots, b_n$。
输出格式
$T$ 行,对于每组数据,若 Mio 能够达成她的目的,输出一行 `Yes`,否则输出一行 `No`。
输入输出样例
输入样例 #1
2
5
1 3 4 3 3
2 2 3 2 1
5
1 2 1 1 1
1 1 1 2 2
输出样例 #1
Yes
No
说明
**【样例解释】**
对于第一组数据,一种合法的方案为:
先选取 $l=2$,$r=5$ 进行一次减少操作,数列变为 $[1,1,3,2,1]$。
再选取 $l=1$,$r=2$ 进行一次增加操作,数列变为 $[2,2,3,2,1]$。
对于第二组数据,可以证明不存在合法的方案。
**【数据范围】**
对于 $20\%$ 的数据,$n \le 5$,$a_i,b_i \le 4$。
对于另外 $40\%$ 的数据,$\forall 1 \le i \le j \le n$,$a_i=a_j$,$b_i=b_j$。
对于所有数据,保证 $1 \le T \le 5$,$1 \le n \le 10^5$,$1 \le a_i,b_i \le 10^9$。