CF446C DZY 喜欢斐波那契数字

文章CF446C DZY Loves Fibonacci Numbers，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

CF446C DZY Loves Fibonacci Numbers

题目大意

分析

首先看到区间查询，区间修改，考虑用线段树。

但是，我们看到区间修改这个操作，如果真的去暴力写，则时间一定T，因为没办法加懒标记，每次加的都不同。

我们是要求和，这里有两个性质。

设a数组符合Fibonacci数列的递推式，其中\(a_1,a_2\)为任意值

其有\(a_i=f_{i-1}*a_2+f{i-2}*a_1\)，以及\(\sum_{i=1}^{n}a_i=f_n*a_1+(f_{n+1}-1)*a_2\)

依据这两个性质，我们直接维护两个懒标记f1，f2。其分别表示，该区间的待下传的f_1，f_2是多少。

Ac_code

#include#define ios ios::sync_with_stdio(false); cin.tie(0), cout.tie(0)using namespace std;typedef long long LL;const int N = 3e5 + 10,mod = 1e9 + 9;struct Node{    int l,r;    LL v,f1,f2;}tr[N<<2];int n,m;LL f[N],a[N];void pushup(int u){    tr[u].v = (tr[u<<1].v + tr[u<<1|1].v)%mod;}void build(int u,int l,int r){    if(l==r)    {        tr[u] = {l,r,a[l]};        return ;    }    tr[u] = {l,r};    int mid = l + r >> 1;    build(u<<1,l,mid),build(u<<1|1,mid+1,r);    pushup(u);}void change(Node &u,int l,int r,LL f1,LL f2){    u.f1 += f1;u.f1 %= mod;    u.f2 += f2;u.f2 %= mod;    u.v += f2*(f[r-l+2]-1) + f1*f[r-l+1];u.v %= mod;}void pushdown(int k){    if(tr[k].f1||tr[k].f2)    {        int l = tr[k].l,r = tr[k].r;        int mid=(l+r)>>1;change(tr[k<<1],l,mid,tr[k].f1,tr[k].f2);int pos=mid-l+2;        LL t1 = (f[pos-1]*tr[k].f2+f[pos-2]*tr[k].f1)%mod;        LL t2 = (f[pos]*tr[k].f2+f[pos-1]*tr[k].f1)%mod;change(tr[k<<1|1],mid+1,r,t1,t2);tr[k].f1=0,tr[k].f2=0;    }}void modify(int u,int l,int r){    if(l<=tr[u].l&&tr[u].r<=r)    {        int L = tr[u].l,R = tr[u].r;        change(tr[u],L,R,f[L-l+1],f[L-l+2]);        return ;    }    pushdown(u);    int mid = tr[u].l + tr[u].r >> 1;    if(l<=mid) modify(u<<1,l,r);    if(r>mid) modify(u<<1|1,l,r);    pushup(u);}LL query(int u,int l,int r){    if(l<=tr[u].l&&tr[u].r<=r) return tr[u].v;    pushdown(u);    int mid = tr[u].l + tr[u].r >> 1;    LL res = 0;    if(l<=mid) res = (1ll*res + query(u<<1,l,r))%mod;    if(r>mid) res = (1ll*res + query(u<<1|1,l,r))%mod;    return res;}int main(){    ios;        cin>>n>>m;    f[1] = f[2] = 1;    for(int i=3;i<=n+1;i++) f[i] = (f[i-1] + f[i-2])%mod;    for(int i=1;i<=n;i++) cin>>a[i];    build(1,1,n);    while(m--)    {        int op,l,r;cin>>op>>l>>r;        if(op==1) modify(1,l,r);        else cout<