【题解】 CF718C Sasha and Array

以你之姓@ 2022-01-12 03:07 163阅读 0赞

\\(Description:\\)

> 设计一个数据结构，支持区间加，区间求斐波那契和，比如求\\(\\sum\_\{i=l\}^\{r\} f(a\_i)\\)

\\(Sample\\) \\(Input:\\)

> 5 4  
> 1 1 2 1 1  
> 2 1 5  
> 1 2 4 2  
> 2 2 4  
> 2 1 5

\\(Sample\\) \\(Output:\\)

> 5  
> 7  
> 9

考虑想段树上每个节点维护一个矩阵，因为矩阵满足结合律：  
\\(a\*c+b\*c=(a+b)\*c\\)

但由于幂运算不满足结合律，那么就不能直接在线段树的懒标记里面存幂次，要存一个矩阵，每次修改的时候乘一下。

但还有一个要考虑的：

如果普通斐波那契的话,矩阵快速幂的时候是原矩阵是\\(f\[n-1\],f\[n-2\]=>1,1\\)，但这里面如果原矩阵为这个就没办法询问到\\(f\[1\]\\)

其他的话只要注意下传懒标记之后吧懒标记变为单位矩阵就行了。

哦，还有要开long long

#include<bits/stdc++.h> #define int long long using namespace std; int n,m; const int N=1e5,p=1e9+7; int a[N+3]; struct matrix { int a[3][3]; inline void set (int x) { for(int i=1;i<=x;++i) a[i][i]=1;} inline void clear() { memset(a,0,sizeof(a));} inline bool operator != (const matrix &nt) const { for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) } inline matrix operator + (const matrix &nt) const { matrix tmp;tmp.clear(); for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) tmp.a[i][j]=(a[i][j]+nt.a[i][j])%p; return tmp; } inline matrix operator * (const matrix &nt) const { matrix tmp;tmp.clear(); for(int i=1;i<=2;++i) for(int j=1;j<=2;++j) for(int k=1;k<=2;++k) tmp.a[i][j]=(tmp.a[i][j]+a[i][k]*nt.a[k][j]%p)%p; return tmp; } inline matrix write () const { for(int i=1;i<=2;++i){ for(int j=1;j<=2;++j) printf("%lld ",a[i][j]); putchar('\n'); } return *this; } inline matrix operator *= (const matrix &nt) { return *this=*this*nt;} inline matrix operator += (const matrix &nt) { return *this=*this+nt;} }ori,oo,ff; inline matrix power(matrix a,int b){ matrix ret;ret.clear(); ret.set(2); while(b){ if(b&1) ret*=a; a*=a; b>>=1; } return ret; } struct node { int l,r; matrix v,tag; }tree[(N<<2)+2]; inline int lc(int k){return k<<1;} inline int rc(int k){return k<<1|1;} inline void push_up(int k){ tree[k].v=tree[lc(k)].v+tree[rc(k)].v;} inline void push_down(int k){ tree[lc(k)].v*=tree[k].tag; tree[rc(k)].v*=tree[k].tag; tree[lc(k)].tag*=tree[k].tag; tree[rc(k)].tag*=tree[k].tag; tree[k].tag.clear(); tree[k].tag.set(2); } inline void build(int k,int l,int r){ tree[k].l=l;tree[k].r=r; tree[k].tag.set(2); if(l==r){ tree[k].v=oo*power(ori,a[l]); return; } int mid=(l+r)>>1; build(lc(k),l,mid); build(rc(k),mid+1,r); push_up(k); } inline void update(int k,int l,int r,matrix x){ if(l<=tree[k].l && tree[k].r<=r){ tree[k].v*=x; tree[k].tag*=x; return; } int mid=(tree[k].l+tree[k].r)>>1; push_down(k); if(l<=mid) update(lc(k),l,r,x); if(r>mid) update(rc(k),l,r,x); push_up(k); } inline int query(int k,int l,int r){ if(l<=tree[k].l && tree[k].r<=r) return tree[k].v.a[1][1]%p; int mid=(tree[k].l+tree[k].r)>>1; push_down(k); int ret=0; if(l<=mid) ret=(ret+query(lc(k),l,r))%p; if(r>mid) ret=(ret+query(rc(k),l,r))%p; return ret; } signed main(){ freopen("1.out","w",stdout); ff.set(2); ori.a[1][1]=1; ori.a[1][2]=1; ori.a[2][1]=1; ori.a[2][2]=0; oo.a[1][1]=0; oo.a[1][2]=1; scanf("%lld%lld",&n,&m); for(int i=1;i<=n;++i) scanf("%lld",&a[i]); build(1,1,n); for(int i=1;i<=m;++i){ int opt=0; scanf("%lld",&opt); if(opt==1){ int l=0,r=0,x=0; scanf("%lld%lld%lld",&l,&r,&x); update(1,l,r,power(ori,x)); } if(opt==2){ int l=0,r=0; scanf("%lld%lld",&l,&r); printf("%lld\n",query(1,l,r)); } } return 0; }

转载于:https://www.cnblogs.com/JCNL666/p/10669796.html