考虑分块，每块大小为13，则一共需要38465块，求出b[i]表示前i块的和。
查询时中间部分可以$O(1)$查询，只需再往两边累加零散的不超过26个数的和。
空间上一共需要开500000的int和38465的long long。
#include<cstdio>
typedef long long ll;
const int N=500001,M=38465,K=13;
int n,m,t,i,a[N],l,r;ll ans,x,y,b[M];
inline void read(int&a){
char c;bool f=0;a=0;
while(!((((c=getchar())>=‘0‘)&&(c<=‘9‘))||(c==‘-‘)));
if(c!=‘-‘)a=c-‘0‘;else f=1;
while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;
if(f)a=-a;
}
inline void read(ll&a){char c;while(!(((c=getchar())>=‘0‘)&&(c<=‘9‘)));a=c-‘0‘;while(((c=getchar())>=‘0‘)&&(c<=‘9‘))(a*=10)+=c-‘0‘;}
inline int pos(int x){return(x-1)/K+1;}
inline void ask(int l,int r){
if(pos(l)==pos(r)){
for(i=l;i<=r;i++)ans+=a[i];
return;
}
ans=b[pos(r)-1]-b[pos(l)];
for(i=l;pos(i)==pos(l);i++)ans+=a[i];
for(i=r;pos(i)==pos(r);i--)ans+=a[i];
}
int main(){
read(n),read(m),read(t);
for(i=1;i<=n;i++)read(a[i]),b[pos(i)]+=a[i];
for(i=2;i<=pos(n);i++)b[i]+=b[i-1];
while(m--){
if(ans<0)ans=-ans;
read(x),read(y);
if(t)l=(x^ans)%n+1,r=(y^ans)%n+1;else l=x,r=y;
if(l>r)i=l,l=r,r=i;
ans=0,ask(l,r);
printf("%lld\n",ans);
}
return 0;
}
原文：http://www.cnblogs.com/clrs97/p/4679804.html