题目大意
万老板希望在新的智能音乐播放设备IPOOD中，实现对波文件音质性能的评定。
离散的波文件被考虑为长度为$N$的整数序列：$A_1,A_2,\cdots,A_N$。所谓的音质性能检测，可以评定任何的一个区间范围$[L,R]$，其音质性能取决于下述评分：其中$F$是可归纳定义的数列，满足$F[1]=1$，$F[2]=2$且$F[k+2]=F[k+1]+aF[k]+b$对于任何$k\ge 1$成立。其中$a$和$b$为正整系数。
为了可以为用户提供更好的服务体验，并希望对给定的波文件进行修正优化。这一款设备中，还应该支持对波文件的修改。
对于给定的区间范围$[L,R]$，允许用户将$A[L]$至$A[R]$同时增加一，或同时减少一。
题目分析
说明，数据有保证$A[i]$严格大于总的修改次数$+2$，不只是$+1$，可以不用求第$0$项。
维护广义斐波拉契数列，一眼线段树套矩阵。
但具体怎么搞呢？%%%LZX2019写了一个$9\times9$的矩阵，关键是还比我跑得快。
下面我来讲讲我的$3\times3$的矩阵。
首先对于题目的$F$下标不同，拆成两个数列分别维护。
每个位置维护两个向量$\begin{pmatrix}F_1(i) & F_1(i-1) & 1\end{pmatrix}$，$\begin{pmatrix}F_2(i) & F_2(i-1) & 1\end{pmatrix}$，这里是行向量。
对于$+1$移位乘上转移矩阵即可：
$-1$移位可以求逆矩阵转移，逆矩阵可以初等行变换手算：
初始情况的矩阵可以通过快速幂计算。
注意原矩阵存在逆当且仅当$a$存在逆元，但$a$可能为$0$，此时便没有逆矩阵。
当$a=0$时，转移式变为$F[k+2]=F[k+1]+b$，可以构造出$2\times 2$的矩阵：
以及其逆矩阵：
修改的时候记录标记，然后标记下传，这些都很简单，现在考虑如何回答询问。
询问的式子即为：
定位到对应区间，写成向量形式即为：
其中$\cdot$是向量的点积。
若在表达式中加上对应的标记即为：
其中$\times$是矩阵乘法。
这样不好算，对其中左边的向量进行转置得到：
因此左边的向量变成了列向量，左边的标记矩阵也进行了转置，答案为上述结果矩阵的第一行第一列的值。
代码
洛谷太慢了，TLE，建议在vijos交。
稍微超了一点内存，使用动态开点线段树优化。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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
using namespace std;
typedef long long LL;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
const LL mod=1e9+7;
struct Matrix {
const static int n=3;
LL a[n][n];
Matrix(bool f=0) {
memset(a,0,sizeof(a));
for(int i=0; i<n; i++)a[i][i]=f;
}
LL* operator [] (const int x) {
return a[x];
}
Matrix T() {
Matrix c(n);
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)c[j][i]=a[i][j];
return c;
}
Matrix operator + (Matrix b) {
Matrix c;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)c[i][j]=a[i][j]+b[i][j]>=mod?a[i][j]+b[i][j]-mod:a[i][j]+b[i][j];
return c;
}
Matrix operator * (Matrix b) {
Matrix c;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++) {
for(int k=0; k<n; k++)c[i][j]+=a[i][k]*b[k][j];
c[i][j]%=mod;
}
return c;
}
Matrix operator ^ (LL k) {
Matrix a=*this,c(1);
for(; k; k>>=1,a=a*a)if(k&1)c=c*a;
return c;
}
} linc,rinc,ldec,rdec,lf,rf,null=Matrix(),e=Matrix(1);
LL Quick_Pow(LL a,LL b) {
LL sum=1;
for(; b; b>>=1,a=a*a%mod)if(b&1)sum=sum*a%mod;
return sum;
}
LL inv(LL x) {
return Quick_Pow(x,mod-2);
}
LL a,b,A[maxn];
void Build_Matrix() {
if(a) {
linc[0][0]=1,linc[0][1]=a,linc[0][2]=b,linc[1][0]=1,linc[2][2]=1;
ldec[0][1]=1,ldec[1][0]=inv(a),ldec[1][1]=mod-inv(a),ldec[1][2]=mod-b*inv(a)%mod,ldec[2][2]=1;
lf[0][0]=2,lf[1][0]=1,lf[2][0]=1;
} else {
linc[0][0]=1,linc[0][1]=b,linc[1][1]=1;
ldec[0][0]=1,ldec[0][1]=mod-b,ldec[1][1]=1;
lf[0][0]=2,lf[1][0]=1;
}
rinc=linc.T(),rdec=ldec.T(),rf=lf.T();
}
struct Segment_Tree {
struct Tree {
int ls,rs;
int left,right;
Matrix l,r,sum;
Tree(int l=0,int r=0):ls(0),rs(0),left(l),right(r),l(e),r(e),sum(e) {}
} tree[maxn<<1];
int size;
void build(int &index,int Left,int Right) {
if(!index)index=++size;
tree[index]=Tree(Left,Right);
if(Left==Right) {
tree[index].sum=(linc^(A[Left-1]+1-2))*lf*rf*(rinc^(A[Left+1]-1-2));
return;
}
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
push_up(index);
}
void push_up(int index) {
tree[index].sum=tree[ls].sum+tree[rs].sum;
}
void modify(int index,Matrix l,Matrix r) {
tree[index].sum=l*tree[index].sum*r;
tree[index].l=l*tree[index].l;
tree[index].r=tree[index].r*r;
}
void push_down(int index) {
modify(ls,tree[index].l,tree[index].r);
modify(rs,tree[index].l,tree[index].r);
tree[index].l=tree[index].r=e;
}
void modify(int index,int Left,int Right,Matrix l,Matrix r) {
if(Right<tree[index].left||Left>tree[index].right)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {
modify(index,l,r);
return;
}
push_down(index);
modify(ls,Left,Right,l,r);
modify(rs,Left,Right,l,r);
push_up(index);
}
Matrix query(int index,int Left,int Right) {
if(Right<tree[index].left||Left>tree[index].right)return null;
if(Left<=tree[index].left&&Right>=tree[index].right)return tree[index].sum;
push_down(index);
return query(ls,Left,Right)+query(rs,Left,Right);
}
} st;
int n,q,root;
int main() {
n=Get_Int();
q=Get_Int();
a=Get_Int();
b=Get_Int();
for(int i=1; i<=n; i++)A[i]=Get_Int();
Build_Matrix();
st.build(root,2,n-1);
while(q--) {
char opt=' ';
while(!isalpha(opt))opt=getchar();
int x=Get_Int(),y=Get_Int();
if(opt=='p')st.modify(1,x+1,y+1,linc,e),st.modify(1,x-1,y-1,e,rinc);
else if(opt=='m')st.modify(1,x+1,y+1,ldec,e),st.modify(1,x-1,y-1,e,rdec);
else printf("%lld\n",st.query(1,x+1,y-1)[0][0]);
}
return 0;
}
