[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers

这个题的官方题解简直玄学，根号5取模，然后转化成等比数列，服气。

还好评论区有人给了更简便的做法：广义斐波那契数列。任意两个广义斐波那契数列相加仍然是斐波那契数列，而且只要知道了前两项的和就可以知道任意一项的和和任意一项的开始的前缀和。比如若第一二项为a,b,那么手推几下就可以发现，fab[n]=af[n-2]+bf[n-1]，然后前缀和是fsum[n]=f[n+2]-f[2]（这个也很容易推出来，甚至奇数项偶数项分别的和都能推出来）,然后这时候就很简单了，对于每一个区间只需要保存其左端点处的a，b就可以了，把ab做成lazy tag就可以实现区间修改了。注意这时候pushdown的时候，对于右孩子要计算出来fibab到这个点是多大才可以。一如既往的，add操作需要在maintain里加单节点特判（我也不知道为什么但是已经习惯了）还有一点注意ta一定是+的第一个，tb一定是+的第二个。

准备再用等比数列方法做一遍吧，看看是怎么个操作。。今天写了一下等比数列的操作方法，感觉比原来的方法简单emmm

第一种方法
 

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<string>
#include<cctype>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<deque>
#include<bitset>
#include<limits>
//#include<unordered_map>
#define eps (1e-6)
using namespace std;
typedef long long LL;
const int maxn=3e5+100;
const int MOD=1e9+9;
const int INF=0x4f4f4f4f;
const int maxnode=1e6+5;

LL sum[maxn<<2],addv[maxn<<2],lb[maxn<<2],ta[maxn<<2],tb[maxn<<2];
LL fib[maxn];
LL getfib(LL a,LL b,int n){return n==1?a:a*fib[n-2]+b*fib[n-1];}
LL getsumfib(LL a,LL b,int n){return getfib(a,b,n+2)-getfib(a,b,2);}

void pushdown(int o,int l,int r)
{
    if(ta[o]||tb[o])
    {
        int len=2+((l+r)>>1)-l;
        ta[o<<1]=(ta[o<<1]+ta[o])%MOD;
        tb[o<<1]=(tb[o<<1]+tb[o])%MOD;
        ta[(o<<1)+1]=(ta[(o<<1)+1]+getfib(ta[o],tb[o],len))%MOD;
        tb[(o<<1)+1]=(tb[(o<<1)+1]+getfib(ta[o],tb[o],len+1))%MOD;
        ta[o]=tb[o]=0;
    }
}

void maintain(int o,int l,int r)
{
    if(r>l)
        sum[o]=(sum[o<<1]+sum[(o<<1)+1])%MOD;
    
    else
    {
        sum[o]=(sum[o]+ta[o])%MOD;
        ta[o]=tb[o]=0;
    }
    if(ta[o]||tb[o])
    {
        sum[o]=(sum[o]+getsumfib(ta[o],tb[o],r-l+1))%MOD;
    }
}

int  pl,pr,pos,v;
void change(int o,int l,int r)
{
    if(r==l)
        sum[o]=v;
    else
    {
        int mid=(l+r)>>1;
        if(pos<=mid)change(o<<1,l,mid);
        if(pos>mid)change((o<<1)+1,mid+1,r);
        sum[o]=sum[o<<1]+sum[(o<<1)+1];
    }
}
void update(int o,int l,int r)
{
    if(pl<=l&&r<=pr)
    {
        ta[o]=(ta[o]+fib[l-pl+1])%MOD;
        tb[o]=(tb[o]+fib[l-pl+2])%MOD;
    }
    else
    {
        pushdown(o,l,r);;
        int mid=(l+r)>>1;
        if(pl<=mid)update(o<<1,l,mid);else maintain(o<<1,l,mid);
        if(mid<pr)update((o<<1)+1,mid+1,r);else maintain((o<<1)+1,mid+1,r);
    }
    maintain(o,l,r);
}

int ql,qr,ans;
void query(int o,int l,int r)
{
    maintain(o,l,r);
    if(ql<=l&&r<=qr)
    {
        ans=(ans+sum[o])%MOD;
    }
    else
    {
        pushdown(o,l,r);
        int mid=(l+r)>>1;
        if(ql<=mid)query(o<<1,l,mid);else maintain(o<<1,l,mid);
        if(mid<qr)query((o<<1)+1,mid+1,r);else maintain((o<<1)+1,mid+1,r);

    }
}

void calF()
{
    fib[1]=fib[2]=1;
    for (int i=3;i<=300010;++i)
        fib[i]=(fib[i-1]+fib[i-2])%MOD;
}

int main()
{
    //freopen("1.txt","r",stdin);
    //freopen("2.txt","w",stdout);
    calF();
    int n,m,op,l,r;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&v);
        pos=i;
        change(1,1,n);
    }
    while(m--)
    {
        scanf("%d%d%d",&op,&l,&r);
        if(op&1)
        {
            pl=l,pr=r;
            update(1,1,n);
        }
        else
        {
            ql=l,qr=r;
            ans=0;
            query(1,1,n);
            printf("%d\n",(ans%MOD+MOD)%MOD);
        }
    }
    return 0;
}

