记录编号	424911	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]布娃娃	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.850 s
提交时间	2017-07-14 13:39:06	内存使用	8.32 MiB

#include<cstdio>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=3e5+10;
int n,p[N],c[N],l[N],r[N];
void init(int *a){
	int add,first,mod,prod;
	scanf("%d%d%d%d",&add,&first,&mod,&prod);
	a[1]=first%mod;
	for (int i=2;i<=n;i++) a[i]=(1ll*a[i-1]*prod+add+i)%mod;
}
struct Treap{
	struct node{
		int k,size,ran;
		node *l,*r;
		node(int key){
			k=key;size=1;
			ran=rand();
			l=r=0;
		}
		void update(){
			size=1;
			if (l) size+=l->size;
			if (r) size+=r->size;
		}
	}*root;
	node *l_rot(node *x){
		node *y=x->r;
		x->r=y->l;y->l=x;
		x->update();
		y->update();
		return y;
	}
	node *r_rot(node *x){
		node *y=x->l;
		x->l=y->r;y->r=x;
		x->update();
		y->update();
		return y;
	}
	node *insert(node *x,int key){
		if (!x) return x=new node(key);
		x->size++;
		if (x->k>key){
			x->r=insert(x->r,key);
			if (x->r->ran>x->ran) x=l_rot(x);
		}
		else{
			x->l=insert(x->l,key);
			if (x->l->ran>x->ran) x=r_rot(x);
		}
		return x;
	}
	int rank(int k){
		if (!root||k>root->size) return 0;
		node *x=root;
		while (1){
			int i=x->l?x->l->size+1:1;
			if (i==k) return x->k;
			if (k>i) k-=i,x=x->r;else x=x->l;
		}
	}
	node *merge(node *x,node *y){
		if (!x||!y) return x?x:y;
		if (x->ran>y->ran){
			x->r=merge(x->r,y);
			x->update();
			return x;
		}
		else{
			y->l=merge(x,y->l);
			y->update();
			return y;
		}
	}
	node *del(node *x,int key){
		if (x->k==key) return merge(x->l,x->r);
		x->size--;
		if (x->k>key) x->r=del(x->r,key);
			else x->l=del(x->l,key);
		return x;
	}
}T;
struct opt{int T,tp,k;}Q[N];
int m;
//tp=1表示插入k,tp=-1表示删除k,tp=0表示询问第k大
bool cmp(const opt &x,const opt &y){
	return x.T==y.T?x.tp>y.tp:x.T<y.T;
}
int main()
{
	freopen("doll.in","r",stdin);
	freopen("doll.out","w",stdout);
	srand(time(0));
	scanf("%d",&n);
	init(p);init(c);init(l);init(r);
	for (int i=1;i<=n;i++){
		//printf("p=%d c=%d [%d,%d]\n",p[i],c[i],l[i],r[i]);
		if (l[i]>r[i]) swap(l[i],r[i]);
		Q[++m]=(opt){p[i],0,i};
		Q[++m]=(opt){l[i],1,c[i]};
		Q[++m]=(opt){r[i],-1,c[i]};
	}
	sort(Q+1,Q+m+1,cmp);
	long long ans=0;
	for (int i=1;i<=m;i++){
		if (Q[i].tp==1) T.root=T.insert(T.root,Q[i].k);
		if (Q[i].tp==0) ans+=T.rank(Q[i].k);
		if (Q[i].tp==-1) T.root=T.del(T.root,Q[i].k);
	}
	printf("%lld\n",ans%19921228);
	return 0;
}