题目
长为n(n<=3e5)的序列a、b，模数mod(1<=mod<=1e9+7)
两个序列有初值，0<=ai,bi q(q<=3e5)次操作，每次给一个a或b的区间加上一个斐波那契数列，
此处，fib[1]=fib[2]=1%mod，fib[i]=(fib[i-1]+fib[i-2])%mod
A l r，对a[l]加fib[1]%mod，...，对a[r]加fib[r-l+1]%mod
B l r，对b[l]加fib[1]%mod，...，对b[r]加fib[r-l+1]%mod
每次操作后，询问两个序列是否在模mod意义下完全相同，相同输出YES，否则输出NO
思路来源 Codeforces Round #770 (Div、2) F(构造/差分) - 知乎
题解 首先，令a[i]=a[i]-b[i]，
这样对a序列/b序列加fib序列，就变成对a序列加/减fib序列
然后，构造长为n+2的新数组c[i]=a[i]-a[i-1]-a[i-2]，
这样，对于一段区间加/减fib数列，
只有c[l]、c[r+1]、c[r+2]三个值需要改变
维护c数组的0的个数，若没有非0的差分值，即说明二者相同
tips：这里为了避免下标越界的判断，把[1,n]挪到了[2,n+1]
心得 差分不止能维护相邻项差分QAQ
关注改变量与不变量，
可以将差分序列扩展成构造任意形如fib的递推式
代码 #includeusing namespace std;const int N=3e5+10;int n,q,v,mod,a[N],b[N],fib[N],l,r,zero;char s[5];void cal(int pos,int v){ zero-=(b[pos]!=0); b[pos]=(b[pos]+v)%mod; zero+=(b[pos]!=0);}int main(){ scanf("%d%d%d",&n,&q,&mod); fib[1]=1; for(int i=2;i<=n+1;++i){ fib[i]=(fib[i-1]+fib[i-2])%mod; scanf("%d",&a[i]); } for(int i=2;i<=n+1;++i){ scanf("%d",&v); a[i]=(a[i]-v)%mod; b[i]=((a[i]-a[i-1])%mod-a[i-2])%mod; zero+=(b[i]!=0); } for(int i=n+2;i<=n+3;++i){ b[i]=((a[i]-a[i-1])%mod-a[i-2])%mod; zero+=(b[i]!=0); } while(q--){ scanf("%s%d%d",s,&l,&r); l++;r++; int sg=(s[0]=='A'?1:-1); cal(l,sg); cal(r+1,-sg*(fib[r-l]+fib[r-l+1])%mod); cal(r+2,-sg*fib[r-l+1]); puts(!zero?"YES":"NO"); } return 0;}