【线段树维护区间加等比数列】Codeforces Round FF (Div. 2) E. DZY Loves Fibonacci Numbers
2021-08-22 20:45:00 # ACM

题链

题目解析

题目需要完成两个操作：
  $1.$ 区间加上一个斐波那契数列；
  $2.$ 查询区间和；

由于 $\sqrt{5}$ 在 $mod 1e9+9$ 下是有二次剩余的，所以斐波那契的通项公式：
$$F(n) = \frac{\sqrt{5}}{5}[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]$$
可以转变为：
$$F(n) = 276601605(691504013^n - 308495997^n) (mod 1e9+9)$$

于是题目操作变为区间加上两个等比数列，线段树维护；

如何维护

相同公比是有可加性的，例如：

A = {2,6,18,54}, 首项为 2，公比为 3；
B = {1,3,9,27}, 首项为 1，公比为 3；
将 A 与 B 相加，得到：
C = {3,9,27,81}, 首项为 3，公比为 3；

所以线段树维护节点区间对应的首项值，当然有几个公比就维护几棵线段树；
斐波那契通项公式中有两个公比 $Q[2] = {691504013,308495997}$，所以维护两棵线段树；

代码实现

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <bits/stdc++.h>
using namespace std;
	#define LL long long
    #define Pair pair<LL ,LL >
    #define ls rt<<1
    #define rs rt<<1|1
    #define PI acos(-1.0)
    #define eps 1e-13
    #define mod 1000000009
    #define MAXN 50001
    #define MS 300005

// f[n] = 276601605(691504013^n - 308495997^n) (mod 1e9+9)

int n,m;
LL Q[2] = {691504013, 308495997};
struct node{
	LL S[2];
	LL sum;
}p[MS<<2];
LL inv[2];
LL c[2][MS];

LL qpow(LL a,LL b){
	LL ans = 1;
	for(;b;b>>=1){
		if(b&1) ans = ans*a%mod;
		a = a*a%mod;
	}
	return ans;
}

void init(){
	inv[0] = qpow(1LL-Q[0],mod-2);
	inv[1] = qpow(1LL-Q[1],mod-2);
	for(int i=0;i<=n;i++) c[0][i] = qpow(Q[0],i);
	for(int i=0;i<=n;i++) c[1][i] = qpow(Q[1],i);
}

void push_up(int rt){
	p[rt].sum = (p[ls].sum + p[rs].sum)%mod;
}

void build(int l,int r,int rt){
	p[rt] = {0,0,0};
	if(l == r){
		cin >> p[rt].sum;
		return;
	}
	int m = l+r>>1;
	build(l,m,ls); build(m+1,r,rs);
	push_up(rt);
}

void update(int rt,int l,int r,LL valS,int Qid){
	int len = r-l+1;
	if(Qid == 0) p[rt].sum = (p[rt].sum + valS*(1LL-c[Qid][len])%mod *inv[Qid]%mod)%mod;
	else 		 p[rt].sum = (p[rt].sum - valS*(1LL-c[Qid][len])%mod *inv[Qid]%mod)%mod;
	p[rt].S[Qid] = (p[rt].S[Qid] + valS)%mod;
}

void push_down(int rt,int l,int r){
	for(int i=0;i<=1;i++){
		if(p[rt].S[i]){
			int m = l+r>>1;
			update(ls,l,m,p[rt].S[i],i);
			LL S = p[rt].S[i]*c[i][m+1-l]%mod;
			update(rs,m+1,r,S,i);
			p[rt].S[i] = 0;
		}
	}
}

void modify(int L,int R,int l,int r,int rt,LL valS,int Qid){
	if(L <= l && r <= R){
		LL S = valS*c[Qid][l-L]%mod;
		update(rt,l,r,S,Qid);
		return;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	if(m >= L) modify(L,R,l,m,ls,valS,Qid);
	if(m <  R) modify(L,R,m+1,r,rs,valS,Qid);
	push_up(rt);
}

LL query(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return (p[rt].sum%mod+mod)%mod;
	}
	int m = l+r>>1;
	push_down(rt,l,r);
	LL ans = 0;
	if(m >= L) ans = (ans + query(L,R,l,m,ls))%mod;
	if(m <  R) ans = (ans + query(L,R,m+1,r,rs))%mod;
	return ans;
}

void solve(){
	cin >> n >> m; init(); build(1,n,1);
	while(m--){
		int op,l,r; cin >> op >> l >> r;
		if(op == 1){
			modify(l,r,1,n,1,276601605LL*Q[0]%mod,0);
			modify(l,r,1,n,1,276601605LL*Q[1]%mod,1);
		} 
		else cout << query(l,r,1,n,1) << "\n";
	}
} 

int main() {
    ios::sync_with_stdio(false);
//	srand((unsigned)time(0));
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);
    int ce = 1;
//    cin >> ce;
//    scanf("%d",&ce);
    while(ce--) solve();
    
    return 0;
}
/*


*/

Prev
2021-08-22 20:45:00 # ACM
Next