BZOJ4216 Pig 解题报告【卡空间】【数据结构】【分块】

本文主要是介绍BZOJ4216 Pig 解题报告【卡空间】【数据结构】【分块】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description
红学姐和黄学长是好朋友。
有一天，黄学长想吃猪肉丸，于是他去找红学姐买猪。红学姐到她的猪圈中赶猪的时候发现有许多猪逃离了她的猪圈。同时红学姐发现，一个名叫wwf的魔法猪藏在某
个猪圈中施法。然而wwf实在太巨了，红学姐并没有办法捉住它，只好向方老师求救。
为了确定wwf的位置，方老师向红学姐提出了m组询问，每次询问标号在区间[l,r]内的猪圈剩余的猪的数量和，但红学姐不屑于做这些简单的问题，就把它们交给了你，同
时给了你一台内存较小的电脑。
由于wwf施展了一些奇怪的魔法，所以猪圈中猪的数量可能是负数。
Input
第一行两个正整数n,m,t。n表示猪圈数，m表示询问数，t=0表示方老师没有对询问进行加密，t=1表示方老师对询问进行了加密，解密方法如下：
其中^表示异或操作，last_ans表示上一次询问的答案，对于第一次询问，last_ans=0。
第二行n个整数，第i个整数x[i]表示标号为i的猪圈中剩余猪的数量。
接下来m行每行两个正整数l,r表示一组询问。
Output
输出m行，第i行表示第i个询问的答案
Sample Input
5 5 1
1 3 -4 5 -3
3 4
1 1
2 3
2 4
3 5
Sample Output
2
5
-1
5
4
HINT
N,M<=500000,|x[i]|<=8000000
解题报告
这道题一看，一个区间求和还没有修改，一个前缀和就可以搞定。然而看到Memory Limit: 3 MB，这就非常绝望了。因为我们要开long long，所以前缀和是显然开不到5e5的。那么就有两条路，一条是把前缀和数组拆分开来，另一条是分段存储前缀和，也就是分块。
由于内存坑，我开不了bl数组，就只好用的时候变量写出来了。
代码：

#include<cmath>
#include<cstdio>
#include<cstring>
#define abs(x)((x>=0)?x:(-x))
const int N=500000;
const int M=707;
int a[N+5],L[M+5],R[M+5];
long long sum[M+5];
int n,m,blk,cnt,t;
long long ans;
long long query(int lf,int rg)
{long long ret=0;int blx=(lf-1)/blk+1,bly=(rg-1)/blk+1;if(blx==bly){for(int i=lf;i<=rg;i++)ret+=a[i];}else{for(int i=lf;i<=R[blx];i++)ret+=a[i];for(int i=L[bly];i<=rg;i++)ret+=a[i];for(int i=blx+1;i<=bly-1;i++)ret+=sum[i];}return ret;
}
void swap(int &a,int &b)
{int temp=a;a=b,b=temp;
}
int main()
{scanf("%d%d%d",&n,&m,&t);for(int i=1;i<=n;i++)scanf("%d",&a[i]);blk=sqrt(n);if(n%blk)cnt=n/blk+1;else cnt=n/blk;for(int i=1;i<=cnt;i++)L[i]=(i-1)*blk+1,R[i]=i*blk;R[cnt]=n;for(int i=1;i<=n;i++)sum[(i-1)/blk+1]+=a[i];for(int i=1;i<=m;i++){int lf,rg;scanf("%d%d",&lf,&rg);if(t)lf=(lf^abs(ans))%n+1,rg=(rg^abs(ans))%n+1;if(lf>rg)swap(lf,rg);ans=query(lf,rg);printf("%lld\n",ans);}return 0;
}