第二种方法，转化为等比数列

#include<bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <math.h>
#define G 3 //998244353 的原根

using namespace std;

typedef long long ll;
const int mx=1e2+5; 
const int maxn=3e5+5;
const int mod=1e9+9;

const int a=691504013,b=308495997,c=276601605,ia=691504013,ib=308495997;

const double PI = acos(-1.0);


ll sum[maxn<<2],sa[maxn<<2],sb[maxn<<2],lazya[maxn<<2],lazyb[maxn<<2];
ll pa[maxn],pb[maxn];

void build(int o,int l,int r){
    if(l==r){
        scanf("%I64d",&sum[o]);
    }
    else{
        build(o<<1,l,(l+r)>>1);
        build(o<<1|1,((l+r)>>1)+1,r);
        sum[o]=sum[o<<1]+sum[o<<1|1];
    }
}

void pushdown(int o,int l,int r){
    int m=(l+r)>>1;
    if(lazya[o]){
        lazya[o<<1]=(lazya[o<<1]+lazya[o])%mod;//error2
        lazya[o<<1|1]=(lazya[o<<1|1]+lazya[o]*pa[m+1-l])%mod;
        lazya[o]=0;
    }
    if(lazyb[o]){
        lazyb[o<<1]=(lazyb[o<<1]+lazyb[o])%mod;
        lazyb[o<<1|1]=(lazyb[o<<1|1]+lazyb[o]*pb[m+1-l])%mod;
        lazyb[o]=0;
    }
}

void maintain(int o,int l,int r){
    if(l!=r){
        sum[o]=(sum[o<<1]+sum[o<<1|1])%mod;
        if(lazya[o]){
            sum[o]=(sum[o]+(lazya[o]*ia%mod)*(pa[r-l+1]-1))%mod;//error1
        }
        if(lazyb[o]){
            sum[o]=(sum[o]-(lazyb[o]*ib%mod)*(pb[r-l+1]-1))%mod;
        }
    }
    else{
        if(lazya[o]||lazyb[o]){
            sum[o]=(sum[o]+lazya[o]-lazyb[o])%mod;
            lazya[o]=lazyb[o]=0;
        }
    }
}

int pl,pr,x;
void update(int o,int l,int r){
    if(pl<=l&&r<=pr){
        lazya[o]=(lazya[o]+c*pa[l-pl+1])%mod;
        lazyb[o]=(lazyb[o]+c*pb[l-pl+1])%mod;
    }
    else{
        pushdown(o,l,r);
        int m=(l+r)>>1;
        if(pl<=m) update(o<<1,l,m);else maintain(o<<1,l,m);
        if(m<pr) update(o<<1|1,m+1,r);else maintain(o<<1|1,m+1,r);
    }
    maintain(o,l,r);
}

int ql,qr;
ll query(int o,int l,int r){
    maintain(o,l,r);
    if(ql<=l&&r<=qr){
        return sum[o];
    }
    else{
        int m=(l+r)>>1;
        pushdown(o,l,r);
        ll res=0;
        if(ql<=m) res=query(o<<1,l,m);else maintain(o<<1,l,m);
        if(m<qr) res+=query(o<<1|1,m+1,r);else maintain(o<<1|1,m+1,r);
        return res%mod;
    }
}

void pre(){
    pa[0]=pb[0]=1;
    for(int i=1;i<maxn;i++){
        pa[i]=pa[i-1]*a%mod;
        pb[i]=pb[i-1]*b%mod;
    }
}

int main()
{
    int n,m,op,u,v;
    pre();
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&op,&u,&v);
        if(op==1){
            pl=u,pr=v;
            update(1,1,n);
        }
        else{
            ql=u,qr=v;
            ll ans=query(1,1,n);
            printf("%I64d\n",(ans%mod+mod)%mod);
        }
    }
    return 0;
}