CF1634F Fibonacci Additions 题解

传送门。

题目大意：给定两个序列 \(A\) 和 \(B\)，每次一个可以选一个区间，并在区间的第 \(i\) 个数加上 \(F_i\)，其中 \(F\) 是斐波那契数列，你需要在每次询问结束时输出两个序列是否相等。

可以先求一个序列 \(C\) 表示 \(A\) 和 \(B\) 每个位置的差，即 \(C_i=A_i-B_i\)，然后问题就转换为了在 \(C\) 上面选区间加减，每次看 \(C\) 是否全为 \(0\)。

区间加减，很容易就能想到差分数组，我们看一下差分数组的定义：\(D_i=C_i-C_{i-1}\)，它适用的区间加减是加或减同一个数，这样 \(C_i-C_{i-1}\) 不会变。

继续考虑斐波那契的性质：\(F_i=F_{i-1}+F_{i-2}\)，所以 \(F_i-F_{i-1}-F_{i-2}=0\)，那么每次区间加减时，区间内的数 \(C_i-C_{i-1}-C_{i-2}\) 就不会变，于是可以得出 \(D\) 数组的定义：\(D_i=C_i-C_{i-1}-C_{i-2}\)。

然后每次区间加减就只需要改边界上的值就行了，而且 \(C\) 全为 \(0\) 和 \(D\) 全为 \(0\) 是等价的，所以每次只用看 \(D\) 是否全为 \(0\) 就行了。具体来说，用一个 \(cnt\) 来记录 \(D\) 中 \(0\) 的个数。

#include <iostream>
#include <cstdio>
#define ll long long
using namespace std;
const int N = 3e5+5;
int n,q,mod;
ll d[N],f[N],cnt;
void up(int x,ll v)
{
    if(x>n)return;
    cnt -= !d[x];(d[x] += v+mod) %= mod;
    cnt += !d[x];
}
int main()
{
    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++)scanf("%d",d+i);
    for(int i = 1;i <= n;i++)
    {
        int x;scanf("%d",&x);
        (d[i] -= x-mod) %= mod;
    }
    for(int i = n;i;i--)
    {
        d[i] = (d[i]-d[i-1]-d[i-2]+mod+mod)%mod;
        cnt += !d[i];
    }
    while(q--)
    {
        int l,r;char s[5];
        scanf("%s %d %d",s,&l,&r);
        if(s[0]=='A'){up(l,1);up(r+1,-f[r-l+2]);up(r+2,-f[r-l+1]);}
        else{up(l,-1);up(r+1,f[r-l+2]);up(r+2,f[r-l+1]);}
        puts(cnt==n?"YES":"NO");
    }
}