引例：数列游戏（NKOJ3754）

给定一个长度为N的序列，首先进行A次操作，每次操作在Li和Ri这个区间加上一个数Ci。
然后有B次询问，每次询问Li到Ri的区间和。
初始序列都为0。

第一行三个整数N A B。(1<=N<=1000000,1<=A<=N,A<=B<=N)
接下来A行，每行三个数Li Ri Ci。(1<=Li<=N,Li<=Ri<=N,|Ci|<=100000000000000)。
接下来B行，每行两个数 Li Ri。范围同上。

对于每次询问，输出一行一个整数。
因为最后的结果可能很大，请对结果mod 1000000007。

很显然这道题用暴力要超时，光是修改操作就以O（n^2）。

这其实是一道线段树裸题，但我们可以用更简单的方法。

差分数组（差分序列）

对于一个数组A[i]，其差分数组D[i]=A[i]-A[i-1](i>0）且D[0]=A[0]

令SumD[i]=D[0]+D[1]+D[2]+...+D[i] (SumD[]是差分数组D[]的前缀和)

则SumD[i]=A[0]+A[1]-A[0]+A[2]-A[1]+A[3]-A[2]+...+A[i]-A[i-1]=A[i]。

即A[i]的差分数组是D[i]，而SumD[i]是A[i]。

对于刚才这道题：
如果每次修改都修改从L到R的值得话，一定会TLE。

注意特殊处：这道题是先进行整体区间修改，最后才统一查询。

所以，我们只需要维护一个差分数组。

对于将区间[L,R]加C，我们只需要将D[L]+C,D[R+1]-C。

附上代码：

#include<stdio.h>
using namespace std;
typedef long long ll;
const int N=2000005;
const ll mod=1000000007;
ll n,a,b;
ll D[N],SumA[N],SumD[N];
int main(){
    scanf("%lld%lld%lld",&n,&a,&b);
    for(int i=1;i<=a;i++){
        ll l,r,c;
        scanf("%lld%lld%lld",&l,&r,&c);
        D[l]=D[l]+c;
        D[r+1]=D[r+1]-c;
    }
    for(int i=1;i<=n;i++)
        SumD[i]=(D[i]+SumD[i-1]);
    for(int i=1;i<=n;i++)
        SumA[i]=(SumA[i-1]+SumD[i]);
    for(int i=1;i<=b;i++){
        ll l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",(SumA[r]%mod-SumA[l-1]%mod+mod)%mod);    
    }
    return 0;    
}

数列操作（NKOJ3786)

问题描述
给定一个长度为n的数列{a1,a2...an}，每次可以选择一个区间[l,r]，使这个区间内的数都加一或者都减一。
问至少需要多少次操作才能使数列中的所有数都一样,并求出在保证最少次数的前提下,最终得到的数列有多少种。

输入格式
第一行一个正整数n 
接下来n行,每行一个整数,第i+1行的整数表示ai。


输出格式
第一行输出最少操作次数
第二行输出最终能得到多少种结果

代码：

#include<stdio.h>
#include<algorithm>
using namespace std;
const int N=100005;
long long n,a[N],Sum1,Sum2,D[N];
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    for(int i=n;i>1;i--){
        D[i]=a[i]-a[i-1];
        if(D[i]>0)
            Sum1+=D[i];
        else
            Sum2+=abs(D[i]);
    }
    printf("%lld\n",max(abs(Sum1),abs(Sum2)));
    printf("%lld",abs(Sum1-Sum2)+1);
    return 0;    
}