题目描述
https://codeforces.com/problemset/problem/1634/F
简要题意：给定两个长度为 $n$ 的数列 $a_i,b_i$，现在有 $m$ 个操作，每次操作给定一个区间 $[l,r]$ 以及将要操作的数列是 $a$ 还是 $b$，然后将区间内的数按顺序加上 $f_i$，其中 $f$ 是斐波那契数列，求每次操作后 $a$ 数列是否和 $b$ 数列完全相同
$n,m\le 3\times 10^5$
Solution
我们考虑差分，注意到 $a_{i+2}$ 所增加的数恰好为 $a_i$ 和 $a_{i+1}$ 所增加的数的和，那么我们构造一个这样的差分，令 $d_i=a_{i}-a_{i-1}-a_{i-2}$，那么这样一个区间加的操作，我们只需要修改 $a_{l},a_{l+1},a_{r+1},a_{r+2}$ 这四个位置即可
至于如何判断相等，我们只需要将其看做 $a-b$，然后维护 $0$ 的个数即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| #include <iostream>
#define maxn 300010
using namespace std;
int n, m, p, a[maxn], d[maxn], f[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> p; int num = 0;
f[1] = f[2] = 1; for (int i = 2; i <= n; ++i) f[i] = (f[i - 1] + f[i - 2]) % p;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1, x; i <= n; ++i) cin >> x, a[i] = (a[i] - x) % p;
d[1] = a[1]; d[2] = (a[2] - a[1]) % p;
for (int i = 3; i <= n; ++i) d[i] = (1ll * a[i] - a[i - 1] - a[i - 2]) % p;
for (int i = 1; i <= n; ++i) num += d[i] == 0;
for (int i = 1; i <= m; ++i) {
char s[3]; int x, y, z, opt; cin >> s >> x >> y;
opt = s[0] == 'A' ? 1 : -1;
num -= d[x] == 0; d[x] = (d[x] + opt) % p; num += d[x] == 0;
if (y + 1 <= n)
num -= d[y + 1] == 0, d[y + 1] = (d[y + 1] - opt * f[y - x + 2]) % p, num += d[y + 1] == 0;
if (y + 2 <= n)
num -= d[y + 2] == 0, d[y + 2] = (d[y + 2] - opt * f[y - x + 1]) % p, num += d[y + 2] == 0;
cout << (num == n ? "YES" : "NO") << "\n";
}
return 0;
}
|