记录编号	298737	评测结果	AAAAAAAAAA
题目名称	梦游仙境	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	8.870 s
提交时间	2016-08-22 16:44:58	内存使用	440.10 MiB

#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
inline int cat_min(const int &a,const int &b){return a<b ? a:b;}
inline int cat_max(const int &a,const int &b){return a>b ? a:b;}
const int maxn = 100010;
const int maxq = 500010;
const int maxm = 320;//sqrt(maxn)
int w[maxn],map[maxm][maxn],val[maxm][maxn],l,r,jump;
ll sum[maxm][maxn];
ll solve1(){
	if( !jump ) return (ll)(w[l]);
	int L = l,R = r - (r - l) % jump;
	if( L > R ) return (ll)(w[l]);
	L = map[jump][L],R = map[jump][R];
	return (sum[jump][R] - sum[jump][L-1]);
}
ll solve2(){
	ll ret = 0;
	for(int i=l;i<=r;i+=jump) ret += (ll)(w[i]);
	return ret;
}
int main(){
	freopen("XTTMYXJ.in","r",stdin);
	freopen("XTTMYXJ.out","w",stdout);
	int n,q;
	read(n);read(q);
	for(int i=1;i<=n;++i) read(w[i]);
	int m = (int)(sqrt((double)n));
	for(int i=1;i<=m;++i){
		int cnt = 0;
		for(int j = 1;j<=i;++j){
			for(int k = j;k <= n;k += i){
				map[i][k] = ++cnt;
				val[i][cnt] = w[k];
			}
		}
		for(int j = 1;j<=n;++j){
			sum[i][j] = sum[i][j-1] + val[i][j];
		}
	}
	while(q--){
		read(l);read(r);read(jump);
		if( jump <= m ) printf("%lld\n",solve1());
		else printf("%lld\n",solve2());
	}
	fclose(stdin);fclose(stdout);
	return 0;
}