F. Sum of Progression

?题面

输入
每个测试由几个测试用例组成。第一行包含一个整数 t（1 ≤ t ≤ 1e4）——测试用例的数量。接下来的几行包含测试用例的描述。
每个测试用例的第一行包含两个数字n，q（1 ≤ n ≤ 1e5，1 ≤ q ≤ 2e5）——数组a中的元素数量和查询数量。
第二行包含 n 个整数 a1，。。。an（?1e8 ≤ a1，…，an≤ 1e8）——数组a的元素。
接下来的q行分别包含三个整数s、d和k（1≤s，d，k≤n，s+d?（k?1）≤n）。
保证所有测试用例上的n之和不超过 1e5，并且所有测试用例的q之和不超出2e5。

输出
对于每个测试用例，在单独的一行中打印q个数字——用空格分隔的所需总和。

Input
5
3 3
1 1 2
1 2 2
2 2 1
1 1 2
3 1
-100000000 -100000000 -100000000
1 1 3
5 3
1 2 3 4 5
1 2 3
2 3 2
1 1 5
3 1
100000000 100000000 100000000
1 1 3
7 7
34 87 5 42 -44 66 -32
2 2 2
4 3 1
1 3 2
6 2 1
5 2 2
2 5 2
6 1 2

Output
5 1 3?
-600000000?
22 12 55?

?具体解析见?http://t.csdnimg.cn/CM96P，讲得很好！

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const double PI=acos(-1.0);
const int N=1e5+10,F=300; //F 界限划分
int n,q;
int a[N];
int g[F][N+F],f[F][N+F];  //步数，序号
int s,d,k;
void solve()
{
    cin>>n>>q;

    for (int i=0;i<n;i++) cin>>a[i];

    for (int d=1;d<F;d++)    //预处理
    for (int i=0;i<n;i++)
    {
        f[d][i+d]=f[d][i]+a[i]*(i/d+1);
        g[d][i+d]=g[d][i]+a[i];
    }
    while (q--)
    {
        cin>>s>>d>>k;
        s--;
        if (d<F)
        {
            int r=s+d*k;
            cout<<f[d][r]-f[d][s]-(g[d][r]-g[d][s])*(s/d)<<" ";
        }
        else 
        {
            int ans=0;
            for (int i=0;i<k;i++) ans +=a[s+d*i]*(i+1);
            cout<<ans<<" ";
        }
    }
    cout<<endl;
}
signed main()
{
    ios;
    int T=1;
    cin>>T;
    while (T--) solve();
    return 0;
}