P4458题解

· · 题解

P4458 链上二次求和

前言

尽量做到一气呵成，会 sigma 的小学生都能看懂，因为真的就是线段树和推式子。

解题思路

记原链表为 a，一次前缀和 S_a 记为 S，二次前缀和 S_{S_a} 记为 SS。

&\sum\limits_{k=l}^{r}\sum\limits_{i=k}^{n}\sum\limits_{j=i-k+1}^{i}a_j \\&=\sum\limits_{k=l}^{r}\sum\limits_{i=k}^{n}S_i-S_{i-k} \\&=\sum\limits_{k=l}^{r}(\sum\limits_{i=k}^{n}S_i-\sum\limits_{j=0}^{n-k}S_j) \\&=\sum\limits_{k=l}^{r}(SS_n-SS_{k-1}-SS_{n-k}) \\&=(r-l+1)SS_n-\sum\limits_{k=l-1}^{r-1}SS_k-\sum\limits_{k=n-r}^{n-l}SS_k \end{aligned}

我们要维护 \sum\limits_{k=l}^{r}SS_k，支持区间修改。

当对 l\sim r 加上 \Delta 时，

对于 l\le i\le r 的 i，SS_i 加上 \frac{(i-l+1)(i-l+2)}{2}\times\Delta。

对于 r< i\le n 的 i，SS_i 加上 \frac{(r-l+1)(r-l+2)}{2}\times\Delta+(i-r)(r-l+1)\times\Delta。

最后一点，lazy 数组可以用三个数 la,lb,lc 三个数表示，代表 val[id] 需要加上 \sum\limits_ {i=l}^r{la\times i^2+lb\times i+lc}。

相信没有什么疑问了吧。

细节

  1. 可能出现 l>r。

  2. 除以 2 和 6 就算出 2 和 6 在 \pmod{1000000007} 下的逆元就行。

  3. 注意负数和各种奇怪的溢出。

  4. 不要写着写着忘了式子，坚定信念，也就一百多行。

代码部分

#include <bits/stdc++.h>
using namespace std;
void file(string str){
    freopen((str+".in").c_str(),"r",stdin);
    freopen((str+".out").c_str(),"w",stdout);
}
const int MAXN=200010;
const int mod=1e9+7,inv2=5e8+4,inv6=inv2/3;
int n,m,init[MAXN],s[MAXN],ss[MAXN];
int val[MAXN<<2],laa[MAXN<<2],lab[MAXN<<2],lac[MAXN<<2];
inline int ad(int a,int b){return (a+b)%mod;}
inline int add(int a,int b,int c=0,int d=0){return ad(ad(a,b),ad(c,d));}
inline int mu(int a,int b){return 1ll*a*b%mod;}
inline int mul(int a,int b,int c=1,int d=1){return mu(mu(a,b),mu(c,d));}
int p1sum(int a){return mul(a,a+1,inv2);}
int p2sum(int a){return mul(a,a+1,2*a+1,inv6);}
int p1sum(int a,int b){return p1sum(b)-p1sum(a-1);}
int p2sum(int a,int b){return p2sum(b)-p2sum(a-1);}
void ___(int &a){a%=mod;if(a<0)a+=mod;}
void pushup(int id){val[id]=add(val[id<<1],val[id<<1|1]);}
void tag(int id,int l,int r,int la,int lb,int lc){
    val[id]=add(val[id],mul(la,p2sum(l,r)),mul(lb,p1sum(l,r)),mul(lc,r-l+1));
    ___(val[id]);laa[id]=add(laa[id],la);lab[id]=add(lab[id],lb);lac[id]=add(lac[id],lc);
}
void pushdown(int id,int l,int r){
    if(laa[id]||lab[id]||lac[id]){
        int mid=(l+r)>>1;
        tag(id<<1,l,mid,laa[id],lab[id],lac[id]);
        tag(id<<1|1,mid+1,r,laa[id],lab[id],lac[id]);
        laa[id]=lab[id]=lac[id]=0;
    }
}
void update(int id,int l,int r,int ql,int qr,int la,int lb,int lc){
    if(r<ql||l>qr)return;
    if(l>=ql&&r<=qr){tag(id,l,r,la,lb,lc);return;}
    int mid=(l+r)>>1;pushdown(id,l,r);
    update(id<<1,l,mid,ql,qr,la,lb,lc);
    update(id<<1|1,mid+1,r,ql,qr,la,lb,lc);
    pushup(id);
}
int query(int id,int l,int r,int ql,int qr){
    if(r<ql||l>qr)return 0;
    if(l>=ql&&r<=qr)return val[id];
    int mid=(l+r)>>1;pushdown(id,l,r);
    return add(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));
}
void build(int id,int l,int r){
    if(l==r){val[id]=ss[l];return;}
    int mid=(l+r)>>1;
    build(id<<1,l,mid);build(id<<1|1,mid+1,r);pushup(id);
}
void UPDATE(int l,int r,int d){
    int inv2_d=mul(inv2,d);
    update(1,1,n,l,r,inv2_d,mul((mod+3-2*l),inv2_d),mul(l-1,l-2,inv2_d));
    int tmp1=mul(p1sum(r-l+1),d),tmp2=mul(r-l+1,d);
    if(r<n)update(1,1,n,r+1,n,0,tmp2,tmp1-mul(tmp2,r));
}
int QUERY(int l,int r){
    int res=mul(r-l+1,query(1,1,n,n,n));
    res-=query(1,1,n,l-1,r-1);res-=query(1,1,n,n-r,n-l);
    ___(res);return res;
}
void initt(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&init[i]);
        s[i]=add(s[i-1],init[i]);ss[i]=add(ss[i-1],s[i]);
    }
    build(1,1,n);
}
int main(){
    initt();
    for(int i=1;i<=m;i++){
        int op,a,b,c;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1){scanf("%d",&c);if(a>b)swap(a,b);UPDATE(a,b,c);}
        else printf("%d\n",QUERY(a,b));
    }
    return 0;
}