hdu 5107 这题说的是给了一个二维的 平面， 平面内有30000个点每个点都有自己的高度，然后又30000次的查询，每次查询给的是(X,Y,K), 要求出set(x,y){x,y|x<=X&&y<=Y } 的所有点，中第K 大的数是多少，存在输出该高度，允许重复； 否者输出-1，。
本来想用主席树做，发现，找前节点还是比较麻烦的。再加上k<=10 还是比较小的， 然后我们按照y设置为线段树的页节点，然后发现每个页节点最多存10种高度，然后他们的父节点只需要合并孩子的两个长度为10的高度数组， 我们将所有的点包括询问的点进行离散化，按x按y从小到大排序， 离散化后查询在数组中， 保证了x一定小于等于当前要插入或者是查询的点，这样就可以减少对于x的处理，然后接下来就是让该点的y找到相应的叶节点，然后用该建筑物的h更新叶节点。 如果是查询就查寻（1，IDX（P[i].y））
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <vector>
using namespace std;
const int maxn=;
typedef int ll;
struct point{
ll x,h[];
}AN;
struct build{
ll x,y,h;
ll id,op;
bool operator < ( const build A ) const {
return x<A.x||(x==A.x&&y<A.y)||(x==A.x&&y==A.y&&op<A.op)||(x==A.x&&y==A.y&&op==A.op&&id<A.id);
}
}P[maxn*];
ll Y[maxn*];
ll ans[maxn];
ll Va,loc,cL,cR,tim;
struct Itree{
point V[maxn**];
void build(int o,int L, int R){
V[o].x=;
if(L==R) return ;
int mid =(L+R)/;
build(o*, L, mid );
build(o*+, mid+, R);
}
void inser(int o ){
int i=;
for( i=; i<V[o].x; i++){
if(Va<V[o].h[i]) break;
}
if(i==) return;
for(int j = V[o].x; j>i; --j)
V[o].h[j]=V[o].h[j-];
V[o].h[i]=Va;
V[o].x=min(V[o].x+,);
}
point maintain( point o1, point o2){
point ans;
int i,j,k;
i=j=k=;
while( (i<o1.x||j<o2.x )&&( k<) ){
if(j>=o2.x ||( i<o1.x && o1.h[i]<o2.h[j] ) )
ans.h[k++] = o1.h[i++];
else ans.h[k++] = o2.h[j++];
}
ans.x=k;
return ans;
}
void update(int o, int L, int R){
if(L==R){
inser(o); return ;
}
int mid = (L+R)>>;
if(loc<=mid) update(o*,L, mid);
else update(o*+,mid+,R);
V[o]=maintain(V[o*], V[o*+]);
}
void query(int o, int L, int R){
if(cL<=L && R<= cR){
if(tim==){
tim=;
AN=V[o];
}else {
AN=maintain(AN,V[o]);
}
return ;
}
int mid = (L+R)>>;
if(cL<=mid) query(o*,L,mid);
if(cR>mid) query(o*+, mid+, R); }
}T;
int main()
{
int n,m;
while(scanf("%d%d",&n,&m)==){
for(int i=; i<n; ++i){
scanf("%d%d%d",&P[i].x,&P[i].y,&P[i].h);
P[i].id=i;
P[i].op=;
Y[i]=P[i].y;
}
for(int i=; i<m; ++i){
scanf("%d%d%d",&P[i+n].x,&P[i+n].y,&P[i+n].h);
P[i+n].id=n+i;
P[i+n].op=;
Y[i+n]=P[i+n].y;
}
sort(Y,Y+n+m);
int Ynum = unique(Y,Y+n+m)-Y;
T.build(,,Ynum);
sort(P,P+n+m);
for(int i=; i<n+m; ++i){
if(P[i].op==){
loc = lower_bound(Y,Y+Ynum,P[i].y)-Y+;
Va= P[i].h;
T.update(, , Ynum);
}else{
tim=;
cR = lower_bound(Y,Y+Ynum,P[i].y)-Y+;
cL=;
T.query(,,Ynum);
if(AN.x>=P[i].h){
ans[P[i].id-n]=AN.h[ P[i].h- ];
} else{
ans[P[i].id-n]=-;
}
}
}
for(int i=; i<m; ++i)
printf("%d\n",ans[i]);
}
return ;
}