Question

CF1921 F Sum of Progression

给定一个序列 \(\{a\}\) ，有 \(q\) 组询问，对于每组询问 \(s,d,k\)，求

Solution

\(s,d,k\) 其实就是在描述一个等差数列

考虑到 \(d\times k \le n\) 如果 \(d\) 很大，那么就意味着 \(k\) 很小，反之亦然

所以考虑根号分治，对于 \(d > \sqrt{n}\) 的直接处理

\(d \le \sqrt{n}\) 的情况预处理，然后用前缀和求和

具体这么使用前缀和求解答案

不妨先考虑 \(s=1,d=1\) 的情况

\(a_1\cdot 1+a_2 \cdot 2+ a_3 \cdot 3+\cdots+ a_n\cdot n\)

设 \(f[i]=\sum\limits_{j=1}^i a_i\times i\)

如果我们想要求 \(s=3,d=1,k=2\)

只需要用 \(f[5]-f[3-1]-\sum\limits_{i=3}^5 a_i\)

后面那一项可以再构造一个前缀和，设 \(s[i]=\sum\limits_{j=1}^i a[i]\)

那么 \(ans=f[5]-f[2]-(s[5]-s[2])\times 2\)

后面的 \(\times 2\) 其实就是把前面多乘的项减去

当 \(d\ne 1\) 的情况也类似

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

void print(LL x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}

LL sum[100005][305],tsum[100005][305];

void solve(){
    int n=read(),Q=read();
    int tot=0;
    vector<LL> a(n+1); 
    int block = min((int)sqrt(n),300);
    for(int i=1;i<=n;i++) a[i]=read();

    for(int d=1;d<=block;d++){
        for(int i=1;i<=d;i++){
            for(int j=i,cnt=1;j<=n;j+=d,cnt++){
                tot++;
                if(j-d > 0) tsum[j][d] = tsum[j-d][d] + a[j]*cnt, sum[j][d] = sum[j-d][d] + a[j];
                else tsum[j][d] = a[j]*cnt, sum[j][d] = a[j];
            }
        }
    }
    
    while(Q--){
        int s=read(),d=read(),k=read(); LL ans=0;
        if(d > block){
            for(int i=s,cnt=1;cnt<=k;i+=d,cnt++)
                ans += a[i]*cnt;
        }
        else{
            int st = s, ed = s+d*(k-1);
            int num = (st- 1) / d;
            ans = (tsum[ed][d] - tsum[max(st-d,0)][d]) - (sum[ed][d] - sum[max(st-d,0)][d]) * num;
        }
        print(ans);putchar(' ');
    }
    putchar('\n');
}

int main(){
    freopen("F.in","r",stdin);
    freopen("F1.out","w",stdout);
    int T=read();
    while(T--) solve();
    return 0;
}