P5309 初始化

题面

原题链接 click

题解

从计算贡献的角度考虑。
首先，对 \(A_i\) 求解前缀和来处理 \(A_i\) 初值对各个询问的影响。
其次，取合适的阈值 \(k\)，对于 \(x>k\) 的修改，直接处理即可。
然后，考虑 \(x\le k\) 的情形，枚举所有 \(x\)，注意到固定 \(x\) 时只有 \(x\) 种可能的 \(y\)，发现对于 \(x,y\) 均相同的修改可以合并，于是对于每一个 \(y\)，记录下 \((x,y)\) 对应的所有 \(z\) 的和，记作 \(t_y\)，求答案时就是一段 \(t_y\) 的后缀和，加上若干个 \(t_y\) 的总和，再加上一个 \(t_y\) 的前缀和，实时维护 \(t\) 数组的前缀和即可。
我们认为 \(n,q\) 同阶，总复杂度 \(O(nk+\frac{n^2}k)\)，取 \(k\sim\Theta \sqrt n\) 可得 \(O(n\sqrt n)\)。
由于常数原因，\(k\) 会略小于 \(\sqrt n\)。

Code

#include<bits/stdc++.h>
using namespace std;
const int lim=100,p=1000000007;
int a[200005],sum[200005];
int n,q;
int tp[200005],x[200005],y[200005],z[200005];
int d[200005],e[505];
inline void add(int u,int v){
    d[u]=(d[u]+v)%p; e[u>>9]=(e[u>>9]+v)%p;
}
int getsum(int l,int r){
    int res=0;
    for(int i=0;i<=(n>>9);i++){
        if(l>=(i+1<<9)) continue;
        if(r<(i<<9)) break;
        if(l<=(i<<9)&&(i+1<<9)-1<=r) res=(res+e[i])%p;
        else{
            for(int j=(i<<9);j<(i+1<<9);j++){
                if(j>=l&&j<=r) res=(res+d[j])%p;
            }
        }
    }
    return res;
}
int h[lim+5],h1[lim+5],h2[lim+5];
int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sum[i]=(sum[i-1]+a[i])%p;
    for(int i=1;i<=q;i++){
        cin>>tp[i]>>x[i]>>y[i];
        if(tp[i]==1) cin>>z[i];
    }
    for(int i=1;i<=q;i++){
        if(tp[i]==1&&x[i]>lim){
            for(int j=y[i];j<=n;j+=x[i]){
                add(j,z[i]);
            }
        }
        if(tp[i]==2){
            z[i]=((sum[y[i]]-sum[x[i]-1]+p)%p+getsum(x[i],y[i]))%p;
        }
    }
    for(int k=1;k<=lim;k++){
        memset(h,0,sizeof(h));
        memset(h1,0,sizeof(h1));
        memset(h2,0,sizeof(h2));
        for(int i=1;i<=q;i++){
            if(tp[i]==1&&x[i]==k){
                h[y[i]]+=z[i]; h[y[i]]%=p;
                for(int j=1;j<=y[i];j++){
                    h1[j]+=z[i]; h1[j]%=p;
                }
                for(int j=y[i];j<=x[i];j++){
                    h2[j]+=z[i]; h2[j]%=p;
                }
            }
            if(tp[i]==2){
                int d1=(x[i]-1)%k+1,d2=(y[i]-1)%k+1,e=((y[i]-d2)-(x[i]-d1))/k-1;
                z[i]+=1ll*e*h1[1]%p; z[i]%=p; z[i]+=p; z[i]%=p;
                z[i]+=h1[d1]; z[i]%=p;
                z[i]+=h2[d2]; z[i]%=p;
            }
        }
    }
    for(int i=1;i<=q;i++){
        if(tp[i]==2) cout<<z[i]<<'\n';
    }
    return 0;
}