区间dp题解

首先将数组做环形差分，记差分数组为，可以发现，只要全0，相当于就可以对全局做一个确定次数的操作，把也变成全相等的数组。

于是考虑能不能把变成全0。我们可以发现，对于点，可以传递到。于是我们可以利用并查集，把所有向合并，维护成几个联通块，每个联通块内的可以相互传递。

也就是说，对于所有联通块，块内所有的和为0，才能让全局的都为0。时间复杂度 。

// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define int long long

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n), b(n), c(n);
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int i = 0; i < n; ++i)
        std::cin >> b[i];
    std::vector<int> f(n + 2);
    std::iota(f.begin(), f.end(), 0);
    auto find = [&](auto&& find, int x) -> int {
        return f[x] == x ? x : f[x] = find(find, f[x]);
    };
    auto merge = [&](int x, int y) {
        x = find(find, x);
        y = find(find, y);
        if (x != y) {
            f[x] = y;
        }
    };
    for (int i = 0; i < n; i++) {
        if (i == 0)
            c[i] = b[0] - b[n - 1];
        else
            c[i] = b[i] - b[i - 1];
    }
    for (int i = 0; i < n; i++)
        merge(i, (i + a[i] - 1) % n);
    std::vector<int> sum(n);
    for (int i = 0; i < n; i++) {
        sum[find(find, i)] += c[i];
    }
    for (int i = 0; i < n; i++) {
        if (sum[find(find, i)] != 0) {
            std::cout << "NO\n";
            return;
        }
    }
    std::cout << "YES\n";
}
signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    int t = 1;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}