Cogs 1695. 梦游仙境(分块)

2019-11-11 03:07:45

字体：大中小

来源：转载

供稿：网友

梦游仙境 ★☆ 输入文件：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 longusing 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;}

上一篇：【2月7日】Unity和控制台程序中生成随机数的方法

下一篇：ThinkTemplate模板引擎的设计和使用方法

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注