BZOJ4216: Pig 恶心题+前缀和

题解：

要支持在线，还要求区间的和，显然应该用前缀和预处理嘛。

但是内存非常鬼畜，50W个long long根本是开不下的！

所以应该分块存前缀和，如果从理论上计算的话两个一块内存就够用了，但是这样的话完全没考虑系统的运行空间。

所以要留出更多的内存，每16个分成一块就行了。

注意开了某些库也会增大内存哦~~

代码：

#include<cstdio>

typedef long long ll;
ll p[500020>>4];
int a[500010];

int n,m,t,cnt;
ll lastans,l,r;

inline ll get(int x){
	static ll ans;
	static int i;
	ans=p[x>>4];
	for(i=((x>>4)<<4)+1;i<=x;++i)
		ans+=a[i];
	return ans;
}
inline void swap(ll&a,ll&b){
	static ll t;
	t=a;
	a=b;
	b=t;
}
int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		if(i%16==1){
			++cnt;
			p[cnt]=p[cnt-1];
		}
		p[cnt]+=a[i];
	}
	while(m--){
		scanf("%lld%lld",&l,&r);
		if(t){
			l=(l^lastans)%n+1;
			r=(r^lastans)%n+1;
			if(l>r)
				l^=r^=l^=r;
		}
		printf("%lld\n",lastans=get(r)-get(l-1));
		if(lastans<0)
			lastans=-lastans;
	}
	return 0;
}