代码源OJ #562. 蜗蜗的数列、CF1634 F. Fibonacci Additions；
参考；
思路
题目要求验证数列 A,B 是否相同，我们构造数列 C， Ci=Ai−Bi ，检验数列 C 是否全为 0 即可；
对于一般的差分来说，连续区间加上定值，只需要在区间首末加上和减去这个值即可，但是此题加上的是斐波那契数列，我们需要特殊构造；
构造差分数组 D， Di=Ci−Ci−1−Ci−2 。我们可以发现如果对 C 的 [l,r] 区间进行操作，只需要对 Dl+F1,Dr+1+Fr−l+2,Dr+2+Fr−l+1 ，其余项在这种构造方式下均被约去了；
更推广来说，对于类斐波那契数列，也可以通过类似的构造来降低时间复杂度
代码
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#pragma GCC optimize(2)
int n, q;
ll m;
int tmp;
ll c[1000006];
ll d[1000006];
int f[1000006];
int upd(int x, int y)
{
int tmp = 0;
if (x >= 1 && x <= n)
{
tmp -= (d[x] != 0);
d[x] = (d[x] + y + m) % m;
tmp += (d[x] != 0);
}
return tmp;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n >> q >> m;
for (int i = 1; i <= n; i++)
{
cin >> c[i];
}
for (int i = 1; i <= n; i++)
{
cin >> tmp;
c[i] -= tmp;
}
int unz = 0;
d[1] = c[1];
d[2] = (c[2] - c[1] + m) % m;
for (int i = 3; i <= n; i++)
{
d[i] = (c[i] - c[i - 1] - c[i - 2] + 6 * m) % m;
}
for (int i = 1; i <= n; i++)
{
if (d[i])
unz++;
}
f[1] = 1 % m;
f[2] = 1 % m;
for (int i = 3; i <= n + 2; i++)
{
f[i] = (f[i - 1] + f[i - 2]) % m;
}
char g;
int l, r;
while (q--)
{
cin >> g >> l >> r;
if (g == 'A')
{
unz += upd(l, 1);
unz += upd(r + 1, -f[r - l + 2]);
unz += upd(r + 2, -f[r - l + 1]);
}
else
{
unz += upd(l, -1);
unz += upd(r + 1, f[r - l + 2]);
unz += upd(r + 2, f[r - l + 1]);
}
if (!unz)
cout << "Yes\n";
else
cout << "No\n";
}
return 0;
}
|
ED
卡常是坏文明