noip2019集训测试赛（四）A.fibonacci

本文主要是介绍noip2019集训测试赛（四）A.fibonacci，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

给定一个长度为 N 的序列 A={a1,a2,…,an} .

M 次操作, 每次操作形如下面两种中的一种:

1 l r x 将 $a_l,a_{l+1},...,a_r$ 都加上 x ;

2 l r 求 $\sum_{i=l}^rf(a_i)\ mod\ (10^9+7)$

其中 $f_n$ 为斐波那契数列的第 n 项, 即

$\left \{ \begin{array}{ll} f_n=1\qquad\qquad\qquad \ \ n=1或n=2\\ f_n=f_{n-1}+f_{n-2}\qquad n>2 \end{array} \right.$

Input

第一行两个数 N,M .

第二行 N 个数 a1,a2,…,an .

接下来 M 行, 每行代表题目描述中的一种操作.

Output

对于每个询问, 输出一行, 表示答案.

Solution

这题是区间修改查询，一看就是线段树，但我们怎么处理序号加x呢？
众所周知，斐波那契数列可以用矩阵快速幂来搞。
所以，我们可以让线段树每一个节点储存一个表示 $f(a_i)$ 的矩阵，对于某个节点加x，只要用这个节点的矩阵乘上单位矩阵p的x次方。

那么问题来了，虽然可以处理单点，但区间怎么办？
其实对于一段区间，我们可以直接将矩阵每一位的值加起来再乘（即结合律），举个栗子：

$\quad\begin{bmatrix} f(2)&f(3) \\\\ 0&0 \end{bmatrix} \quad * \quad \begin{bmatrix} 0&1 \\\\ 1&1 \end{bmatrix} \quad+\quad\begin{bmatrix} f(4)&f(5) \\\\ 0&0 \end{bmatrix} \quad*\quad\begin{bmatrix} 0&1 \\\\ 1&1 \end{bmatrix}\quad$

$\begin{bmatrix} f(2)+f(4)&f(3)+f(5) \\\\ 0&0 \end{bmatrix}\quad*\quad\begin{bmatrix} 0&1 \\\\ 1&1 \end{bmatrix}$

$\begin{bmatrix} f(3)+f(5)&f(4)+f(6 ) \\\\ 0&0 \end{bmatrix}$

那么线段树统计区间直接将矩阵加起来就好啦。

因为常数较大，所以要适当卡常，而且应提前处理好每次加x乘的矩阵，保证复杂度。
但是似乎出题人预处理了2的幂，所以跑得比我快。

Code

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long s[400010];
bool islaz[400010];
struct node{long long a[3][3];node(){memset(a,0,sizeof(a));}
}pp,p,p1,tree[400010],laz[400010];
node func(node a,node b){node c;for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)for(int k=1;k<=2;k++)c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mod;return c;
}
void build(int id,int l,int r){if(l==r){p=pp;laz[id]=node();int x=s[l]-1;tree[id].a[1][2]=1;while(x>0){if(x%2==1) tree[id]=func(tree[id],p);p=func(p,p);x/=2;}return;}int mid=(l+r)>>1;build(id*2,l,mid);build(id*2+1,mid+1,r);for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)tree[id].a[i][j]=(tree[id*2].a[i][j]+tree[id*2+1].a[i][j])%mod;
}
void pushdown(int id){if(islaz[id]){islaz[id]=0;tree[id*2]=func(tree[id*2],laz[id]);tree[id*2+1]=func(tree[id*2+1],laz[id]);if(islaz[id*2]) laz[id*2]=func(laz[id*2],laz[id]);else laz[id*2]=laz[id],islaz[id*2]=1;if(islaz[id*2+1]) laz[id*2+1]=func(laz[id*2+1],laz[id]);else laz[id*2+1]=laz[id],islaz[id*2+1]=1;laz[id]=node();} 
}
void update(int id,int l,int r,int ul,int ur){if(ul<=l&&r<=ur){tree[id]=func(tree[id],p1);if(islaz[id]) laz[id]=func(laz[id],p1);else laz[id]=p1,islaz[id]=1;return;}pushdown(id);int mid=(l+r)>>1;if(ul<=mid) update(id*2,l,mid,ul,ur);if(ur>mid) update(id*2+1,mid+1,r,ul,ur);for(int i=1;i<=2;i++)for(int j=1;j<=2;j++)tree[id].a[i][j]=(tree[id*2].a[i][j]+tree[id*2+1].a[i][j])%mod;
}
int query(int id,int l,int r,int ql,int qr){if(ql<=l&&r<=qr) return tree[id].a[1][2]%mod; pushdown(id);int mid=(l+r)>>1,sum=0;if(ql<=mid) sum=(sum+0ll+query(id*2,l,mid,ql,qr)%mod)%mod;if(qr>mid) sum=(sum+0ll+query(id*2+1,mid+1,r,ql,qr)%mod)%mod;return sum; 
}
inline int read(){char c=getchar(); long long x=0,f=1;while(!isdigit(c) && c!='-') c=getchar();if(c=='-') { f=-1; c=getchar(); }while(isdigit(c)) { x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f;
}
int main(){int n,m,op,l,r,x;n=read(),m=read();for(int i=1;i<=n;i++)s[i]=read();pp.a[1][2]=pp.a[2][1]=pp.a[2][2]=1;build(1,1,n);for(int i=1;i<=m;i++){op=read(),l=read(),r=read();if(op==1){x=read();p1=pp;  p=pp;int x1=x-1;while(x1>0){if(x1%2==1) p1=func(p1,p);p=func(p,p);x1/=2;}update(1,1,n,l,r);}else printf("%d\n",query(1,1,n,l,r)); }
}