P1438 无聊的数列 题解（改）

· · 题解

前言

昨天刷掉了这道题，发现题解区里的题解都是一阶差分+线段树的做法，对于不会段更新和线段树的萌新十分的不友好，所以水一篇基于二阶差分和树状数组的题解。

正文

前置芝士

差分：差分数组 d_i=a_i-a_{i-1}

二阶差分：差分数组上的差分,二阶差分数组为 d2

二阶前缀和：前缀和数组上的前缀和

树状数组：基于前缀和和二进制的数据结构

题目大意

给定一个长度为 n 的数列 a，以及 m 个操作，操作分为增加操作和询问操作。增加操作要求在序列 a 中的区间 [l,r] 上加上一个首项为 K，公差为 D，长度为 r-l+1 的等差数列。询问操作求的是序列 a 的第 p 个元素的值。

二阶差分分析

询问操作很显然是求二阶差分数组的二阶前缀和，那增加操作呢？

首先，增加一个首项为 K，公差为 D 的等差数列，可以理解为增加一个首项为 K，公差为 0 的等差数列和增加一个首项为 0，公差为 D 的等差数列。

第一种情况：首项为 K，公差为 0（整体增加 K）

那么显然，可以得到，在这种情况下:

d_l=d_l+K d_{r+1}=d_{r+1}-K

再继续深入分析，可以得到

d2_l=d2_l+K d2_{l+1}=d2_{l+1}-K d2_{r+1}=d2_{r+1}-K d2_{r+2}=d2_{r+2}+K

第二种情况：首项为 0，公差为 D

一通操作猛如虎，得到

d_{l+1}=d_{l+1}+D$，$d_{l+2}=d_{l+2}+D$，...，$d_{l+r}=d_{l+r}+D d_{r+1}=d_{r+1}-(r-l) \times D

继续一通操作猛如虎，易得：

d2_{l+1}=d2_{l+1}+D d2_{r+1}=-(r-l+1) \times D d2_{r+2}=d2_{r+2}+(r-l) \times D

将这些东西加到一起，可以得到，对于整体增加一个首项为 K，公差为 D的等差数列

d2_l=d2_l+k d2_{l+1}=d2_{l+1}+D-K d2_{r+1}=d2_{r+1}-(r-l+1) \times D -K d2_{r+2}=d2_{r+2}+(r-l) \times D +K

真是amazing的结果啊，原来的段更新已经变成了若干个点更新。

至此，基于二阶差分的分析已经完了，接下来就是如何求二阶前缀和了。

二阶前缀和的分析

我们要分析如何求出 d2 的二阶前缀和，也就是 a 数组。 最暴力的解法是先求一遍前缀和再求一边前缀和，显然超时。

显然

a_k =\sum\limits_{j=1}^k \sum\limits_{i=1}^jd2_i =\sum\limits_{i=1}^k \sum\limits_{j=i}^kd2_i =\sum\limits_{i=1}^kd2_i \times(k-i+1) =(k+1) \times \sum\limits_{i=1}^kd2_i-\sum\limits_{i=1}^kd2_i \times i

经过一通数学变化后，我们发现，只需要维护 d2_i 的前缀和和 d2_i\times i 的前缀和即可，这里我们使用树状数组来维护。

代码

#include<bits/stdc++.h>
#define N 100009
using namespace std;
typedef long long ll;
ll n,m,a[N],d[N],bit1[N],bit2[N];
ll LSB(ll x){
    return x&(-x);
}
void add(ll x,ll delta){
    ll id=x;
    while(x<=n){
        bit1[x]+=delta;
        bit2[x]+=delta*id;
        x+=LSB(x);
    }
}
ll query(ll x){
    ll id=x,sum=0;
    while(x){
        sum+=(id+1)*bit1[x]-bit2[x];
        x-=LSB(x);
    }
    return sum;
}
void input(){
    scanf("%lld %lld",&n,&m);
    for(ll i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        d[i]=a[i]-a[i-1];
        add(i,d[i]-d[i-1]);
    }
}
void solve(){
    for(ll i=1;i<=m;i++){
        ll op;
        scanf("%lld",&op);
        if(op==1){
            ll l,r,K,D;
            scanf("%lld %lld %lld %lld",&l,&r,&K,&D);
            add(l,K); add(l+1,D-K); add(r+1,-(r-l+1)*D-K); add(r+2,K+(r-l)*D);
        }else{
            ll p;
            scanf("%lld",&p);
            printf("%lld\n",query(p));
        }
    }
}
int main(){
    input();
    solve();
    return 0;
}

关于一些别的东西

看过别的题解的肯定都知道，线段树+一阶差分需要进行越界特判，否则会 WA。那么为什么树状数组不用特判呢？因为 add 函数的循环条件已经把这个东西给特判掉了。

致谢

@lilong 是他对于本文中的公式进行了无偿地 \LaTeX 排版，十分感谢他的帮助 。

完结撒花！