CF1634 F. Fibonacci Additions

The question ：$q$ operations , Every time you give an array $A$ perhaps $B$ Of $[l,r]$ Position plus a Fibonacci sequence , Ask after each operation $AB$ Whether the arrays are the same
Consider Fibonacci's generating function
$$\begin{gathered} f(x)=1+1x+2x^2+...+fi{b}_{i-1}{x}^i+...=\sum _{i=0}fi{b}_{i+1}{x}^i \\ xf(x)=\sum _{i=1}fi{b}_i{x}^i,x^{2}f(x)=\sum _{i=2}fi{b}_{i-1}{x}^i \\ f(x)-xf(x)-x^{2}f(x)=1 \\ f(x)=\frac{1}{1-x-x^2} \end{gathered}$$
If you put $A,B$ As two polynomials
$$\begin{gathered} A(x)=\sum _{i=1}^n{a}_i{x}^i \\ B(x)=\sum _{i=1}^n{b}_i{x}^i \end{gathered}$$
So in $A$ Array $[l,r]$ Position plus a Fibonacci sequence is equivalent to
$$\begin{gathered} A(x)+=x^{l}f(x)-fi{b}_{r-l+2}{x}^{r}f(x)-fi{b}_{r-l+1}{x}^{r+1}f(x) \\ *A(x)+=x^l\frac{1}{1-x-x^2}-fi{b}_{r-l+2}{x}^r\frac{1}{1-x-x^2}-fi{b}_{r-l+1}{x}^{r+1}\frac{1}{1-x-x^2} \end{gathered}$$
Ride on both sides $(1-x-x^2)$
$$*(1-x-x^2)A(x)+=x^l-fi{b}_{r-l+2}{x}^r-fi{b}_{r-l+1}{x}^{r+1}$$
The complexity of each modification is reduced to $O(1)$
Then consider $(1-x-x^2)A(x)$ The practical significance of , That is, construct an auxiliary array $D$
$$D_i=A_i-A_{i-1}-A_{i-2}$$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    
	int n,q,mod;
	scanf("%d%d%d",&n,&q,&mod);
	vector<int>a(n+1),b(n+1);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	for(int i=1;i<=n;i++)scanf("%d",&b[i]);
	for(int i=n;i>=2;i--)
	{
    
		a[i]-=a[i-1]+a[i-2];
		a[i]=(a[i]%mod+mod)%mod;
	}
	for(int i=n;i>=2;i--)
	{
    
		b[i]-=b[i-1]+b[i-2];
		b[i]=(b[i]%mod+mod)%mod;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)cnt+=(a[i]!=b[i]);
	vector<int>fib(n+5);
	fib[1]=1%mod;
	fib[2]=1%mod;
	for(int i=3;i<=n;i++)fib[i]=(fib[i-1]+fib[i-2])%mod;
	// printf("cnt=%d\n",cnt);
	// for(int j=1;j<=n;j++)printf("%d%c",a[j]," \n"[j==n]);
	// for(int j=1;j<=n;j++)printf("%d%c",b[j]," \n"[j==n]);
	for(int i=1;i<=q;i++)
	{
    
		char c[2];
		scanf("%s",c);
		int l,r;
		scanf("%d%d",&l,&r);
		auto add=[&](int id,int pos,int add)
		{
    
			// printf("id=%d pos=%d add=%d\n",id,pos,add);
			if(pos>n)return;
			if(id==1)
			{
    
				cnt-=(a[pos]!=b[pos]);
				a[pos]+=add;
				a[pos]=(a[pos]%mod+mod)%mod;
				cnt+=(a[pos]!=b[pos]);
			}
			else
			{
    
				cnt-=(a[pos]!=b[pos]);
				b[pos]+=add;
				b[pos]=(b[pos]%mod+mod)%mod;
				cnt+=(a[pos]!=b[pos]);
			}
		};
		if(c[0]=='A')
		{
    
			add(1,l,1);
			add(1,r+1,-fib[r-l+2]);
			add(1,r+2,-fib[r-l+1]);
		}
		else
		{
    
			add(2,l,1);
			add(2,r+1,-fib[r-l+2]);
			add(2,r+2,-fib[r-l+1]);
		}
		// printf("q=%d cnt=%d\n",i,cnt);
		// for(int j=1;j<=n;j++)printf("%d%c",a[j]," \n"[j==n]);
		// for(int j=1;j<=n;j++)printf("%d%c",b[j]," \n"[j==n]);
		if(cnt==0)printf("YES\n");
		else printf("NO\n");

	}	
    return  0;
}