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
|
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
#define mod 1000000007
#define getchar() (p1==p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;
using namespace std;
struct {
int a[3][3];
inline void init(){
a[1][1]=a[2][2]=1;a[1][2]=a[2][1]=0;
}
inline void init0(){
a[1][1]=a[2][2]=a[1][2]=a[2][1]=0;
}
inline void init1(){
a[1][1]=a[2][1]=a[1][2]=1;a[2][2]=0;
}
friend node operator + (node aa,node bb){
for(int i=1;i<=2;i++)
for(int j=1;j<=1;j++){
aa.a[i][j]=(aa.a[i][j]+bb.a[i][j]);
if (aa.a[i][j]>mod)aa.a[i][j]-=mod;
}
return aa;
}
friend node operator * (node a,node b){
node c;c.init0();
for (int i=1;i<=2;++i)
for (int k=1;k<=2;++k)
for (int j=1;j<=2;++j){
c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod;
if (c.a[i][j]>mod)c.a[i][j]-=mod;
}
return c;
}
friend node operator ^ (node a,int p){
node res;
res.init();
while(p){
if(p&1) res=res*a;
p>>=1;
a=a*a;
}
return res;
}
}f[100005],p,jz[500005],tag[500005];
inline int read(){
int x=0,w=0;char ch=getchar();
while (!isdigit(ch))w|=ch=='-',ch=getchar();
while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return w?-x:x;
}
template <class T>
inline void write(T x) {
if (x < 0) { putchar('-'); x = -x; }
T y = 10, len = 1;
while (y <= x) { y *= 10; ++len; }
while (len--) { y /= 10; putchar(x / y + 48); x %= y; }
}
inline bool check(node tag){
return tag.a[1][1]!=1||!tag.a[2][2]!=1||tag.a[1][2]!=0||tag.a[2][1]!=0;
}
inline void pushup(int k){
jz[k]=jz[ls(k)]+jz[rs(k)];
}
void build(int k,int l,int r){
tag[k].init();
if (l==r){
jz[k]=f[l];
return;
}
int mid=l+r>>1;
build(ls(k),l,mid);
build(rs(k),mid+1,r);
pushup(k);
}
inline void pushdown(int k){
node sq=tag[k];
jz[ls(k)]=sq*jz[ls(k)];
tag[ls(k)]=tag[ls(k)]*sq;
jz[rs(k)]=sq*jz[rs(k)];
tag[rs(k)]=tag[rs(k)]*sq;
tag[k].init();
}
void change(int k,int l,int r,int x,int y,node sq){
if (x<=l&&r<=y){
jz[k]=sq*jz[k];
tag[k]=tag[k]*sq;
return;
}
int mid=l+r>>1;
if (check(tag[k]))pushdown(k);
if (x<=mid)change(ls(k),l,mid,x,y,sq);
if (mid<y) change(rs(k),mid+1,r,x,y,sq);
pushup(k);
}
node query(int k,int l,int r,int x,int y){
if (x<=l&&r<=y)
return jz[k];
int mid=l+r>>1;
if (check(tag[k]))pushdown(k);
if (x<=mid&&mid<y)
return query(ls(k),l,mid,x,y)+query(rs(k),mid+1,r,x,y);
else if (x<=mid)return query(ls(k),l,mid,x,y);
else return query(rs(k),mid+1,r,x,y);
}
signed main(){
int n=read(),m=read();
p.init1();
node ttt;
ttt.a[1][1]=ttt.a[2][1]=1;
for (int i=1;i<=n;++i){
int x=read()-2;
if (x==-1)f[i].a[1][1]=1,f[i].a[2][1]=0;
else f[i]=(p^x)*ttt;
}
build(1,1,n);
while (m--){
int opt=read(),x=read(),y=read();
if (opt==1){
int d=read();
change(1,1,n,x,y,p^d);
}else{
node ans=query(1,1,n,x,y);
write(ans.a[1][1]);puts("");
}
}
return 0;
}
|
近期评论