题目描述
难度分:2700
定义斐波那契序列f[1]=1，f[2]=1，f[i]=f[i−1]+f[i−2](i≥3)
定义数组x的斐波那契区间加表示指定x的一个连续子数组[l,r]，把x[l]加上f[1]，x[l+1]加上f[2]，…x[r]加上f[r−l+1]。
输入n，q(1≤n,q≤3×105)，mod(1≤mod≤109+7)和长为n的数组a和b，元素范围[0,mod−1]，下标从1开始。
然后输入q个操作，每个操作输入一个字符 (A或B) 和两个数l和r(1≤l≤r≤n)。
A表示操作对象是数组a，B表示操作对象是数组b，对这个数组的连续子数组[l,r]执行斐波那契区间加操作，这个操作是永久的。
每次操作后，如果每个a[i]和b[i]都模mod同余，也就是(a[i]−b[i])%mod=0，则输出YES，否则输出NO。
输入样例1
3 5 3
2 2 1
0 0 0
A 1 3
A 1 3
B 1 1
B 2 2
A 3 3
输出样例1
YES
NO
NO
NO
YES
输入样例2
5 3 10
2 5 0 3 5
3 5 8 2 5
B 2 3
B 3 4
A 1 2
输出样例2
NO
NO
YES
算法
差分数组
定义c[i]=a[i]−b[i]，问题转换成是否满足每个c[i]%mod=0都成立。
由于f[i]−f[i−1]−f[i−2]=0，类比差分数组，可以定义（初始化）
d[1]=c[1]
d[2]=c[2]−c[1]
d[i]=c[i]−c[i−1]−c[i−2](i≥3)
例如对[1,5]执行斐波那契区间加，相当于
d[1]+=f[1]=1
d[2]+=f[2]−f[1]=0
d[3]+=f[3]−f[2]−f[1]=0
d[4]+=f[4]−f[3]−f[2]=0
d[5]+=f[5]−f[4]−f[3]=0
d[6]+=0−f[5]−f[4]=−f[6]
d[7]+=0−0−f[5]=−f[5]
一般地，对[l,r]执行斐波那契区间加，相当于
d[l]+=1
d[r+1]−=f[r−l+2]
d[r+2]−=f[r−l+1]
对[l,r]执行斐波那契区间减，相当于
d[l]−=1
d[r+1]+=f[r−l+2]
d[r+2]+=f[r−l+1]
由于c数组模mod均为 0，当且仅当d数组模mod均为 0，所以只需要维护d数组及其0的个数。如果0的个数等于n，则输出YES，否则输出NO。
复杂度分析
时间复杂度
预处理出差分数组d和斐波那契数列f的时间复杂度为O(n)，处理每条询问的时间复杂度为O(1)，因此算法整体的时间复杂度为O(n+q)。
空间复杂度
除开输入数据所消耗的空间，额外开辟的空间为差分数组d所占用的内存，它的规模是O(n)的，因此额外空间复杂度为O(n)。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 300010;
int n, q, mod, a, b, c[N], f[N], d[N];
int main() {
scanf("%d%d%d", &n, &q, &mod);
for(int i = 1; i <= n; i++) {
if(i <= 2) {
f[i] = 1;
}else {
f[i] = (f[i - 1] + f[i - 2]) % mod;
}
scanf("%d", &a);
c[i] = (c[i] + a) % mod;
}
for(int i = 1; i <= n; i++) {
scanf("%d", &b);
c[i] = (c[i] - b + mod)%mod;
}
// 求c的差分数组
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(i == 1) {
d[i] = c[i];
}else if(i == 2) {
d[i] = (c[i] - c[i - 1] + mod) % mod;
}else {
d[i] = ((c[i] - c[i - 1] + mod) % mod - c[i - 2] + mod) % mod;
}
if(!d[i]) cnt++;
}
function<void(int, int)> update = [&](int index, long long val) {
if(index > n) return;
int pre = d[index];
int cur = (d[index] + val + mod)%mod;
d[index] = cur;
if(pre == 0 && cur != 0) cnt--;
if(pre != 0 && cur == 0) cnt++;
};
while(q--) {
char op[5];
scanf("%s", op);
int l, r;
scanf("%d%d", &l, &r);
if(op[0] == 'A') {
update(l, 1);
update(r + 1, -f[r - l + 2]);
update(r + 2, -f[r - l + 1]);
}else {
update(l, -1);
update(r + 1, f[r - l + 2]);
update(r + 2, f[r - l + 1]);
}
if(cnt == n) puts("YES");
else puts("NO");
}
return 0;
}
