Codeforces 718C - Sasha and Array

题意

维护一个数列，支持区间加，以及区间斐波那契数列数列求和，即${\sum }_{i=l}^{r}f(a_i)\backslash sum\_\{i=l\}^rf(a\_i)$。

解法

首先把$f(a_i)f(a\_i)$拆成矩阵的幂次形式：

然后用线段树维护右边的矩阵就好。

区间加$xx$就是区间的和直接乘，区间求和就直接求和即可。

预处理矩阵的幂次可以加快速度。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define LSON rt<<1
#define RSON rt<<1|1
#define DATA(x) a[x].data
#define SIGN(x) a[x].c
#define ADD(x) a[x].c
#define DEL(x) a[x].d
#define LSIDE(x) a[x].l
#define RSIDE(x) a[x].r
#define WIDTH(x) (RSIDE(x)-LSIDE(x)+1)
#define MAXN 100010
#define MOD 1000000007LL
using namespace std;
int n,m;
struct node{
    long long val[2][2];
    inline void clean(){
        for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)val[i][j]=(i==j);
    }
    friend node operator +(const node x,const node y){
        node ret;
        for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)ret.val[i][j]=(x.val[i][j]+y.val[i][j])%MOD;
        return ret;
    }
    friend node operator *(const node x,const node y){
        node ret;
        for(int i=0;i<=1;i++)for(int j=0;j<=1;j++){
            ret.val[i][j]=0;
            for(int k=0;k<=1;k++)ret.val[i][j]=(ret.val[i][j]+x.val[i][k]*y.val[k][j]%MOD)%MOD;
        }
        return ret;
    }
    friend bool operator ==(const node x,const node y){
        for(int i=0;i<=1;i++)for(int j=0;j<=1;j++)if(x.val[i][j]!=y.val[i][j])return false;
        return true;
    }
}null,one,power[35];
struct Segment_Tree{
    node data,c;
    int l,r;
}a[MAXN<<2];
inline long long read(){
    long long date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
long long mexp(long long a,long long b,long long c){
    long long s=1;
    while(b){
        if(b&1)s=s*a%c;
        a=a*a%c;
        b>>=1;
    }
    return s;
}
node pow(long long k){
    node s;
    s.clean();
    for(int i=0;k;i++,k>>=1)if(k&1)s=s*power[i];
    return s;
}
void build(){
    null.val[0][0]=null.val[0][1]=null.val[1][0]=null.val[1][1]=0;
    one.clean();
    power[0].val[0][0]=0;power[0].val[0][1]=power[0].val[1][0]=power[0].val[1][1]=1;
    for(int i=1;i<=32;i++)power[i]=power[i-1]*power[i-1];
}
inline void pushup(int rt){
    DATA(rt)=DATA(LSON)+DATA(RSON);
}
inline void pushdown(int rt){
    if(LSIDE(rt)==RSIDE(rt)||SIGN(rt)==one)return;
    SIGN(LSON)=SIGN(LSON)*SIGN(rt);
    DATA(LSON)=DATA(LSON)*SIGN(rt);
    SIGN(RSON)=SIGN(RSON)*SIGN(rt);
    DATA(RSON)=DATA(RSON)*SIGN(rt);
    SIGN(rt).clean();
}
void buildtree(int l,int r,int rt){
    LSIDE(rt)=l;RSIDE(rt)=r;SIGN(rt).clean();
    if(l==r){
        int k=read();
        if(k>1)DATA(rt)=pow(k-1);
        else DATA(rt).clean();
        return;
    }
    int mid=l+r>>1;
    buildtree(l,mid,LSON);
    buildtree(mid+1,r,RSON);
    pushup(rt);
}
void update(int l,int r,const node c,int rt){
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r){
        SIGN(rt)=SIGN(rt)*c;
        DATA(rt)=DATA(rt)*c;
        return;
    }
    pushdown(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)update(l,r,c,LSON);
    if(mid<r)update(l,r,c,RSON);
    pushup(rt);
}
node query(int l,int r,int rt){
    if(l<=LSIDE(rt)&&RSIDE(rt)<=r)return DATA(rt);
    node ans=null;
    pushdown(rt);
    int mid=LSIDE(rt)+RSIDE(rt)>>1;
    if(l<=mid)ans=ans+query(l,r,LSON);
    if(mid<r)ans=ans+query(l,r,RSON);
    return ans;
}
void work(){
    int f,x,l,r;
    while(m--){
        f=read();l=read();r=read();
        if(f==1){
            x=read();
            update(l,r,pow(x),1);
        }
        else if(f==2)printf("%lld\n",query(l,r,1).val[1][1]);
    }
}
void init(){
    n=read();m=read();
    build();
    buildtree(1,n,1);
}
int main(){
    init();
    work();
    return 0;
}