题目描述

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

题目分析

因为内存只有3MB限制 不够开long long前缀和
那我们就分块 对每一个块开long long的sum[] 这样不炸内存
其余操作和正常分块一样

#include <cstdio>
#include <algorithm>
int n,m,t,siz;
int val[500010];
long long sum[10010];
long long abs(long long a)
{
    return a>0?a:-a;
}
int main()
{
    scanf("%d%d%d",&n,&m,&t);
    for(int i=0;i<n;i++) scanf("%d",&val[i]);
    siz=250;
    long long tmp=0;
    for(int i=0;i<n;i++)
        sum[i/siz]=(long long)sum[i/siz]+val[i];
    long long ans=0;
    for(int tmp,l,r,i=1;i<=m;i++)
    {
        scanf("%d%d",&l,&r);
        if(t) l=((long long)l^abs(ans))%n+1,r=((long long)r^abs(ans))%n+1;
        if(l>r) std::swap(l,r);
        l--,r--;
        ans=0;
        if(l/siz==r/siz) for(int j=l;j<=r;j++) ans=(long long)ans+val[j]; 
        else
        {
            for(int j=l;j<l/siz*siz+siz;j++) ans=(long long)ans+val[j];
            for(int j=r/siz*siz;j<=r;j++) ans=(long long)ans+val[j];
            for(int j=l/siz+1;j<r/siz;j++) ans=(long long)ans+sum[j];
        }
        printf("%lld\n",ans);
    }   
    return 0;
}