【BZOJ2161】布娃娃

Description

小时候的雨荨非常听话，是父母眼中的好孩子。在学校是老师的左右手，同学的好榜样。后来她成为艾利斯顿第二代考神，这和小时候培养的良好素质是分不开的。雨荨的妈妈也为有这么一个懂事的女儿感到高兴。一次期末考试，雨荨不知道第多少次，再次考了全年级第一名。雨荨的妈妈看到女儿100分的成绩单时，脸上又泛起了幸福的笑容，作为奖励，她给雨荨买了n个布娃娃。细心的雨荨发现，第i个布娃娃有一个耐心值P[i]以及一个魅力值C[i]，并且还有能够忍受的耐心值的上限R[i]以及下限L[i]。当一个布娃娃j满足L[j]<=P[i]并且P[i]<=R[j]，那么布娃娃j喜欢布娃娃i。雨荨还发现，一个布娃娃有可能喜欢它自己。每个布娃娃心中都有一个谜团，具体来说就是：第i个布娃娃想知道喜欢它的布娃娃中，魅力值第i大的布娃娃的魅力值是多少，并且称这个布娃娃的谜团答案为这个魅力值的大小，如果不存在，那么这个布娃娃的谜团答案为0。鉴于雨荨的上司栋栋不让题目的数据过大，下面给出数据的生成方法：给出16个参数：

Padd, Pfirst, Pmod, Pprod, Cadd, Cfirst, Cmod, Cprod, Ladd, Lfirst, Lmod, Lprod, Radd, Rfirst, Rmod, Rprod。

----------------------------------------------------------------------------------------

P[1] = Pfirst % Pmod, P[i] = (P[i-1] Pprod + Padd + i) % Pmod (i > 1)。

----------------------------------------------------------------------------------------

对于C、L、R数组也有类似的得到方式, %代表取余运算。注意：L和R数组生成完之后，如果某个布娃娃的忍耐度上限小于下限，那么交换它的上限和下限。当然，雨荨也不会让你告诉她每个布娃娃的谜团答案，因为那样会使输出数据很大。所以雨荨希望你告诉她，所有布娃娃谜团答案的和除以19921228的余数是多少。

Input

输入的第一行有一个整数n，代表布娃娃的个数。

输入的第二行有16个用空格隔开的整数

分别代表Padd,Pfirst,Pmod,Pprod,Cadd,Cfirst,Cmod,Cprod,Ladd,Lfirst,Lmod,Lprod,Radd,Rfirst,Rmod,Rprod。

16个参数均为1到100,000,000中的整数。

Output

输出一个整数，代表所有布娃娃谜团答案的和除以19921228的余数。

Sample Input

3
2 3 4 3 1 4 5 2 3 6 9 1 1 2 3 4

Sample Output

题面补充：n<=10^5，注意，是“喜欢它”的布娃娃，不是“它喜欢”的布娃娃！（一开始写了个主席树。。。）

一句话题面：给你堆点和一堆线段，对于每个点，询问在所有覆盖它的线段中，权值第k大的权值是多少。

题解：直接上扫描线+权值线段树即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define lson x<<1

#define rson x<<1|1

using namespace std;

typedef long long ll;

const int maxn=100010;

const int mod=19921228;

const int inf=100000000;

int n,tot,ans,nm;

int Padd,Pfirst,Pmod,Pprod,Cadd,Cfirst,Cmod,Cprod,Ladd,Lfirst,Lmod,Lprod,Radd,Rfirst,Rmod,Rprod;

int P[maxn],C[maxn],L[maxn],R[maxn],s[maxn<<2],ref[maxn];

struct Q1

{

	int x,y,val;

}q1[maxn<<1];

struct Q2

{

	int x,org;

}q2[maxn];

struct node

{

	int num,org;

}p[maxn];

bool cmp1(Q1 a,Q1 b)

{

	return a.x<b.x;

}

bool cmp2(Q2 a,Q2 b)

{

	return a.x<b.x;

}

bool cmp3(node a,node b)

{

	return a.num<b.num;

}

void updata(int l,int r,int x,int a,int b)

{

	s[x]+=b;

	if(l==r)	return ;

	int mid=l+r>>1;

	if(a<=mid)	updata(l,mid,lson,a,b);

	else	updata(mid+1,r,rson,a,b);

}

int query(int l,int r,int x,int b)

{

	if(l==r)	return ref[l];

	int sm=s[rson],mid=l+r>>1;

	if(b<=sm)	return query(mid+1,r,rson,b);

	return query(l,mid,lson,b-sm);

}

int main()

{

	scanf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",&n,&Padd,&Pfirst,&Pmod,&Pprod,&Cadd,&Cfirst,&Cmod,&Cprod,&Ladd,&Lfirst,&Lmod,&Lprod,&Radd,&Rfirst,&Rmod,&Rprod);

	int i,j;

	P[1]=Pfirst%Pmod;

	for(i=2;i<=n;i++)	P[i]=((ll)P[i-1]*Pprod+Padd+i)%Pmod;

	C[1]=Cfirst%Cmod;

	for(i=2;i<=n;i++)	C[i]=((ll)C[i-1]*Cprod+Cadd+i)%Cmod;

	L[1]=Lfirst%Lmod;

	for(i=2;i<=n;i++)	L[i]=((ll)L[i-1]*Lprod+Ladd+i)%Lmod;

	R[1]=Rfirst%Rmod;

	for(i=2;i<=n;i++)	R[i]=((ll)R[i-1]*Rprod+Radd+i)%Rmod;

	for(i=1;i<=n;i++)

	{

		if(L[i]>R[i])	swap(L[i],R[i]);

		q1[i].x=L[i],q1[i+n].x=R[i]+1,q1[i].val=1,q1[i+n].val=-1;

		q2[i].x=P[i],q2[i].org=i;

		p[i].num=C[i],p[i].org=i;

	}

	sort(p+1,p+n+1,cmp3);

	ref[0]=-1;

	for(i=1;i<=n;i++)

	{

		if(p[i].num>ref[nm])	ref[++nm]=p[i].num;

		q1[p[i].org].y=q1[p[i].org+n].y=nm;

	}

	sort(q1+1,q1+2*n+1,cmp1);

	sort(q2+1,q2+n+1,cmp2);

	for(i=j=1;i<=n;i++)

	{

		for(;q1[j].x<=q2[i].x&&j<=2*n;j++)	updata(1,nm,1,q1[j].y,q1[j].val);

		if(s[1]>=q2[i].org)	ans=(ans+query(1,nm,1,q2[i].org))%mod;

	}

	printf("%d",ans);

	return 0;

}

巴特西

【BZOJ2161】布娃娃扫描线+线段树

【BZOJ2161】布娃娃

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

巴特西

【BZOJ2161】布娃娃 扫描线+线段树

【BZOJ2161】布娃娃

Description

Input

Output

Sample Input

Sample Output

最新文章

热门文章

【BZOJ2161】布娃娃扫描线+线段树