hdu 4742 Pinball Game 3D （BIT + 分治）

题目大意：

一个三维空间，如果球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 
  
   
#include 
   
     #include 
    
      #include 
     
       #define lowbit(x) (x&(-x)) using namespace std; const int N = 100005; typedef pair
      
       P; struct node { int x,y,z,id; bool operator < (const node &cmp)const{ if(x!=cmp.x)return x
       
        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