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 pairP;
struct node
{
    int x,y,z,id;
    bool operator < (const node &cmp)const{
        if(x!=cmp.x)return x0;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