hdu_4742_Pinball Game 3D(cdq分治+树状数组)

时间:2022-05-22 05:30:14

题目链接:hdu_4742_Pinball Game 3D

题意:

给你n个点,让你求三维的LIS,并且求出有多少种组合能达到LIS。

题解:

求三维的LIS,典型的三维偏序问题,x排序,解决一维,cdq分治y,解决一维,树状数组维护z,解决一维。

注意,cdq中sort不要调用太多,不然会被卡常。

 #include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef pair<int,int>P; const int N=1e5+,mod=<<;
int t,n,hsh_ed,hsh[N];
P sum[N],dp[N]; struct node
{
int x,y,z,id;
bool operator <(const node & b)const{return x<b.x||(x==b.x&&y<b.y)||(x==b.x&&y==b.y&&z<b.z);}
}a[N],b[N]; inline void up(P &a,P b)
{
if(a.first==b.first)a.second+=b.second;
else if(a.first<b.first)a=b;
}
inline void add(int x,P c){while(x<=hsh_ed)up(sum[x],c),x+=x&-x;}
inline P ask(int x){P an=P(,);while(x)up(an,sum[x]),x-=x&-x;return an;}
inline void back(int x){while(x<=hsh_ed)sum[x]=P(,),x+=x&-x;} void cdq(int l,int r)
{
if(l==r)return;
int mid=l+r>>;
cdq(l,mid);
F(i,l,r)b[i]=a[i],b[i].x=;
sort(b+l,b++r);
F(i,l,r)
{
if(b[i].id<=mid)add(b[i].z,dp[b[i].id]);
else
{
P now=ask(b[i].z);
if(now.first+>dp[b[i].id].first)dp[b[i].id]=P(now.first+,now.second);
else if(now.first+==dp[b[i].id].first)dp[b[i].id].second+=now.second;
}
}
F(i,l,r)if(b[i].id<=mid)back(b[i].z);
cdq(mid+,r);
} int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n),hsh_ed=;
F(i,,n)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
hsh[i]=a[i].z;
}
sort(a+,a++n);
sort(hsh+,hsh++n),hsh_ed=unique(hsh+,hsh++n)-hsh;
F(i,,n)
{
dp[i]=P(,),a[i].id=i;
a[i].z=lower_bound(hsh+,hsh++hsh_ed,a[i].z)-hsh;
}
cdq(,n);
P ans=P(,);
F(i,,n)up(ans,dp[i]);
printf("%d %d\n",ans.first,ans.second%mod);
}
return ;
}