【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;
}