记录编号	248686	评测结果	AAAAAAAAAA
题目名称	梦游仙境	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	25.157 s
提交时间	2016-04-10 20:30:39	内存使用	504.28 MiB

#include <fstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#define N 100010
#define M 330
using namespace std;
typedef long long ll;
ifstream in("XTTMYXJ.in");
ofstream out("XTTMYXJ.out");
int A[N]={0};
int n,q;
int m;
int num[M][N]={0};
int pos[M][N]={0};
ll s[M][N]={0};
int start,end;
void read()
{
	int i;
	in>>n>>q;
	for(i=1;i<=n;i++)in>>A[i];
	m=int(sqrt(double(n)));
	//out<<m<<endl;
}
ll ask(int l,int r,int x)
{
	int posl,posr,leng;
	ll sum=0;
	if(!x)return ll(A[l]);
	posl=l;posr=r-(r-l)%x;
	if(posl>posr)return ll(A[l]);
	posl=pos[x][posl];
	posr=pos[x][posr];
	sum=s[x][posr]-s[x][posl-1];
	return sum;
}
void init()
{
	int i,j,k,sum=0,top=0;
	for(i=1;i<=m;i++)
	{
		//mop=n%i;
		top=0;
		for(j=1;j<=i;j++)//向上取整
		{
			for(k=j;k<=n;k+=i)
			{
				pos[i][k]=++top;
				num[i][top]=A[k];
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		for(j=1;j<=n;j++)
		{
			s[i][j]=s[i][j-1]+num[i][j];
		}
	}
}
void work()
{
	int i,j;
	int l,r,x;
	ll ans=0;
	//out<<q<<endl;
	for(i=1;i<=q;i++)
	{
		in>>l>>r>>x;
		if(x<=m)
		{
			ans=ask(l,r,x);
			//out<<"A"<<endl;
		}
		else
		{
			ans=0;
			for(j=l;j<=r;j+=x)ans+=A[j];
			//out<<"B"<<endl;
		}
		out<<ans<<endl;
	}
}
int main()
{
	//start=clock();
	read();
	init();
	work();
	//end=clock();
	//out<<end-start<<endl;
	return 0;
}