Steven_MengのBlog

设$F$为斐波那契数列,不妨设$F_{-1}=1$
整个数列也就是$F_{-1}=1,F_{0}=0,F_{1}=1,F_{2}=1,F_{3}=2,F_{4}=3,F_{5}=5,F_{6}=8,….$

定义数列$S(0)=F_1a_1+F_2a_2+F_3a_3+…+F_na_n$,
定义数列$S(1)=F_2a_1+F_3a_2+F_4a_3+…+F_{n+1}a_n$
即:

发现:
$S(m+1)+S(m+2)=\sum_{i=1}^{i \le n} F_{i+m+1}a_i + \sum_{i=1}^{i \le n} F_{i+m+2}a_i=\sum_{i=1}^{i \le n} F_{i+m+3}a_i$
$=S(m+3)$

所以,$S$数列的递推关系的类似于斐波那契数列的递推关系。

现在,我们想只用$S(0)$和$S(1)$推出任意$S(m)$
不妨设$S(0)=A$,$S(1)=B$,发现

最后我们发现:$S(m)=F_{m-1} \times A+F_{m} \times B = F_{m-1} \times S(0)+F_{m} \times S(1)$,且$S(0),S(1)$是特殊情况需要加特判

考虑如何修改$S(0)$和$S(1)$,假设加上的数为c,发现:

所以,我们只要预处理$F$数组前缀和即可,修改$S(1)$也是同理。

考虑如何维护信息:
设当前要合并的两个区间分别为$[l_1,r_1][l_2,r_2]$
发现$S(0)=\sum_{i=l_1}^{i \le r_2} F_{i}a_i$
$=\sum_{i=l_1}^{i \le r_1}F_ia_i + \sum_{i=l_2+1}^{i \le r_2}F_ia_i$
$=S_l(0)+S_r(l_1-r_1+1)$
维护$S(1)$也是同理。

记得要开$\rm long$ $\rm long$并且疯狂取模。

具体要看代码(可能和思路在下标上有所不同)

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
#define MOD 1000000000
#define MAXN 200005
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^'0');
ch=getchar();
}
return x*f;
}
int a[MAXN],f[MAXN],pref[MAXN],pref2[MAXN];
inline void Init(){//预处理F数组和前缀和
f[1]=1,f[2]=2;
for (register int i=3;i<MAXN;++i){
f[i]=(f[i-1]+f[i-2])%MOD;
}
for (register int i=1;i<MAXN;++i){
pref2[i]=(pref2[i-1]+f[i])%MOD;
}

f[1]=1,f[2]=1;
for (register int i=3;i<MAXN;++i){
f[i]=(f[i-1]+f[i-2])%MOD;
}
for (register int i=1;i<MAXN;++i){
pref[i]=(pref[i-1]+f[i])%MOD;
}
}
namespace SegmentTree{
struct node{
int l,r;
int s0,s1;
int tag;
inline int len(){return r-l+1;}
}tree[MAXN<<2];
inline int Get_S(int x,int n){//求S(m)
if (n==1) return tree[x].s0;
if (n==2) return tree[x].s1;
return (tree[x].s0*f[n-2]%MOD+tree[x].s1*f[n-1]%MOD)%MOD;
}
#define lc i<<1
#define rc i<<1|1
inline void pushup(int i){
tree[i].s0=(tree[lc].s0+Get_S(rc,tree[lc].len()+1))%MOD;
tree[i].s1=(tree[lc].s1+Get_S(rc,tree[lc].len()+2))%MOD;
}
inline void Change(int i,int c){
int l=tree[i].len();
tree[i].s0=(tree[i].s0+pref[l]*c%MOD)%MOD;
tree[i].s1=(tree[i].s1+pref2[l]*c%MOD)%MOD;
}
inline void pushdown(int i){
if (tree[i].tag){
Change(lc,tree[i].tag);
Change(rc,tree[i].tag);
tree[lc].tag=(tree[lc].tag+tree[i].tag)%MOD;
tree[rc].tag=(tree[rc].tag+tree[i].tag)%MOD;
tree[i].tag=0;
}
}
void Build(int i,int l,int r){
tree[i].l=l,tree[i].r=r;
tree[i].tag=0;
if (l==r){
tree[i].s0=tree[i].s1=a[l];
return ;
}
int mid=(l+r)>>1;
Build(lc,l,mid);
Build(rc,mid+1,r);
pushup(i);
}
void Update(int i,int L,int R,int val){
if (L<=tree[i].l&&tree[i].r<=R){
tree[i].tag=(tree[i].tag+val)%MOD;
Change(i,val);
return ;
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>1;
if (L<=mid) Update(lc,L,R,val);
if (mid<R) Update(rc,L,R,val);
pushup(i);
}
void Update_Pos(int i,int index,int val){
if (tree[i].l==tree[i].r){
tree[i].s1=tree[i].s0=val;
return ;
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>1;
if (index<=mid) Update_Pos(lc,index,val);
else Update_Pos(rc,index,val);
pushup(i);
}
int Query(int i,int L,int R){
if (L<=tree[i].l&&tree[i].r<=R){
return Get_S(i,tree[i].l-L+1);
}
pushdown(i);
int mid=(tree[i].l+tree[i].r)>>1;
int ans=0;
if (L<=mid) ans=(ans+Query(lc,L,R))%MOD;
if (mid<R) ans=(ans+Query(rc,L,R))%MOD;
return ans;
}
}
using namespace SegmentTree;
#undef int
int main(){
#define int long long
Init();
int n=read(),m=read();
for (register int i=1;i<=n;++i){
a[i]=read();
}
Build(1,1,n);
for (register int i=1;i<=m;++i){
int opr=read();
if (opr==1){
int pos=read(),x=read();
Update_Pos(1,pos,x);
}
else if (opr==2){
int l=read(),r=read();
printf("%I64d\n",Query(1,l,r));
}
else if (opr==3){
int l=read(),r=read(),val=read();
Update(1,l,r,val);
}
}
}

 评论