Codeforces 1634 F. Fibonacci Additions —— 斐波那契数列加，想法

This way

题意：

给你长度为n的数组a和数组b，每次会有一个操作：
x l r
如果x是A表示在数组a上进行操作，否则是b
l r表示将区间[l,r]的数一一对应加上斐波那契数列[1,r-l+1]的数。
问你最后a和b是否相等。

题解：

斐波那契数列加的题目之前好像做到过？447E吧，那个是使用到了斐波那契的性质，有点忘了到时候回去再看看。

这道题首先想到的就是把b减到a上，然后就只用在一个数组上，每次查看是否全为0即可了。
然后该怎么办呢，用线段树该怎么做我想了一会想不太到，于是更改思路：
设f[x]就是斐波那契数列的第x位，f[x]=f[x-1]+f[x-2]。
既然斐波那契数列是简单的相加前推后，它可以使用差分表示。
如果用a[i]表示a[i]-a[i-1]-a[i-2]呢，那区间加上f[l:r]不就变成了a[l]+1,a[r+1]-f[r-l+2]？
这是正常的差分，但是我们这里a[i]减去了a[i-1]和a[i-2]，所以a[r]的变动会影响到a[r+2]。
对于a[r+3]，它是维护了a[r+2]和a[r+1]，既然这两个没变，那a[r+3]也就没变。
那么a[r+2]变了多少？我们可以发现a[r]加上了f[r-l+1]，a[r+1]不变，那么a[r+2]由于维护的是a[r+2]-a[r+1]-a[r]，所以应该减小f[r-l+1]。
然后用num维护当前0的数量。

不过这里好容易TLE啊，我怎么改怎么改都T，最后把longlong改掉了才过

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e5+5;
int f[N],a[N],b[N];
int n,q;
    int mod;
void add(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
    if(x<0)x+=mod;
}
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin>>n>>q>>mod;
    f[1]=f[2]=1;
    int num=0;
    for(int i=3;i<N;i++)add(f[i],f[i-1]+f[i-2]);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++){
        cin>>b[i],add(b[i],a[i]-2*b[i]);
        add(a[i],-a[i]+b[i]-b[i-1]);
        if(i>1)add(a[i],-b[i-2]);
        num+=a[i]==0;
    }
    while(q--){
        char s[5];
        int l,r;
        cin>>s>>l>>r;
        if(s[0]=='A'){
            if(a[l]==0)num--;
            if(r+1<=n&&a[r+1]==0)num--;
            if(r+2<=n&&a[r+2]==0)num--;
            add(a[l],1),add(a[r+1],-f[r-l+2]),add(a[r+2],-f[r-l+1]);
            if(a[l]==0)num++;
            if(r+1<=n&&a[r+1]==0)num++;
            if(r+2<=n&&a[r+2]==0)num++;
        }
        else{
            if(a[l]==0)num--;
            if(r+1<=n&&a[r+1]==0)num--;
            if(r+2<=n&&a[r+2]==0)num--;
            add(a[l],-1),add(a[r+1],f[r-l+2]),add(a[r+2],f[r-l+1]);
            if(a[l]==0)num++;
            if(r+1<=n&&a[r+1]==0)num++;
            if(r+2<=n&&a[r+2]==0)num++;
        }
        if(num==n)
            cout<<"YES\n";
        else
            cout<<"NO\n";
    }
    return 0;
}