记录编号	142380	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]stone	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.478 s
提交时间	2014-12-08 10:54:33	内存使用	4.74 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define sqr(x) ((x)*(x))
const int SIZEN=40010,INF=0x7fffffff/2;
class NODE{
public:
	int a,b;
	int lc,rc;
	int mn;
	int lazy;
	#define a(x) Tree[x].a
	#define b(x) Tree[x].b
	#define lc(x) Tree[x].lc
	#define rc(x) Tree[x].rc
	#define mn(x) Tree[x].mn
	#define lazy(x) Tree[x].lazy
}Tree[SIZEN*4];
int tot=0;
void pushdown(int x){
	if(!x||!lc(x)) return;
	mn(lc(x))+=lazy(x);lazy(lc(x))+=lazy(x);
	mn(rc(x))+=lazy(x);lazy(rc(x))+=lazy(x);
	lazy(x)=0;
}
void update(int x){
	if(!x||!lc(x)) return;
	mn(x)=min(mn(lc(x)),mn(rc(x)));
}
int build(int l,int r,int s[]){
	int p=++tot;
	a(p)=l;b(p)=r;lazy(p)=0;
	if(l==r){
		lc(p)=rc(p)=0;
		mn(p)=s[l];
	}
	else{
		int mid=(l+r)/2;
		lc(p)=build(l,mid,s);
		rc(p)=build(mid+1,r,s);
		update(p);
	}
	return p;
}
int query(int x,int l,int r){
	if(!x||a(x)>r||b(x)<l) return INF;
	pushdown(x);
	if(a(x)>=l&&b(x)<=r) return mn(x);
	else return min(query(lc(x),l,r),query(rc(x),l,r));
}
void change(int x,int l,int r,int t){//[l,r]区间加t
	if(!x||a(x)>r||b(x)<l) return;
	pushdown(x);
	if(a(x)>=l&&b(x)<=r){
		mn(x)+=t;
		lazy(x)+=t;
	}
	else{
		change(lc(x),l,r,t);
		change(rc(x),l,r,t);
		update(x);
	}
}
int N,M;
int A[SIZEN]={0};
int S[SIZEN]={0};
int K[SIZEN]={0};
int L[SIZEN],R[SIZEN];
int f_Root,g_Root;
//f[i]=S[i]-TR[i],g[i]=TL[i]-S[i]
//需要对任意j>i都有f[j]+g[i]>=0
void work(void){
	f_Root=build(0,N,S);
	for(int i=1;i<=N;i++) S[i]*=-1;
	g_Root=build(0,N,S);
	for(int i=1;i<=M;i++){
		/*
		假设这次是x~y,选的石头数量为t
		那么TR[y]~TR[N]+=t,f[y]~f[N]-=t
		同时TL[x]~TL[N]+=t,g[x]~g[N]+=t
		对于x'<x<=y<=y'的(x',y'),(f[y']+g[x'])-=t
		对于x<=x'<=y'<=y的(x',y'),(f[y']+g[x'])+=t,但never mind
		*/
		int now=query(f_Root,R[i],N)+query(g_Root,0,L[i]-1);
		now=min(now,K[i]);
		printf("%d\n",now);
		change(f_Root,R[i],N,-now);
		change(g_Root,L[i],N,now);
	}
}
void read(void){
	scanf("%d",&N);
	int x,y,z,P;
	scanf("%d%d%d%d",&x,&y,&z,&P);
	for(int i=1;i<=N;i++){
		A[i]=sqr(i-x)%P;
		A[i]+=sqr(i-y)%P;A[i]%=P;
		A[i]+=sqr(i-z)%P;A[i]%=P;
		S[i]=S[i-1]+A[i];
	}
	scanf("%d",&M);
	scanf("%d%d%d%d%d%d",&K[1],&K[2],&x,&y,&z,&P);
	for(int i=3;i<=M;i++){
		K[i]=(x*K[i-1])%P;
		K[i]+=(y*K[i-2])%P;K[i]%=P;
		K[i]+=z%P;K[i]%=P;
	}
	for(int i=1;i<=M;i++) scanf("%d%d",&L[i],&R[i]);
}
int main(){
	freopen("nt2011_stone.in","r",stdin);
	freopen("nt2011_stone.out","w",stdout);
	read();
	work();
	return 0;
}