记录编号	142954	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]布娃娃	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.090 s
提交时间	2014-12-12 09:12:44	内存使用	9.47 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZEN=100010,MOD=19921228;
class Node{//线段树的节点
public:
	int a,b;
	int lc,rc;
	int sum;
	#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 sum(x) Tree[x].sum
}Tree[SIZEN*2];
int tot=0,root;
int build(int l,int r){
	int p=++tot;
	a(p)=l,b(p)=r,sum(p)=0;
	if(l==r) lc(p)=rc(p)=0;
	else{
		int mid=(l+r)/2;
		lc(p)=build(l,mid);
		rc(p)=build(mid+1,r);
	}
	return p;
}
void modify(int p,int x,int t){
	if(!p||a(p)>x||b(p)<x) return;
	sum(p)+=t;
	modify(lc(p),x,t);
	modify(rc(p),x,t);
}
int query_kth(int x,int k){//第k大
	if(!x) return 0;
	if(a(x)==b(x)) return a(x);
	else{
		if(sum(rc(x))>=k) return query_kth(rc(x),k);
		else return query_kth(lc(x),k-sum(rc(x)));
	}
}
class Generator{
public:
	LL add,first,mod,prod;
	void read(void){scanf("%lld%lld%lld%lld",&add,&first,&mod,&prod);}
	void assign(int a[],int n){
		a[1]=first%mod;
		for(int i=2;i<=n;i++)
			a[i]=(a[i-1]*prod+add+i)%mod;
	}
};
class Event{
public:
	int pos;
	int cmd;//1加0查-1删
	int id;
};
bool operator < (Event a,Event b){
	if(a.pos<b.pos) return true;
	if(a.pos>b.pos) return false;
	if(a.cmd<b.cmd) return false;
	if(a.cmd>b.cmd) return true;
	return a.id<b.id;
}
int N;
Generator GP,GC,GL,GR;
int P[SIZEN],C[SIZEN],L[SIZEN],R[SIZEN];
int CX[SIZEN]={0};
Event E[SIZEN*3];
void work(void){
	int ans=0;
	for(int i=1;i<=3*N;i++){
		if(E[i].cmd==0){//查询
			//注意CX[0]=0
			int k=query_kth(root,E[i].id);
			ans+=CX[k],ans%=MOD;
		}
		else modify(root,C[E[i].id],E[i].cmd);
	}
	printf("%d\n",ans);
}
void init(void){
	for(int i=1;i<=N;i++) CX[i]=C[i];
	sort(CX+1,CX+1+N);
	for(int i=1;i<=N;i++) C[i]=lower_bound(CX+1,CX+1+N,C[i])-CX;
	int tot=0;
	for(int i=1;i<=N;i++){
		E[++tot]=(Event){L[i],1,i};
		E[++tot]=(Event){P[i],0,i};
		E[++tot]=(Event){R[i],-1,i};
	}
	sort(E+1,E+1+tot);
	root=build(0,N);//0是一个空位置,用来判断无解
}
void read(void){
	scanf("%d",&N);
	GP.read();
	GC.read();
	GL.read();
	GR.read();
	GP.assign(P,N);
	GC.assign(C,N);
	GL.assign(L,N);
	GR.assign(R,N);
	for(int i=1;i<=N;i++) if(L[i]>R[i]) swap(L[i],R[i]);
}
int main(){
	freopen("doll.in","r",stdin);
	freopen("doll.out","w",stdout);
	read();
	init();
	work();
	return 0;
}