前言
一個感覺特别單一的資料結構啊，Po大爺才寫兩個這個題呢。
然後仔細研究了一下KD-TREE為什麼要這樣做，發現其中的每一個操作都是很巧妙的。
原理簡述（瞎逼逼）
KD-Tree确實應該算是計算幾何的一種東西了吧，可以看作線段樹的高維推廣還自帶離散功能。
KD-Tree也是一個二叉樹，并且除了葉子結點外，每個結點都代表了一堆點，葉子結點則代表了一個，和線段樹是很像的。
每個點我們要維護它的各個坐标的最大值以及最小值，這是有利于後面的搜尋操作的。
它的分割原則是對于一個K維的一些點，用一個超平面（k-1維）來把這堆點分割成平均的兩部分，如何平均，用一些STL的nth_element函數就可以了（下面有介紹）
在分割的時候，我們根據不同的層數，不停的轉變被分割的那一維，本來一直用一維也是可以的，但是對于接下來的搜尋操作就不是很有利了。
現在講一下一個搜尋操作：對于一個結點，我們要找最大值/最小值，就按照我們對于一堆點坐标最值來貪心地去選擇順序搜尋，并且及時剪枝，是以這似乎就是一個優雅的暴力。不過權威證明，它的時間複雜度是O(n^1/2),并且在實際運作中跑得賊快。這裡也可以看我們為什麼要不停換次元分割，我們讓一堆點盡量存在在一個比較‘方’的區間裡面，有利于我們的搜尋。（仔細體會一下嘛）
插入操作就按照劃分方式往下放就行了，但是由于插入過多可能不平衡，是以我們可以利用替罪羊樹的思想在一定情況下進行暴力重構。
時間複雜度的話：
建樹是O(nlogn)
其它大概都是O(logn)
搜尋是O(n^（1-（1/k））)但是實際效果好很多
再談KD-Tree
KD-Tree的時間複雜度随着次元升高并不是線性增長的，一般二維還是sqrt(n)的級别，那麼和log^2(n)，基本上是沒有差距的，但是更高緯度可能就不行了，是以最好是保證在二維之内，KDTree的維護有兩個方式，一個是暴力重構，一個是一來就把資料全部建好。
然而KD-Tree找距離是可以被卡成O(n)的，但是毒瘤出題人要是偏要故意卡那就認了呗。不過一般資料結構不知道能不能卡。
資料的限制一般是很難降維的，畢竟咱不是三體，是以一旦分析除了，最好不要嘗試降維，而是找合适的資料結構。
KD-Tree查找時間複雜度的由來：由于為了貪心查找距離，是以我們要求目前空間盡量方，這樣比較好找，但是就會出現一個區間本來都抵滿了還要被繼續分割的情況，是以是比logn^2要大一些的，而且次元越高越大。
關于次元的選擇，不要覺得隻是拿來玩的，由于不同次元可能有不同的性質，比如區間加法或者，
是以遇到二維以内的線上問題就直接上KD-Tree吧， 也就是說懶得去寫樹套樹了，但是次元更高就嘗試用其它方法降維，比如二分、可持久化，如果可以用莫隊，CDQ什麼的也不要用KD-Tree，因為KD-Tree時間複雜度不好保證。
注意二分也是可以降維的東西。
一般來說sqrt(n)的算法都是可以代替兩個log的，是以懶的話就多考慮下sqrt(n)算法吧。
介紹一個STL函數:nth_element
用法介紹:nth_element(a+1,a+n,a+m+1)
含義：就是把a數組第n大的元素放在第n個位置，并且比n小的在n前面，比n大的在n後面
時間複雜度：元素較多大概是O(n)，較少/最壞時間複雜度是O(n^2)，是一種很高效的算法了。
說說題目
感覺題目都比較裸的啊。。
要不刷刷我們市的省選題吧。。
代碼
先寫幾個KDtree注意的點
1、mx和mi兩個在估價的時候同時要用，不要以為找最大值就不用mi了，可能負數呢，是以不要忘了abs。
2、D那個排序的全局變量隻能放在結構體外面，因為結構體内部的東西不一定被定義了的。
3、特别注意估價函數以及查詢的寫法，KD-tree的核心了吧。
其實這個算法非常好實作，大概有了思路就可以自己寫出來了。
KD-Tree再次了解:
- 不要把KDtree當成線段樹用，最好當成平衡樹寫，不過本人這種懶人可以寫lc，rc而不是ch。
- 隻有在建樹的時候才需要用到超平面分割，查詢的時候是不用的。
- 要注意每個結點都代表了一個元素，是以注意要把這個元素統計進去。
- 建樹的時候L>R的時候則傳回
- 查詢的時候要特判四種情況，一個是目前點不存在，一個是不包含傳回，一個是包含upd之後再傳回，一個是判斷是否包含目前點。
- 查詢的時候必須使用貪心政策查詢，不然就不是KD-Tree。
- 特别注意不包含關系，隻有有任何一維不包含就算是不包含了，而包含需要所有次元包含。
int D;
struct data{
int d[],w;//l,r是實際有效閉區間
friend bool operator<(data a,data b)
{
return a.d[D]<b.d[D];
}
}p[maxn];
struct KD_Tree
{
int rt,np,lc[maxn],rc[maxn],mx[maxn][],mi[maxn][],maxv[maxn];
void pushup(int now)
{
if(lc[now])
{
maxv[now]=max(maxv[now],maxv[lc[now]]);
for(int i=;i<;i++)
{
mx[now][i]=max(mx[now][i],mx[lc[now]][i]);
mi[now][i]=min(mi[now][i],mi[lc[now]][i]);
}
}
if(rc[now])
{
maxv[now]=max(maxv[now],maxv[rc[now]]);
for(int i=;i<;i++)
{
mx[now][i]=max(mx[now][i],mx[rc[now]][i]);
mi[now][i]=min(mi[now][i],mi[rc[now]][i]);
}
}
}
int Newnode(int x)
{
++np;
maxv[np]=p[x].w;
for(int i=;i<;i++)
mx[np][i]=mi[np][i]=p[x].d[i];
return np;
}
void Build(int &now,int L,int R,int k)
{
if(L>R)return;
int m=(L+R)>>;
D=k;
nth_element(p+L,p+m,p+R+);
now=Newnode(m);
Build(lc[now],L,m-,(k+)%);
Build(rc[now],m+,R,(k+)%);
pushup(now);
}
bool calc1(int now,data i,data j)//如果now完全在ij外就傳回1
{
for(int k=;k<;k++)
{
if(mx[now][k]<i.d[k] || j.d[k]<mi[now][k])
return ;
}
return ;
}
bool calc2(int now,data i,data j)//如果i，j包含了now就傳回1
{
for(int k=;k<;k++)
{
if(!(i.d[k]<=mi[now][k] && mx[now][k]<=j.d[k]))
return ;
}
return ;
}
bool calc(data x,data i,data j)
{
for(int k=;k<;k++)
{
if(!(i.d[k]<=x.d[k] && x.d[k]<=j.d[k]))
return ;
}
return ;
}
void query(int now,int L,int R,data i,data j)
{
if(!now)return;
if(maxv[now]<=ret)return;
if(calc1(now,i,j))return;
if(calc2(now,i,j)){ret=maxv[now];return;}
int m=(L+R)>>;
if(calc(p[m],i,j))
ret=max(ret,p[m].w);
if(maxv[lc[now]]>maxv[rc[now]])
{
query(lc[now],L,m-,i,j);
query(rc[now],m+,R,i,j);
}
else
{
query(rc[now],m+,R,i,j);
query(lc[now],L,m-,i,j);
}
}
}kd;