【BZOJ2253】[2010 Beijing wc]纸箱堆叠 cdq分治

时间：2024-07-11 09:04:44

【BZOJ2253】[2010 Beijing wc]纸箱堆叠

Description

P 工厂是一个生产纸箱的工厂。纸箱生产线在人工输入三个参数 n p a , , 之后，即可自动化生产三边边长为

(a mod P,a^2 mod p,a^3 mod P)
(a^4 mod p,a^5 mod p,a^6 mod P)
....
(a^(3n-2) mod p,a^(3n-1) mod p,a^(3n) mod p)的n个纸箱。在运输这些纸箱时，为了节约空间，必须将它们嵌套堆叠起来。一个纸箱可以嵌套堆叠进另一个纸箱当且仅当它的最短边、次短边和最长边长度分别严格小于另一个纸箱的最短边、次短边和最长边长度。这里不考虑任何旋转后在对角线方向的嵌套堆叠。 你的任务是找出这n个纸箱中数量最多的一个子集，使得它们两两之间都可嵌套堆叠起来。

Input

输入文件的第一行三个整数，分别代表 a,p,n

Output

输出文件仅包含一个整数，代表数量最多的可嵌套堆叠起来的纸箱的个数。

Sample Input

10 17 4

Sample Output

2
【样例说明】
生产出的纸箱的三边长为(10, 15, 14), (4, 6, 9) , (5, 16, 7), (2, 3, 13)。其中只有
(4, 6, 9)可堆叠进(5, 16, 7)，故答案为 2。
2<=P<=2000000000,1<=a<=p-1,a^k mod p<>0,ap<=2000000000,1<=N<=50000

题解：先把每个纸箱的边长都算出来，然后这题就变成了求二维LIS

先按x排序，然后用cdq分治，在处理区间[l,r]的时候，一定要先处理[l,mid]，再处理[l,r]内部，最后[mid+1,r]，处理[l,r]内部的具体方法如下：

先将[l,mid]和[mid+1,r]分别按y排序，然后用两个指针去扫，将左边的f[i]加入树状数组，再用树状数组里的f值更新右边的f[i]，注意一定要满足左边的x,y都比右边的小才能加入树状数组，最后再按x排回来

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define pc (B=(B*A)%P)

using namespace std;

const int maxn=50010;

typedef long long ll;

ll A,P,B;

int n,nm,ans;

int x[maxn],y[maxn],z[maxn],p[maxn],q[maxn],tr[maxn],f[maxn];

struct NUM

{

	int v,org;

}num[maxn];

bool cmp(NUM a,NUM b)

{

	return a.v<b.v;

}

bool cmpx(int a,int b)

{

	if(x[a]==x[b]&&y[a]==y[b])	return z[a]<z[b];

	if(x[a]==x[b])	return y[a]<y[b];

	return x[a]<x[b];

}

bool cmpy(int a,int b)

{

	if(x[a]==x[b]&&y[a]==y[b])	return z[a]<z[b];

	if(y[a]==y[b])	return x[a]<x[b];

	return y[a]<y[b];

}

void updata(int a,int v)

{

	for(int i=a;i<=nm;i+=i&-i)	tr[i]=max(tr[i],v);

}

void clr(int a)

{

	for(int i=a;i<=nm;i+=i&-i)	tr[i]=0;

}

int query(int a)

{

	if(!a)	return 0;

	int i,ret=0;

	for(i=a;i;i-=i&-i)	ret=max(ret,tr[i]);

	return ret;

}

void dfs(int l,int r)

{

	if(l==r)	return ;

	int mid=l+r>>1,h1=l,h2=mid+1,i;

	dfs(l,mid);

	sort(p+l,p+mid+1,cmpy);

	sort(p+mid+1,p+r+1,cmpy);

	for(i=l;i<=r;i++)

	{

		if(h1<=mid&&(h2>r||(y[p[h1]]<y[p[h2]]&&x[p[h1]]<x[p[h2]])))	updata(z[p[h1]],f[p[h1]]),h1++;

		else	f[p[h2]]=max(f[p[h2]],query(z[p[h2]]-1)+1),h2++;

	}

	for(i=l;i<=mid;i++)	clr(z[p[i]]);

	sort(p+l+1,p+r+1,cmpx);

	dfs(mid+1,r);

}

int main()

{

	scanf("%lld%lld%d",&A,&P,&n);

	B=1;

	int i;

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

	{

		x[i]=pc,y[i]=pc,z[i]=pc;

		if(x[i]<y[i])	swap(x[i],y[i]);

		if(x[i]<z[i])	swap(x[i],z[i]);

		if(y[i]<z[i])	swap(y[i],z[i]);

		num[i].v=z[i],num[i].org=p[i]=i,f[i]=1;

	}

	sort(num+1,num+n+1,cmp);

	for(num[0].v=-1,i=1;i<=n;i++)

	{

		if(num[i].v>num[i-1].v)	nm++;

		z[num[i].org]=nm;

	}

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

	dfs(1,n);

	for(i=1;i<=n;i++)	ans=max(ans,f[i]);

	printf("%d",ans);

	return 0;

}

相关文章