题解：P13979 数列分块入门 4

· · 题解

题解：P13979 数列分块入门 4

题目传送门

题外话

真入门。

思路

显而易见，这道题并不可以暴力去模拟，因为 1 \le n\le 3 \times 10^5，我们需要去维护一个在线的数组，所以可以使用树状数组求解。但是该操作涉及区间加法，区间求和，所以我们可以使用差分的思路，可以得到如下结论：

\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}\sum_{j = 1}^{n}b_j

我们会发现 b_p 被计算过一次，b_{p-1} 计算过两次，以此类推，容易得到 b_1 就被计算过 p 次。所以不难推出下一步为：

\sum_{i = 1}^{n}a_i = \sum_{i = 1}^{n}b_i \times (n-i+1)

此时把 i 放进求和公式中即可得到最后的算是可以演变为：

\sum_{i = 1}^{n}a_i = (n+1)\times\sum_{i = 1}^{n}b_i -\sum_{i = 1}^{n}b_i \times i

所以我们只需要去维护 b_i 与 b_i \times i 即可。

notice

当取模时光一次加再取模不够的。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct PPT{
    int a[1150000];
    void up(int i,int p){
        while(i<1150000){
            a[i]+=p;
            i+=(i&-i);
        }
    }
    int down(int x){
        int p=0;
        while(x){
            p+=a[x];
            x-=(x&-x);
        }
        return p;
    }
} T,C;
signed main(){
    int n;
    cin>>n;
    int t=0;
    for(int i=1;i<=n;i++){
        int po;
        cin>>po;
        T.up(i,po-t);
        C.up(i,(i-1)*(po-t));
        t=po;
    }
    for(int i=0;i<n;i++){
        int a,b,c,d;
        cin>>a;
        if(a==0){
            cin>>b>>c>>d;
            T.up(b,d);
            T.up(c+1,-d);
            C.up(b,d*(b-1));
            C.up(c+1,-d*c);
        }   
        else{
            cin>>b>>c>>d;
            int s1=(b-1)*T.down(b-1)-C.down(b-1);
            int s2=c*T.down(c)-C.down(c);
            cout<<((s2-s1)+900000000*(d+1))%(d+1)<<endl;
        }
    }    
    return 0;
}