[CF718C]Sasha and Array

718C:Sasha and Array

题意简述

维护一个长度为 n 的数列a，支持下面两个操作： 1. al 到 ar 加上 x 。 2.询问∑ri=lfib(ai)模 109+7 的值，其中 fib(x) 表示斐波那契数列的第 x 项 询问数m

数据范围

1≤n,m≤105 1≤ai,x≤109

思路

线段树维护斐波那契的转移矩阵。 我们的1操作就相当于是区间乘上这个矩阵。 因为矩阵满足乘法对加法的分配律。 所以父亲记录了两个孩子矩阵的和。 用一个矩阵当做标记，可以避免每次pushdown的时候都要计算一次快速幂，复杂度少一个log。 整体复杂度 O(23nlogn)

代码

#include<cstdio> #include<cstring> using namespace std; const int p=1000000007; struct Matrix{ int x,y; int d[2][2]; Matrix(){}; Matrix (int _x,int _y) { x=_x,y=_y; memset(d,0,sizeof(d)); } Matrix operator * (const Matrix &n1) { Matrix ret(x,n1.y); for (int i=0;i<x;i++) for (int j=0;j<y;j++) for (int k=0;k<n1.y;k++) ret.d[i][k]=(ret.d[i][k]+1LL*d[i][j]*n1.d[j][k])%p; return ret; } Matrix operator + (const Matrix &n1) { Matrix ret(x,y); for (int i=0;i<x;i++) for (int j=0;j<y;j++) ret.d[i][j]=(d[i][j]+n1.d[i][j])%p; return ret; } Matrix pow(int ff) { Matrix ret(x,y); ret.d[0][0]=ret.d[1][1]=1; Matrix sum=*this; while (ff) { if (ff&1) ret=ret*sum; sum=sum*sum; ff/=2; } return ret; } }base(2,2),tmp(2,2); int n,m,u,v,w,opt; int seq[100010]; namespace Segtree { struct Node{ Matrix data,add; void modify_add(Matrix &val) { add=add*val; data=data*val; } }; Node tree[400010]; void pushup(int node) { tree[node].data=tree[node<<1].data+tree[node<<1|1].data; } bool is_0(Matrix &val) { return (val.d[0][0]==1&&val.d[0][1]==0&&val.d[1][0]==0&&val.d[1][1]==1); } void pushdown(int node) { if (!is_0(tree[node].add)) { tree[node<<1].modify_add(tree[node].add); tree[node<<1|1].modify_add(tree[node].add); tree[node].add.d[0][0]=tree[node].add.d[1][1]=1; tree[node].add.d[0][1]=tree[node].add.d[1][0]=0; } } void build(int l,int r,int node) { tree[node].add=base.pow(0); if (l==r) { tree[node].data=base.pow(seq[l]-1); return; } int mid=(l+r)>>1; build(l,mid,node<<1); build(mid+1,r,node<<1|1); pushup(node); } void modify_add(int L,int R,int l,int r,int node,Matrix &val) { if (L<=l&&r<=R) { tree[node].modify_add(val); return; } pushdown(node); int mid=(l+r)>>1; if (L<=mid) modify_add(L,R,l,mid,node<<1,val); if (R>mid) modify_add(L,R,mid+1,r,node<<1|1,val); pushup(node); } int query(int L,int R,int l,int r,int node) { if (L<=l&&r<=R) return (tree[node].data.d[0][0]+tree[node].data.d[1][0])%p; pushdown(node); int ret=0; int mid=(l+r)>>1; if (L<=mid) ret=(ret+query(L,R,l,mid,node<<1))%p; if (R>mid) ret=(ret+query(L,R,mid+1,r,node<<1|1))%p; return ret; } } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) scanf("%d",&seq[i]); base.d[0][0]=0; base.d[1][1]=base.d[0][1]=base.d[1][0]=1; Segtree::build(1,n,1); tmp=base.pow(0); for (int i=1;i<=m;i++) { scanf("%d",&opt); if (opt==1) { scanf("%d%d%d",&u,&v,&w); tmp=base.pow(w); Segtree::modify_add(u,v,1,n,1,tmp); } if (opt==2) { scanf("%d%d",&u,&v); printf("%d\n",Segtree::query(u,v,1,n,1)); } } return 0; }