题目大意：
一个三维空间，如果球A 能 碰撞到 球B 要求A的三维的坐标都小于等于 B的坐标，A球撞到B求之后A球就消失了，问你最后n个球最多碰多少次，而且有多少种方式能达到这个数量。
思路：
可以联想到的是二维的这样的题目。
如果是三维的话，就用排序x去掉一维。
然后我们要找到 y z。然后对于一个区间上，我们对y排序，但是在排序之前记录下此时的id
排序之后，就能得到y的递增，但是此时可能打乱了x的顺序。所以我们就要利用之前记录的id
id小的也就是x小，那么此时我们就能找到xy的大小关系，然后我们将z离散化之后建一个bit树。
在之前排序的y区间左子树的可以直接加进去。不用更新，因为 如果dp[i-1]<=dp[i]
但是对于右子树，不仅要加进去 而且还要更新。
这样x小的都去左子树了，大的都到右子树去了。而且是按照y的增序加进去的。
而且后面的x一定比前面的x要大。所以这样就可以保证 x y都是有序进去的。
最后在看1-z之间有多少个，更新一下就好了
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define lowbit(x) (x&(-x))
using namespace std;
const int N = 100005;
typedef pair<int,int>P;
struct node
{
int x,y,z,id;
bool operator < (const node &cmp)const{
if(x!=cmp.x)return x<cmp.x;
if(y!=cmp.y)return y<cmp.y;
return z<cmp.z;
}
}a[N],b[N];
int save[N],x[N],m,n;
P dp[N],tre[N];
void init()
{
for(int i=1;i<=m;i++)tre[i]=make_pair(0,0);
}
void update(P &a,P b)
{
if(a.first<b.first)a=b;
else if(b.first==a.first)a.second+=b.second;
}
void add(int idx,P val)
{
for(int i=idx;i<=m;i+=lowbit(i))
{
update(tre[i],val);
}
}
void clear(int idx)
{
for(int i=idx;i<=m;i+=lowbit(i))
tre[i]=make_pair(0,0);
}
P query(int idx)
{
P ans=make_pair(0,0);
for(int i=idx;i>0;i-=lowbit(i))
{
update(ans,tre[i]);
}
return ans;
}
void solve(int l,int r)
{
if(l==r)return;
int mid=(l+r)>>1;
solve(l,mid);
int cnt=0;
for(int i=l;i<=r;i++)
{
b[cnt]=a[i];
b[cnt++].x=0;
}
sort(b,b+cnt);
for(int i=0;i<cnt;i++)
{
if(b[i].id<=mid)
{
add(b[i].z,dp[b[i].id]);
}
else
{
P t=query(b[i].z);
t.first++;
update(dp[b[i].id],t);
}
}
for(int i=0;i<cnt;i++)
{
if(b[i].id<=mid)
clear(b[i].z);
}
solve(mid+1,r);
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
x[i]=a[i].z;
dp[i]=make_pair(1,1);
}
sort(x,x+n);
m=unique(x,x+n)-x;
for(int i=0;i<n;i++)
{
a[i].z=lower_bound(x,x+m,a[i].z)-x+1;
}
sort(a,a+n);
for(int i=0;i<n;i++)a[i].id=i;
init();
solve(0,n-1);
P ans=make_pair(0,0);
for(int i=0;i<n;i++)
{
update(ans,dp[i]);
}
printf("%d %d\n",ans.first,ans.second);
}
return 0;
}
hdu 4742 Pinball Game 3D （BIT + 分治）,布布扣,bubuko.com
hdu 4742 Pinball Game 3D （BIT + 分治）
原文：http://blog.csdn.net/u010709592/article/details/21182851