题目描述
现在给你一个数列，长度为n（n <= 100000）,数列中的每一个数的绝对值不超过10000。定义一个对 i 的操作会造成这样的结果
操作前 ai-1, ai ,ai+1 ===》》 操作后 ai-1 + ai , -ai , ai+1 + ai
第一个数和最后一个数是不被允许进行操作的。现在，给你两个序列，问是否能够通过对第一个数列进行操作，从而使其转换为第二个数列
如果可以，输出“YES”，否则输出“NO”(均不包括引号)
输入说明
第一行一个正整数T(T <= 10)表示测试组数
对于每一组测试数据有三行，第一行为两个序列的长度n，下面两行是两个数列中元素的值
输出说明
对于每一组测试数据，输出一行”YES”或”NO”
样例输入
3
6 5 5 1 6 1 6
18 -8 1 -6 12 7
6
5 0 3 0 6 2
5 9 -6 0 -3 11
6
-5 -3 0 -1 0
-8 0 6 5 0 8 5
样例输出
YES
YES
NO
题目分析：
我们可以很简单地发现，我们操作过后，所有元素的总和是不变的。所以我们可以先判断一下两个数列的元素的总和是不是相等的，如果相等再进行下一步的判断，如果不相等就可以直接输出NO了。
我们进一步挖掘每一次操作的本质，设Si表示前缀和，我们发现，对于一个操作，他的前缀和的变化是
a[i-1] + a[i] , -a[i] ,a[i+1] + a[i]
S[i-1] + a[i],S[i-1],S[i+1]
而我们知道S[i-1] + a[i] == S[i]
也就是说，前缀和从S[i-1] , S[i] , S[i+1] 变成了S[i],S[i-1],S[i+1]
所以我们发现，每一次操作的本质就是交换前缀和，绝对不会产生新的前缀和。所以我们直接判断一下两个数组的前缀和出现的数字是不是全部相等就可以了，复杂度O(nlogn)，排序复杂度
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(ll &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');
if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
inline ll cat_max(const ll &a,const ll &b){return a>b ? a:b;}
inline ll cat_min(const ll &a,const ll &b){return a<b ? a:b;}
const ll maxn = 1000010;
ll a[maxn],b[maxn],n;
bool judge(){
if(a[n] != b[n]) return false;
sort(a+1,a+n);sort(b+1,b+n);
for(ll i=1;i<n;++i) if(a[i] != b[i]) return false;
return true;
}
int main(){
ll T;read(T);
while(T--){
read(n);
for(ll i=1;i<=n;++i) read(a[i]),a[i] += a[i-1];
for(ll i=1;i<=n;++i) read(b[i]),b[i] += b[i-1];
if( judge() ) puts("YES");
else puts("NO");
}
//getchar();getchar();
return 0;
}