cf1634 F. Fibonacci Additions

题意：

给定两个一样长的数组 \(a,b\) 和一个模数 \(M\)。每次操作选定一个数组的一个区间，将区间中的数对位加上斐波那契数列（1,1,2,3,...）

每次操作后，判断两个数组是否在模 \(M\) 意义下是否相同。

\(n,q\le 3e5,0\le a_i,b_i\le M\)

思路：

俩数组对应位置作差，记录非零的数量，全为0就是相等。

考虑差分数组 \(d_i=a_{i}-a_{i-1}-a_{i-2}\)，每次操作 \([l,r]\) 只需改变三个位置：\(d_l,d_{r+1},d_{r+2}\)

ll n, q, mod, a[N], b[N], fib[N], sum;

void add(int x, int y) {
    sum -= (a[x] != 0);
    a[x] += y, a[x] %= mod;
    if(a[x] < 0) a[x] += mod;
    sum += (a[x] != 0);
}

signed main() {
    iofast;
    cin >> n >> q >> mod;
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1, x; i <= n; i++) {
        cin >> x, a[i] -= x;
        a[i] %= mod; if(a[i] < 0) a[i] += mod;
    }
    //变成差分数组
    for(int i = n; i >= 2; i--) {
        a[i] -= a[i-1] + a[i-2];
        a[i] %= mod; if(a[i] < 0) a[i] += mod;
        if(a[i]) sum++; //非零的个数
    }
    if(a[1]) sum++;
    //预处理斐波那契数列
    fib[1] = 1; for(int i = 2; i < N; i++)
        fib[i] = (fib[i-1] + fib[i-2]) % mod;

    while(q--) {
        char c; int t, l, r; cin >> c >> l >> r;
        t = (c == 'A' ? 1 : -1);
        add(l, t);
        if(r + 1 <= n) add(r+1, -t * fib[r-l+2]);
        if(r + 2 <= n) add(r+2, -t * fib[r-l+1]);

        cout << (!sum ? "YES" : "NO") << endl;
    }
}