zcmimi's blog
avatar
zc
2020-07-18 11:27:00
  • 本文总阅读量
查看原题

点击跳转

sa的前缀和,Ss的前缀和

\begin{aligned} ans &=\sum_{i=l}^r \sum_{j=i}^n s_j-s_{j-i}\\ &=\sum_{i=l}^r\left(\sum_{j=i}^n s_j-\sum_{j=i}^ns_{j-i}\right)\\ &=\sum_{i=l}^r\left(\sum_{j=1}^n s_j - \sum_{j=1}^{i-1} s_j -\sum_{j=0}^{n-i}s_j\right)\\ &=\sum_{i=l}^r ( S_n-S_{i-1}-S_{n-i})\\ \end{aligned}

线段树维护S即可,如何维护S?

假设[l,r]区间加v,

g_i=1+2+3+\dots+i=\frac{i(i+1)}2

假设i\in[l,r],那么S_i加上v\times g_{r-i+1}

假设i\in[r+1,n],那么S_i加上v\times g_{r-l+1} + v\times(i-r)(r-l+1)

#include<bits/stdc++.h>
int rd(){int x=0;char c;bool f=0;for(c=getchar();c<'0'||'9'<c;c=getchar())f^=c=='-';for(x=c-48,c=getchar();'0'<=c&&c<='9';x=x*10+c-48,c=getchar());return f?-x:x;}
const int N=200011,P=1000000007,i2=500000004;
int n,m,a[N],s[N<<2],la[N<<2],lb[N<<2],lc[N<<2],G[N],S[N];
#define ls rt<<1
#define rs rt<<1|1
void mod(int&x){if(x>=P)x-=P;}
void pu(int rt){mod(s[rt]=s[ls]+s[rs]);}
void add(int rt,int l,int r,int a,int b,int c){
    mod(la[rt]+=a),mod(lb[rt]+=b),mod(lc[rt]+=c);
    mod(s[rt]+=1ll*(S[r]-S[l-1]+P)%P*a%P);
    mod(s[rt]+=1ll*(G[r]-G[l-1]+P)%P*b%P);
    mod(s[rt]+=1ll*(r-l+1)*c%P);
}
void pd(int rt,int l,int r){
    int m=l+r>>1;
    if(la[rt]||lb[rt]||lc[rt])
        add(ls,l,m,la[rt],lb[rt],lc[rt]),
        add(rs,m+1,r,la[rt],lb[rt],lc[rt]),
        la[rt]=lb[rt]=lc[rt]=0;
}
void build(int l,int r,int rt){
    if(l==r){s[rt]=a[l];return;}
    int m=l+r>>1;
    build(l,m,ls),build(m+1,r,rs);
    pu(rt);
}
void upd(int L,int R,int a,int b,int c,int l=1,int r=n,int rt=1){
    if(L>r||R<l)return;
    if(L<=l&&r<=R){add(rt,l,r,a,b,c);return;}
    int m=l+r>>1;
    pd(rt,l,r);
    if(L<=m)upd(L,R,a,b,c,l,m,ls);
    if(R>m)upd(L,R,a,b,c,m+1,r,rs);
    pu(rt);
}
int ask(int L,int R,int l=1,int r=n,int rt=1){
    if(L>r||R<l)return 0;
    if(L<=l&&r<=R)return s[rt];
    int m=l+r>>1,res=0;
    pd(rt,l,r);
    if(L<=m)res=ask(L,R,l,m,ls);
    if(R>m)mod(res+=ask(L,R,m+1,r,rs));
    return res;
}
void mdy(int l,int r,int v){
    int a=1ll*v*i2%P;
    upd(l,r,
        a,
        1ll*a*(3-l*2+P)%P,
        (1ll*l*(l-3)+2)%P*a%P
    );
    if(r<n)upd(r+1,n,
        0,
        1ll*(r-l+1)*v%P,
        (G[r-l+1]-1ll*r*(r-l+1)%P+P)%P*v%P
    );
}
int qry(int l,int r){
    int res=1ll*(r-l+1)*ask(n,n)%P;
    mod(res+=P-ask(l-1,r-1));
    mod(res+=P-ask(n-r,n-l));
    return res;
}
int main(){
    n=rd(),m=rd();
    for(int i=1;i<=n;++i)mod(a[i]=a[i-1]+rd());
    for(int i=2;i<=n;++i)mod(a[i]+=a[i-1]);
    for(int i=1;i<=n;++i)
        mod(G[i]=G[i-1]+i),
        mod(S[i]=S[i-1]+1ll*i*i%P);
    build(1,n,1);
    while(m--){
        int opt=rd(),l=rd(),r=rd();
        if(l>r)l^=r,r^=l,l^=r;
        if(opt==1)mdy(l,r,rd());
        else printf("%d\n",qry(l,r));
    }
}
LG 4458 [BJOI2018]链上二次求和
comment评论
Search
search