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模板引擎的設計和使用方法