Codeforces 1634 F. Fibonacci additions - Fibonacci sequence addition, ideas

This way

The question ：

I'll give you a length of n Array of a And an array b, There will be one operation at a time ：
x l r
If x yes A Represents in the array a Operation on top , It is b
l r Indicates that the interval will be [l,r] Add the Fibonacci sequence to the one-to-one correspondence [1,r-l+1] Number of numbers .
Ask you the last a and b Whether it is equal or not .

Answer key ：

It seems that Fibonacci sequence addition has been done before ？447E Well , That is to use the nature of Fibonacci , I forgot to go back and have a look .

The first thing that comes to mind in this problem is to put b Reduced to a On , Then just use it on an array , Each time you check whether it is all 0 That's all. .
And then what to do , I thought for a while about what to do with the line segment tree , So I changed my mind ：
set up f[x] It is the th of Fibonacci series x position ,f[x]=f[x-1]+f[x-2].
Since the Fibonacci sequence is simply adding before and after , It can be expressed by difference .
If you use a[i] Express a[i]-a[i-1]-a[i-2] Well , That interval plus f[l:r] It turns into a[l]+1,a[r+1]-f[r-l+2]？
This is a normal difference , But here we are a[i] Minus the a[i-1] and a[i-2], therefore a[r] Changes in will affect a[r+2].
about a[r+3], It is maintained a[r+2] and a[r+1], Since these two have not changed , that a[r+3] It hasn't changed .
that a[r+2] How much has changed ？ We can find out a[r] Combined with the f[r-l+1],a[r+1] unchanged , that a[r+2] Because the maintenance is a[r+2]-a[r+1]-a[r], So we should reduce f[r-l+1].
And then use num To maintain the current 0 The number of .

But it's easy here TLE ah , I can change it no matter how I change it T, Finally, put longlong It's not until you get rid of it

#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;
}