6th 【差分数组】数列游戏

数列游戏

【题目描述】：

给定一个长度为N的序列，初始序列都为0。

首先进行A次操作，每次操作在Li和Ri这个区间加上一个数Ci。

然后有B次询问，每次询问Li到Ri的区间和。

【输入描述】：

第一行三个整数N A B。(1<=N<=1000,000,1<=A,B<=N)

接下来A行，每行三个数Li Ri Ci。(1<=Li<=Ri<=N,|Ci|<=100,000,000,000,000)。

接下来B行，每行两个数 Li Ri。范围同上。

【输出描述】：

对于每次询问，输出一行一个整数。

因为最后的结果可能很大，请对结果mod 1000000007。

【样例输入】

5 1 1
1 3 1
1 4

【样例输出】

【数据范围及描述】：

输入输出量巨大，强烈建议使用手工输入输出

看到题目首先想到的是分块（因为太烦不想写），又想起zsz大神和lyc大神常常提及的线段树（然而我不会）

这就非常尴尬了。但上网查了一下看到了一个神奇的东西叫差分数组，顿时茅塞顿开。

用一个数组t[]来表示相邻两个数的差值,这样每次操作的时候，实际差值变化的只有一头一尾，
所以在l到r之间加上v，t[]是这样操作的：
t[l]=(t[l]+v);
t[r+1]=(t[r+1]-v);
那么我们求差值又有什么意义呢
突破点就在数组第一个数 t[0]=0
因为修改后的第一个数和0相差为t[1]，而修改前第一个数本身就是0。
所以修改后的第一个数可以写为t[0]+t[1];

所以可以还原数组了：t[i]=t[i-1]+t[i];
这样的话t[1]实际储存的就是修改后的第一个数的大小。
所以之后所有的都可以推出来 t[i]=t[i-1]+t[i];，前面一个数加上差值就是后一个数现在的大小。

在中间求一个和数组,为下面的查询做准备。
ans=s[r]-s[l-1] (从l到r的和)

所以这样就可以解决问题了。
注意每次要mod，另外好像写读入优化会快很多。我太菜了不会写-。-

# include <iostream>  
# include <cstring>  
# include <cstdio>  
# include <algorithm>  
const long long MOD = 1000000007;  
using namespace std;  
long long  t[1000001], s[1000001],v;  
int main()  
{  
        int n,x,y,l,r;  
        freopen("test1.in","r",stdin);
        freopen("test1.out","w",stdout);
        scanf("%d%d%d",&n,&x,&y);  
        while(x--)   //差分数组的处理 
        {  
            scanf("%d%d%lld",&l,&r,&v);  
            t[l]=(t[l]+v)%MOD;//最左端加上v 
            t[r+1]=(t[r+1]-v)%MOD; //最右端的右端减去一个v 
        }  
        for(int i=1;i<=n;i++)  
        {  
            t[i]=(t[i]+t[i-1])%MOD;//还原数组  t[i]记录修改后第i个数大小 
            s[i]=(s[i-1]+t[i])%MOD;//和数组 
        }  
        while(y--)  
        {  
            scanf("%d%d",&l,&r);  
            printf("%lld\n",((s[r]-s[l-1])%MOD+MOD)%MOD);//轻松完成每次询问！！！  
        }  
    return 0;  
}

秒客网