F. Sum of Progression

思路：首先根据数据范围，可以发现，可以用分治来写。

根据感觉可以猜一猜，让S=350。

1.如果d>=S，直接暴力算

2.d<=S，我们根据d值来分组，d值相同的肯定分到一组。比如分为三组：(3,6,9),(1,4,7,10)(2,5,8),
例如要查询7,10,那么相当于结果为 1*7+2*10，我们发现它其实是 3*7+4*10-2*(7+10);我们维护两个前缀和
a[1],2*a[2],3*a[3],k*a[k];
a[1],a[2],a[3],a[k];

代码：

const int S=350;

/*
比如分为三组：(3,6,9),(1,4,7,10),(2,5,8),
例如要查询7,10,那么相当于结果为 1*7+2*10
，我们发现它其实是 3*7+4*10-2*(7+10);
我们维护两个前缀和
a[1],2*a[2],3*a[3],k*a[k];
a[1],a[2],a[3],a[k];
。
*/


void solve(){
	int n,q;
	cin>>n>>q;
	vector<int>a(n+1);
	for(int i=1;i<=n;i++)
		cin>>a[i];
	vector<int>ans(q);
	vector<vector<array<int,3>>>query(S+1);
	for(int i=0;i<q;i++){
		int s,d,k;
		cin >> s >> d >> k;
		if(d > S){
			int sum = 0;
			for(int j = 1;j <= k; j++){
				sum+=a[s]*j;
				s+=d;
			}
			ans[i]=sum;
		}else{
			query[d].push_back({s,k,i});
		}
	}
	for(int i=1;i<=S;i++){
		if(query[i].empty())continue;
		vector<int>s1(n+1),s2(n+1);
		for(int j=1;j<=n;j++){
			int t=(j+i-1)/i;
			s1[j]=a[j];
			s2[j]=a[j]*t;
			if(t>1){
				s1[j]+=s1[j-i];
				s2[j]+=s2[j-i];
			}
		}
		for(auto [st,k,id]:query[i]){
			int ed=st+(k-1)*i;
			int t=(st+i-1)/i;
			if(t==1){
				ans[id]=s2[ed];
			}else{
				ans[id]=s2[ed]-s2[st-i]-(t-1)*(s1[ed]-s1[st-i]);
			}
		}
	}
	for(auto x:ans)cout<<x<<' ';
	cout<<endl;
}