记录编号	143472	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]cheat(吴确)	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	3.511 s
提交时间	2014-12-14 22:56:57	内存使用	66.70 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int SIZEn=255,SIZEN=62510;
typedef long long LL;
class PS_Array{//前缀和数组
public:
	int n,m;
	int s[SIZEn][SIZEn];
	void clear(int n_,int m_){
		n=n_,m=m_;
		memset(s,0,sizeof(s));
	}
	void turn_to_pre(void){
		static int a[SIZEn][SIZEn];
		for(int i=1;i<=n;i++){
			a[i][0]=0;
			for(int j=1;j<=m;j++) a[i][j]=a[i][j-1]+s[i][j];
		}
		for(int j=1;j<=m;j++){
			s[0][j]=0;
			for(int i=1;i<=n;i++) s[i][j]=s[i-1][j]+a[i][j];
		}
	}
	void add(int i,int j,int t){s[i][j]+=t;}//此时s还是普通数组,不是差分数组
	int sum(int x1,int y1,int x2,int y2){
		return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
	}
};
PS_Array R[SIZEn];//R数组的长度其实是块数
int n,m,N,Bsize;
LL V[SIZEn][SIZEn];
LL A[SIZEN],B[SIZEN],C[SIZEN];//其实只需要开到3000,有钱任性!
LL PA,PB,PC,P;
class Person{
public:
	int w,x,y;
};
bool operator < (Person a,Person b){return a.w<b.w;}
Person stu[SIZEN];
int W[SIZEN];
int query_Person(int k,int x1,int y1,int x2,int y2){
	int t=k/Bsize;
	int ans=R[t].sum(x1,y1,x2,y2);
	for(int i=t*Bsize+1;i<=k;i++)
		if(x1<=stu[i].x&&stu[i].x<=x2&&y1<=stu[i].y&&stu[i].y<=y2) ans++;
	return ans;
}
int query(int a,int b,int x1,int y1,int x2,int y2){
	int p1=lower_bound(W+1,W+1+N,a)-W;
	int p2=upper_bound(W+1,W+1+N,b)-W-1;
	return query_Person(p2,x1,y1,x2,y2)-query_Person(p1-1,x1,y1,x2,y2);
}
void work(void){
	int x1,y1,x2,y2,a,b,Q;
	scanf("%d",&Q);
	int ans=0;
	LL cmd[10]={0};
	for(int i=1;i<=Q;i++){
		for(int j=1;j<=6;j++) cmd[j]=A[i%PA]+B[i%PB]+C[i%PC]+A[j%PA]+B[j%PB]+C[j%PC];
		a=min(cmd[5]%P+1,cmd[6]%P+1),b=max(cmd[5]%P+1,cmd[6]%P+1);
		x1=min(cmd[1]%n+1,cmd[3]%n+1),x2=max(cmd[1]%n+1,cmd[3]%n+1);
		y1=min(cmd[2]%m+1,cmd[4]%m+1),y2=max(cmd[2]%m+1,cmd[4]%m+1);
		ans^=query(a,b,x1,y1,x2,y2);
		//懒惰的出题人→_→
	}
	printf("%d\n",ans);
}
void prepare(void){
	sort(stu+1,stu+1+N);
	for(int i=1;i<=N;i++) W[i]=stu[i].w;
	Bsize=sqrt(N+0.5);
	int cnt=0,nb=1;
	R[0].clear(n,m);R[1]=R[0];
	//R[0]全零就不用turn_to_pre了吧
	for(int i=1;i<=N;i++){
		R[nb].add(stu[i].x,stu[i].y,1);
		cnt++;
		if(cnt==Bsize){
			R[nb+1]=R[nb];
			R[nb].turn_to_pre();
			nb++,cnt=0;
		}
	}
	R[nb].turn_to_pre();
}
void read(void){
	scanf("%lld",&PA);for(int i=0;i<PA;i++) scanf("%lld",&A[i]);//注意这里的下标从0
	scanf("%lld",&PB);for(int i=0;i<PB;i++) scanf("%lld",&B[i]);
	scanf("%lld",&PC);for(int i=0;i<PC;i++) scanf("%lld",&C[i]);
	scanf("%d%d",&n,&m);
	scanf("%lld",&P);
	N=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			V[i][j]=A[i%PA]+B[i%PB]+C[i%PC]+A[j%PA]+B[j%PB]+C[j%PC];
			V[i][j]=V[i][j]%P+1;
			stu[++N]=((Person){V[i][j],i,j});
		}
	}
}
int main(){
	freopen("nt2011_cheat.in","r",stdin);
	freopen("nt2011_cheat.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}