Let

$p_i=\sum_{j=1}^{i} a_j,\qquad q_i=\sum_{j=1}^{i} b_j.$

The key is to look at prefix sums. One operation on segment $[l,r]$ adds the pattern $+1,-1,+1,-1,\dots$ starting from the left end. Therefore, the prefix sum of the modified array changes by $1$ on some prefixes and by $0$ on the others, so no prefix sum can ever decrease.

Now take the special segment $[i,i+1]$. It adds $+1$ to $a_i$ and $-1$ to $a_{i+1}$, so only the $i$-th prefix sum increases by $1$, while all other prefix sums stay unchanged. Also, $[n,n]$ increases only the $n$-th prefix sum by $1$.

So every prefix sum can be increased independently and never decreased. Hence, the transformation is possible iff

$p_i\le q_i \qquad \text{for all } i.$

Time Complexity: $\mathcal{O}(n)$.

设

$p_i=\sum_{j=1}^{i} a_j,\qquad q_i=\sum_{j=1}^{i} b_j.$

关键在于观察前缀和。对区间 $[l,r]$ 进行一次操作，会从左端开始添加 $+1,-1,+1,-1,\dots$ 的模式。因此，修改后数组的前缀和在某些前缀上增加 $1$，在其他前缀上保持不变，所以任何前缀和都不会减少。

现在考虑特殊区间 $[i,i+1]$。它会使 $a_i$ 增加 $+1$，$a_{i+1}$ 增加 $-1$，因此只有第 $i$ 个前缀和增加 $1$，而其他所有前缀和保持不变。此外，$[n,n]$ 只会使第 $n$ 个前缀和增加 $1$。

因此，每个前缀和都可以独立增加且永不减少。因此，变换可行的充要条件是

$p_i\le q_i \qquad \text{对所有 } i \text{ 成立}.$

时间复杂度：$\mathcal{O}(n)$。

Solution

#include<bits/stdc++.h>
using namespace std;
 
int main(){
 
    int tt;
    cin >> tt;
 
    while(tt--){
        int n;
        cin >> n;
 
        vector<long long> a(n), b(n);
 
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) cin >> b[i];
        for(int i = 1; i < n; i++) a[i] += a[i - 1];
        for(int i = 1; i < n; i++) b[i] += b[i - 1];
 
        bool is = 1;
        for(int i = 0; i < n; i++) if(a[i] > b[i]) is = 0;
 
        if(is) cout << "YES\n";
        else cout << "NO\n";
    }
 
    return 0;
}