Codeforces Gym Hello 2015 B Troynacci Query(partial sum)

题目大意

定义函数 $f(x)$:给定 $f(1),f(2)$,当 $i > 2,f(i) = af(i - 2) + bf(i - 1) $ 。
现给定一个长度为 $n$ 的序列 $x_i$,一共有 $q$ 次操作。每次操作子序列 $[l,r]$,对于每个 $x_i(l \le i \le r)$, 增加 $f(i-l+1)$。求最终序列。
$(1 \le n, q \le 10^5, 1 \le f(1),f(2),a,b \le 10^9,0 \le x_i \le 10^9)$

解题思路

Partial sum

考虑问题的简化版本,同样给定一个长度为 $n$ 的序列,同样有 $q$ 次操作,只不过每次操作对于每个 $x_i(l \le i \le r)$, 增加的是一个定值 $v$。

假设数据范围是一样的,这时要怎么求解呢?

可能有些人会想到用线段树或者RMQ,复杂度为 $O(nlogn)$。然而实际上这种题目有更快的称为 partial sum 的 $O(n)$ 解法(如下):

维护一个新的数组 $p_1, p_2,…, p_n$,一开始初始化为 $0$,然后对于每次操作 $[l,r]$,使 $p[l]$ 增加 $v$ ,使 $p[r + 1]$ 减少 $v$。所有操作结束后,对于每一个 $i$,从 $1$ 开始,使 $p[i] = p[i] + p[i - 1]$ 。那么最终答案序列就是 $x_1 + p_1, x_2 + p_2, …, x_n + p_n$ 。

算法原理还是很容易理解的,这里就不再赘述了。

那么回到一开始的问题,此时对于 $[l,r]$ 增加的不再是一个定值 $v$。但是可以发现, $f(i)$ 是一个递推求解的函数。而且,对于 $p_i = f[a] + f[b] + f[c] + …$ ,满足 $p_{i+1} = f[a + 1] + f[b + 1] + f[c + 1] + … = ap_{i-1} + bp_{i}$ 。发现这个,问题就基本解决了,另外由于 $f(1),f(2)$ 本身并不满足递推式,需要特殊处理(细节请看代码:多多揣摩)。

解题代码

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
#include <bits/stdc++.h>

typedef long long ll;

const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;

int n, q;
ll a, b, x[MAXN], f[MAXN], s[MAXN];

void init()
{

memset(s, 0, sizeof(s));
for( int i = 3; i < MAXN; ++ i ) {
f[i] = (a * f[i - 2] + b * f[i - 1]) % MOD;
}
}
int main()
{

init();
while( std::cin >> n >> q ) {
std::cin >> f[1] >> f[2] >> a >> b;
init();
for( int i = 1; i <= n; ++ i ) std::cin >> x[i];
int l, r;
while( q-- ) {
std::cin >> l >> r;
(s[l] += f[1]) %= MOD;
if( r - l >= 1 ) {
(s[l + 1] += f[2]) %= MOD;
s[l + 1] = ((s[l + 1] - b * f[1]) % MOD + MOD) % MOD;
s[r + 1] = (s[r + 1] + MOD - f[r - l + 2]) % MOD;
s[r + 2] = ((s[r + 2] - a * f[r - l + 1]) % MOD + MOD) % MOD;
}
else {
s[r + 1] = ((s[r + 1] - b * f[1]) % MOD + MOD) % MOD;
s[r + 2] = ((s[r + 2] - a * f[1]) % MOD + MOD) % MOD;
}
}
for( int i = 1; i <= n; ++ i ) {
if( i >= 2 ) (s[i] += a * s[i - 2]) %= MOD;
(s[i] += b * s[i - 1]) %= MOD;
(x[i] += s[i]) %= MOD;
}
for( int i = 1; i <= n; ++ i ) {
std::cout << x[i] << " ";
}
std::cout << std::endl;
}
return 0;
}
如果您觉得这篇博文对您有所帮助,可以考虑请我吃颗糖哦!