知识点：差分
Link：https://codeforces.com/contest/1634/problem/F
差分的本质是递推。
简述
给定两长度为 \(n\) 的数列 \(a, b\)，模数 \(p\)，要求进行 \(q\) 次操作，每次操作为
c l r的形式，表示将数列 \(c\) 的区间 \([l, r]\) 上的第 \(i\) 项加上 \(\operatorname{fib}_i\)，\(\operatorname{fib}_i\) 表示 斐波那契数列的第 \(i\) 项。
要求在每次操作后判断 \(a, b\) 在模 \(p\) 意义下是否相同。
\(1\le n, q\le 3\times 10^5\)，\(1\le p\le 10^9 + 7\)，\(0\le a_i, b_i<p\)。
1S，256MB。
分析
好玩题。
先令 \(c_i = a_i - b_i\)，则仅需检查 \(c\) 是否全为 0。
发现这题带 \(\log\) 不好跑，又是区间修改，只得考虑差分。但是又要动态检查，这如何是好？
考虑差分的本质。我们可以将区间加 \([l, r]\) 转化为差分数组上的 \(d_l\) 加 \(d_r\) 减，是因为修改的增量 \(\operatorname{delta}\) 满足 \(\operatorname{delta}_i = \operatorname{delta}_{i - 1} (l < i \le r)\)，于是可以构建差分数组：\(d_1 = a_1\)，\(d_i = a_{i} - a_{i - 1}(i\ge 2)\)，则通过维护差分数组即可在修改完成后通过 \(a_i = a_{i - 1} + d_i\) 来递推出 \(a_i\)。
同理，区间加斐波那契数列也存在这样的递推关系：\(\operatorname{delta}_{i} = \operatorname{delta}_{i - 1} + \operatorname{delta}_{i - 2}(l + 1 <i \le r)\)，则考虑构建差分数组：\(d_1 = c_1\)，\(d_2 = c_2 - c_1\)，\(d_i = c_{i} - c_{i - 1} - c_{i - 2}(i\ge 3)\)，则区间加 \([l, r]\) 可转化为三次单点修改：\(d_{l}\leftarrow d_{l} + 1\)，\(d_{r + 1}\leftarrow d_{r + 1} + f_{r - l + 2}\)，\(d_{r + 2}\leftarrow d_{r + 1} + f_{r - l + 1}\)， 则同理有：\(c_{i} = c_{i - 1} + c_{i - 2} + d_i\)。
发现 \(c\) 全为 0 当且仅当差分数组 \(d\) 全为 0，于是在单点修改 \(d\) 的过程中维护 \(d\) 有多少个位置为 0 即可。
总时间复杂度 \(O(n + q)\) 级别，注意随时取模。
代码
//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 3e5 + 10;
//=============================================================
int n, q, num;
LL p, f[kN], c[kN], d[kN];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void Init() {
n = read(), q = read(), p = read();
f[1] = f[2] = 1;
for (int i = 3; i <= n; ++ i) f[i] = (f[i - 1] + f[i - 2]) % p;
for (int i = 1; i <= n; ++ i) c[i] = read() % p;
for (int i = 1; i <= n; ++ i) c[i] = (c[i] - read() % p + p) % p;
d[1] = c[1] % p, d[2] = (c[2] - c[1] + p) % p;
for (int i = 3; i <= n; ++ i) {
d[i] = (c[i] - c[i - 1] - c[i - 2] + 2 * p) % p;
}
for (int i = 1; i <= n; ++ i) num += (!d[i]);
}
void modify(int pos_, int val_) {
if (pos_ > n) return ;
num -= (!d[pos_]);
d[pos_] = (d[pos_] + val_ + p) % p;
num += (!d[pos_]);
}
//=============================================================
int main() {
// freopen("1.txt", "r", stdin);
Init();
while (q --) {
char s[5]; scanf("%s", s + 1);
int l = read(), r = read();
int type = ((s[1] == 'A') ? 1 : -1), ntype = ((s[1] == 'B') ? 1 : -1);
modify(l, type);
modify(r + 1, ntype * f[r - l + 1 + 1]);
modify(r + 2, ntype * f[r - l + 1]);
printf("%s\n", (num == n) ? "YES" : "NO");
}
return 0;
}