记录编号 |
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;
}