Cogs 1695. 梦游仙境(分块)

1. 梦游仙境

   ★☆ 输入文件：XTTMYXJ.in 输出文件：XTTMYXJ.out 简单对比

   时间限制：5 s 内存限制：512 MB

   【题目描述】

   在Asm.def仍然在与人工智能进行艰苦的斗争时，雪甜甜小公主仍然在亚特兰蒂斯里自娱自乐，她不小心误闯了玛丽奥的世界。

   她感觉十分有趣，她闯关到了一行有n个小块上面有傻币的地面（可以看成一个数轴），地面上有许多，假如雪甜甜的起点为l,终点为r,跳跃能力为jump,从左往右跳

   针对雪甜甜皇家公主给出的q组询问l,r,jump，你需要计算他获得的傻币数

   例如下面这种情况

   地面的金币数列:

   2 1 4 7 4 1 2 5 1

   w[1] w[2] w[3] w[4] w[5] w[6] w[7] w[8] w[9]

   若l=2,r=7,jump=3,则总傻币数为w[2]+w[5]=5（w[8]不算，因为雪甜甜跳不到）

   若l=3,r=4,jump=2,则总傻币数为w[3]=4(没法跳，只能留在原地)

   【输入格式】

   第一行为两个整数n，q

   第二行n个数，表示w[i]

   接下来q行每行三个数l,r,jump

   【输出格式】

   总共q行，每行一个答案ans

   【样例输入】

   10 5

   2 1 4 7 4 8 3 6 4 7

   1 10 233333

   4 7 666666

   2 10 2

   1 9 4

   3 5 3

   【样例输出】

   2

   7

   29

   10

   4

   【提示】

   对于30%的数据,n<=2000

   对于100%的数据,n<=100000,q<=500000

/*
本蒟蒻做的第一道分块题.
一开始没想到怎么分.
大概就是对于jump值>sqrt(n)的询问暴力处理.
对于jump值<=sqrt(n)的询问做一个预处理.
sum[i][j]表示跳i次,编号(重新编号)为j的点的前缀答案贡献.
查询的时候我们保证了跳跃起点相同的点的编号是连续的
而且查询的[l,r]有贡献的两个端点必定是同一起跳起点跳过来的.
so 前缀和直接相减就可以.
复杂度O(q√n).
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#define MAXN 100001
#define MAXM 320
#define LL long long
using namespace std;
int n,m,K,a[MAXN],s[MAXM][MAXN],g[MAXM][MAXN];
LL sum[MAXM][MAXN];
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
    return x*f;
}
void pre()
{
    int pos;
    for(int i=1;i<=K;i++)//枚举跳的长度.
    {
      pos=0;
      for(int j=1;j<=i;j++)//枚举跳的起点(显然共有i种情况).
        for(int k=j;k<=n;k+=i)//跳.
        {
            g[i][k]=++pos;
            s[i][pos]=a[k];
        }
      for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+(LL)s[i][j];
    }
}
LL slove1(int l,int r,int jump)
{
    LL tot=0;
    for(int i=l;i<=r;i+=jump) tot+=a[i];
    return tot;
}
LL slove2(int l,int r,int jump)
{
    int ll=l,rr=r-(r-l)%jump;
    if(!jump||ll>=rr) return a[ll];
    ll=g[jump][ll],rr=g[jump][rr];
    return sum[jump][rr]-sum[jump][ll-1];
}
int main()
{
    freopen("XTTMYXJ.in","r",stdin);
    freopen("XTTMYXJ.out","w",stdout);
    int x,y,z;
    n=read(),m=read();K=sqrt(n);
    for(int i=1;i<=n;i++) a[i]=read();
    pre();
    while(m--)
    {
        x=read(),y=read(),z=read();
        if(z>K)  printf("%lld\n",slove1(x,y,z));
        else printf("%lld\n",slove2(x,y,z));
    }
    return 0;
}