题目大意：给你一个长度为n的数列an，有两种操作
1、将L到R的ai加上X
2、询问L到R之间，f(aL)+f(aL+1)+……+f(aR)的和
考虑维护fib数列的转移
区间加，就相当于区间乘上一个矩阵
那么我们直接维护矩阵的合并和懒标记下推就可以了
乘的矩阵要预处理一下不然会多一个log的复杂度
#include<map> #include<cmath> #include<queue> #include<vector> #include<cstdio> #include<string> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int N=2; const long long MOD=1000000007; struct Matrix { long long grid[N][N]; int row,col; Matrix():row(N),col(N) { memset(grid, 0, sizeof grid); } Matrix(int row, int col):row(row),col(col) { memset(grid, 0, sizeof grid); } Matrix operator *(const Matrix &b) { Matrix res(row, b.col); for(int i = 0; i<res.row; i++) for(int j = 0; j<res.col; j++) for(int k = 0;k<col; k++) res[i][j] = (res[i][j] + grid[i][k] * b.grid[k][j]) % MOD; return res; } Matrix operator ^(long long exp) { Matrix res(row, col); for(int i = 0; i < row; i++) res[i][i] = 1; Matrix temp = *this; for(; exp > 0; exp >>= 1, temp = temp * temp) if(exp & 1) res = temp * res; return res; } long long* operator[](int index) { return grid[index]; } void print() { for(int i = 0; i <row; i++) { for(int j = 0; j < col-1; j++) printf("%d ",grid[i][j]); printf("%d\n",grid[i][col-1]); } } }; struct tree { int l,r; long long x[2]; long long s[3][3]; }tr[800001]; inline long long cale(int d) { Matrix c(2,2); if(d<=2&&d>0) return 1; if(d==0) return 0; c[0][0]=0; c[0][1]=1; c[1][0]=1; c[1][1]=1; if(d>2) c=c^(d-2); return (c[0][1]+c[1][1])%MOD; } int a[100001]; inline void up(int p) { tr[p].x[0]=(tr[p*2].x[0]+tr[p*2+1].x[0])%MOD; tr[p].x[1]=(tr[p*2].x[1]+tr[p*2+1].x[1])%MOD; } inline void push(int p) { long long x0=tr[p*2].x[0],x1=tr[p*2].x[1]; tr[p*2].x[0]=(x0*tr[p].s[1][1]+x1*tr[p].s[2][1])%MOD; tr[p*2].x[1]=(x0*tr[p].s[1][2]+x1*tr[p].s[2][2])%MOD; x0=tr[p*2+1].x[0],x1=tr[p*2+1].x[1]; tr[p*2+1].x[0]=(x0*tr[p].s[1][1]+x1*tr[p].s[2][1])%MOD; tr[p*2+1].x[1]=(x0*tr[p].s[1][2]+x1*tr[p].s[2][2])%MOD; long long s11=tr[p*2].s[1][1],s12=tr[p*2].s[1][2],s21=tr[p*2].s[2][1],s22=tr[p*2].s[2][2]; tr[p*2].s[1][1]=(s11*tr[p].s[1][1]+s12*tr[p].s[2][1])%MOD; tr[p*2].s[1][2]=(s11*tr[p].s[1][2]+s12*tr[p].s[2][2])%MOD; tr[p*2].s[2][1]=(s21*tr[p].s[1][1]+s22*tr[p].s[2][1])%MOD; tr[p*2].s[2][2]=(s21*tr[p].s[1][2]+s22*tr[p].s[2][2])%MOD; s11=tr[p*2+1].s[1][1],s12=tr[p*2+1].s[1][2],s21=tr[p*2+1].s[2][1],s22=tr[p*2+1].s[2][2]; tr[p*2+1].s[1][1]=(s11*tr[p].s[1][1]+s12*tr[p].s[2][1])%MOD; tr[p*2+1].s[1][2]=(s11*tr[p].s[1][2]+s12*tr[p].s[2][2])%MOD; tr[p*2+1].s[2][1]=(s21*tr[p].s[1][1]+s22*tr[p].s[2][1])%MOD; tr[p*2+1].s[2][2]=(s21*tr[p].s[1][2]+s22*tr[p].s[2][2])%MOD; tr[p].s[1][1]=1; tr[p].s[1][2]=0; tr[p].s[2][1]=0; tr[p].s[2][2]=1; } inline void build(int p,int l,int r) { tr[p].l=l; tr[p].r=r; if(l!=r) { int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r); up(p); tr[p].s[1][1]=1; tr[p].s[1][2]=0; tr[p].s[2][1]=0; tr[p].s[2][2]=1; } else { tr[p].x[0]=cale(a[l]-1); tr[p].x[1]=cale(a[l]); tr[p].s[1][1]=1; tr[p].s[1][2]=0; tr[p].s[2][1]=0; tr[p].s[2][2]=1; } } inline long long query(int p,int l,int r) { if(l<=tr[p].l&&tr[p].r<=r) return tr[p].x[1]; else { push(p); int mid=(tr[p].l+tr[p].r)/2; long long ans=0; if(l<=mid) ans+=query(p*2,l,r); if(r>mid) ans+=query(p*2+1,l,r); ans=ans%MOD; return ans; } } Matrix c(2,2); long long xt[3][3]; inline void change(int p,int l,int r,int x) { if(l<=tr[p].l&&tr[p].r<=r) { // c.print(); long long x0=tr[p].x[0],x1=tr[p].x[1]; tr[p].x[0]=(x0*c[0][0]+x1*c[1][0])%MOD; tr[p].x[1]=(x0*c[0][1]+x1*c[1][1])%MOD; long long s11=tr[p].s[1][1],s12=tr[p].s[1][2],s21=tr[p].s[2][1],s22=tr[p].s[2][2]; tr[p].s[1][1]=(s11*c[0][0]+s12*c[1][0])%MOD; tr[p].s[1][2]=(s11*c[0][1]+s12*c[1][1])%MOD; tr[p].s[2][1]=(s21*c[0][0]+s22*c[1][0])%MOD; tr[p].s[2][2]=(s21*c[0][1]+s22*c[1][1])%MOD; } else { push(p); int mid=(tr[p].l+tr[p].r)/2; if(l<=mid) change(p*2,l,r,x); if(r>mid) change(p*2+1,l,r,x); up(p); } } int main() { int n,m; scanf("%d%d",&n,&m); int i; for(i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); int x,s,t; for(i=1;i<=m;i++) { scanf("%d",&x); if(x==2) { scanf("%d%d",&s,&t); printf("%I64d\n",query(1,s,t)); } else { scanf("%d%d%d",&s,&t,&x); c[0][0]=0; c[0][1]=1; c[1][0]=1; c[1][1]=1; c=c^x; change(1,s,t,x); } } return 0; }
