CodeforcesRound.770.Div2-F Fibonacci Additions

题目链接

Contest #770 - Problem F

题目描述

You are given two arrays $A$ and $B$ of the same length. We will ask you to perform several Fibonacci additions on these arrays with different parameters, and after each operation you have to report whether arrays $A$ and $B$ are equal modulo $MOD$ .

注意事项

• 中间变量会超出INT_MAX
• (bool) a[i] 的使用

AC代码

#include <iostream>

using namespace std;

const int MAXN = 3e5 + 5;
int n, q, MOD, a[MAXN], f[MAXN], cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    cin >> n >> q >> MOD;
    f[1] = 1;
    for (int i = 2; i <= n; i++)
        f[i] = (f[i - 1] + f[i - 2]) % MOD;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        int b;
        cin >> b;
        a[i] = (a[i] - b + MOD) % MOD;
    }
    for (int i = n; i >= 2; i--)
    {
        a[i] = ((long long) a[i] - a[i - 1] - a[i - 2] + MOD * 2) % MOD; // 规避溢出和Narrowing报错
        cnt += (bool) a[i];
    }
    cnt += (bool) a[1];
    while (q--)
    {
        char flag;
        int l, r;
        cin >> flag >> l >> r;
        cnt -= (bool) a[l];
        if (r + 1 <= n)
            cnt -= (bool) a[r + 1];
        if (r + 2 <= n)
            cnt -= (bool) a[r + 2];
        a[l] = (a[l] + (flag == 'A' ? 1 : MOD - 1)) % MOD;
        if (r + 1 <= n)
            a[r + 1] = (a[r + 1] + (flag == 'A' ? MOD - f[r - l + 2] : f[r - l + 2])) % MOD;
        if (r + 2 <= n)
            a[r + 2] = (a[r + 2] + (flag == 'A' ? MOD - f[r - l + 1] : f[r - l + 1])) % MOD;
        cnt += (bool) a[l];
        if (r + 1 <= n)
            cnt += (bool) a[r + 1];
        if (r + 2 <= n)
            cnt += (bool) a[r + 2];
        cout << (!cnt ? "YES" : "NO") << endl;
    }
    return 0;
}