题目链接：

题意：

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

题解：

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

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

1 #include
      
        2 #define F(i,a,b) for(int i=a;i<=b;i++) 3 using namespace std; 4 typedef pair
       
        P; 5  6 const int N=1e5+7,mod=1<<30; 7 int t,n,hsh_ed,hsh[N]; 8 P sum[N],dp[N]; 9 10 struct node11 {12     int x,y,z,id;13     bool operator <(const node & b)const{
    return x
        
         
          
           >1;29     cdq(l,mid);30     F(i,l,r)b[i]=a[i],b[i].x=0;31     sort(b+l,b+1+r);32     F(i,l,r)33     {34         if(b[i].id<=mid)add(b[i].z,dp[b[i].id]);35         else36         {37             P now=ask(b[i].z);38             if(now.first+1>dp[b[i].id].first)dp[b[i].id]=P(now.first+1,now.second);39             else if(now.first+1==dp[b[i].id].first)dp[b[i].id].second+=now.second;40         }41     }        42     F(i,l,r)if(b[i].id<=mid)back(b[i].z);43     cdq(mid+1,r);44 }45 46 int main()47 {48     scanf("%d",&t);49     while(t--)50     {51         scanf("%d",&n),hsh_ed=0;52         F(i,1,n)53         {54             scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);55             hsh[i]=a[i].z;56         }57         sort(a+1,a+1+n);58         sort(hsh+1,hsh+1+n),hsh_ed=unique(hsh+1,hsh+1+n)-hsh;59         F(i,1,n)60         {61             dp[i]=P(1,1),a[i].id=i;62             a[i].z=lower_bound(hsh+1,hsh+1+hsh_ed,a[i].z)-hsh;63         }64         cdq(1,n);65         P ans=P(0,0);66         F(i,1,n)up(ans,dp[i]);67         printf("%d %d\n",ans.first,ans.second%mod);68     }69     return 0;70 }