[平衡规划][模拟][前缀和] Jzoj P4724 斐波那契

Description

DJL为了避免成为一只咸鱼，来找czgj学习Fibonacci数列。
通过czgj的谆谆教导，DJL明白了Fibonacci数列是这样定义的：
F(1)=1;F(2)=1;F(n)=F(n-1)+F(n-2)(n>2)
Czgj深谙熟能生巧的道理，于是他给了DJL一个数列，并安排了如下的训练计划：
1、“1 L r”，表示给ai 加上F(i-L+1) ，其中L<=i<=r ；
2、“2 L r”，表示询问 的值。
DJL经过长时间的学习，感觉身体被掏空，他希望你能帮他解决这个问题。

 

Input

第一行两个整数n和m，表示原始数列的长度，和总的训练次数。
第二行n个整数a1,a2,...,an(1<=ai<=10^9) ，表示czgj给DJL的原始数列。
接下来m行，每一行给出三个整数，表示问题描述中的两种训练的一种。保证1<=L<=r<=n 。

Output

对于每一种形如“2 L r”的训练，输出一行一个整数值。

 

Sample Input

4 4
1 2 3 4
1 1 4
2 1 4
1 2 4
2 1 3

Sample Output

17
12
样例解释
经过第一次操作，数列变为a=[2,3,5,7] ；
第二次询问，sum=2+3+5+7=17 ；
经过第三次操作，数列变为a=[2,4,6,9] ；
第四次询问，sum=2+4+6=12 。

 

Data Constraint

对于20%的数据，1≤n, m≤100；
对于40%的数据，1≤n, m≤1000；
对于100%的数据，1≤n, m≤100000。

平衡规划

对于区间修改操作先不直接修改，每当储存到了√n个后，再进行重构。每次询问的话，先查询重构了的数组，再遍历储存下来的操作，然后再单独做，可以优化时间复杂度

题解

• 那么有了上面的思想，套用到这题目里
• 每次修改就是O(1)的，然后维护一个数组d
• 当一次区间[l,r]修改时
• d[l]=d[l]+1,d[r+1]=d[r+1]-f[r-l+2],d[r+2]=d[r+2]-f[r-l+1],d[i]=d[i]+d[i-1]+d[i-2]
• 然后重构a数组，并求出前缀和
• 最后时间复杂度就是O(m√n)

代码

#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
struct edge {int l,r;}e[100010];
int n,m,a[100010],cnt,feng;
long long sum[100010],k[100010],tot[100010],f[100010],ans,mo=1e9+9;
int main()
{
    scanf("%d%d",&n,&m); feng=sqrt(m);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]),sum[i]=(sum[i-1]+a[i])%mo;
    f[1]=tot[1]=1;
    for (int i=2;i<=n;i++) f[i]=(f[i-1]+f[i-2])%mo,tot[i]=(tot[i-1]+f[i])%mo;
    for (int j=1;j<=m;j++)
    {
        int d,l,r;
        scanf("%d%d%d",&d,&l,&r);
        if (d==1) e[++cnt].l=l,e[cnt].r=r; 
        else 
        {
            ans=0;
            for (int i=1;i<=cnt;i++)
            {
                int a=e[i].l,b=e[i].r;
                if (r<a||l>b) continue;
                ans=(ans+tot[min(b,r)-(a-1)]-tot[max(a,l)-a]+mo)%mo;
            }
            printf("%lld
",(ans+sum[r]-sum[l-1]+mo)%mo);
        }
        if (cnt==feng)
        {
            memset(k,0,sizeof(k));
            for (int i=1;i<=cnt;i++)
            {
                int l=e[i].l,r=e[i].r;
                k[l]=(k[l]+1)%mo;
                k[r+1]=(k[r+1]-f[r-l+2]+mo)%mo,k[r+2]=(k[r+2]-f[r-l+1]+mo)%mo;
            }
            cnt=0;
            for (int i=1;i<=n;i++)
            {
                k[i]=(k[i]+k[i-1]+k[i-2])%mo;
                a[i]=(a[i]+k[i])%mo;
                sum[i]=(sum[i-1]+a[i])%mo;
            }
        }
    }
}