YJQQQAQ's Blog

#include <cstdio>
#include <algorithm>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define lowbit(x) ((x) & (-(x)))
using namespace std;
int n,m,flag;
const int MAXN = 500010;
int bit[MAXN];
long long buf[MAXN / 20];
long long ask(int p) {
	long long ret = 0;
	int bs = p / 20;
	for (int i=1;i<=p % 20;i++) {
		ret += bit[20 * bs + i];
	}
	return buf[bs] + ret;
}	
long long query(int l,int r) {
	return ask(r) - ask(l-1);
}
int main() {
#ifdef YJQ_LOCAL
	freopen(".in","r",stdin);
#endif
	scanf("%d%d%d",&n,&m,&flag);
	long long cur = 0;
	for (int i=1;i<=n;i++) {
		int v;
		scanf("%d",&v);
		cur += v;
		bit[i] = v;
		if (i % 20 == 0) buf[i / 20] = cur;
	}
	long long lastans = 0;
	while (m--) {
		long long l,r;
		scanf(LL "" LL, &l, &r);
		if (flag) {
			l ^= lastans;
			l = l % n + 1;
			r ^= lastans;
			r = r % n + 1;
		}
		if (l > r) swap(l,r);
		lastans = query(l,r);
		printf(LL "\n",lastans);
		lastans = abs(lastans);
	}
} 

题解：

       （一开始我还以为是树状数组），题意就是给一个序列N，每次询问一段区间里面所有数的和。

         开始秒写树状数组（智商下降），然后发现T了OvO，秒改前缀和，发现MLE了←_←

         说着就陷入了纠结：总共3MB内存，然而前缀和全开long long要4MB，开int又要溢出。

         蒟蒻的我开始向zhonghaoxi求救，被D了一番，然后钟神教我写分块OvOOvOOvO

         怎么就没想到呢。