Statement:
给出两个长度为 \(n\) 的序列 \(a,b\)，每次在 \(a\) 或 \(b\) 上 \([l,r]\) 操作，一次操作将会使 \([l,r]\) 中的数分别加上 \(fib[1],fib[2]...,fib[r - l + 1]\)，每次操作完询问 \(a,b\) 是否在模 \(mod\) 意义下相等。
Solution:
先简化问题，令 \(c_i = a_i -b_i\)，问题转化为每次操作完，\(c_i\) 是否全 \(0\).
其实这个问题可以直接上线段树解决。
但是我们考虑将区间操作转化为单点操作，有什么技巧可以实现呢？ 差分！
差分的本质，其实是因为相邻项的增量有一定关系，根据关系设计出一个递推式，并且将区间转化为几个点的调整。
我们的增量 \(del\) 数组有这样的关系：\(del[i] = del[i - 1] + del[i - 2]\)。移项得到 \(del[i] - del[i - 1] - del[i - 2] = 0\)，于是 \(del[i] - del[i - 1] - del[i - 2]\) 其实就是不变量。
于是我们设计差分数组 \(d[i] = c[i] - c[i - 1] - c[i - 2]\)。
分析操作带来的影响（这里分析 \(A\) 数组）：
首先对于 \(d_l\) 显然需要 \(+f[1]\)，\(d_{r+1}\) 因为 \(c_{r+1}\) 不变，所以 \(-f_{r-l + 2}\)，\(d_{r+2}\) 同时也要 \(-f_{r - l + 1}\).
Code:
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 1145;
int n, q, mod, a[N], b[N], c[N], d[N], f[N], cnt;
void ch(int x, int ad){
if(x > n || x < 1) return;
int tmp = (d[x] + (ad % mod + mod) % mod) % mod;
if(d[x] == 0 && tmp) cnt--;
else if(d[x] != 0 && (!tmp)) cnt++;
d[x] = tmp;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> q >> mod;
for(int i = 1; i <= n; i++) cin >> a[i];
for(int i = 1; i <= n; i++) cin >> b[i];
f[1] = f[2] = 1;
for(int i = 3; i <= n + 114; i++) f[i] = (f[i - 1] + f[i - 2]) % mod;
for(int i = 1; i <= n; i++) c[i] = (a[i] - b[i] + mod) % mod, d[i] = ((c[i] - c[i - 1] - c[max(0ll, i - 2)]) + mod) % mod, ch(i, 0), cnt += (d[i] == 0);
while(q--){
char c; int l, r; cin >> c >> l >> r;
if(c == 'A'){
ch(l, f[1]); ch(r + 1, -f[r - l + 2]); ch(r + 2, -f[r - l + 1]);
}
else{
ch(l, -f[1]); ch(r + 1, f[r - l + 2]); ch(r + 2, f[r - l + 1]);
}
if(cnt == n) cout << "YES" << "\n";
else cout << "No" << "\n";
}
return 0;
}
/*
c[i] = a[i] - b[i]
d[i] = c[i] - c[i - 1] - c[i - 2]
*/