题意：二维平面上 N 个高度为 Hi 建筑物，M次询问，每次询问输出 位于坐标（x ，y）左下角（也就是xi <= x && yi <= y）的建筑物中的第k高的建筑物的高度，如果不存在输出-1.
思路：可以发现k很小，最大才是10。对于区间第k大的问题，如果k很小的话，线段树也是可以的，，当然这里要用到 区间合并，对于每个节点 记录其 孩子中 前2*k个高度（不一定非要2*k，只要大于k就可以，至于为什么，自己可以想想），进行合并排序。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std; const int maxn = 3e4+;
struct Building
{
int x,y,flag,k,idx;
Building (){}
Building (int _x,int _y,int _z): x(_x),y(_y),k(_z){}
bool operator < (const Building &rhs)const
{
return x < rhs.x || (x == rhs.x && y < rhs.y) ||
(x == rhs.x && y == rhs.y && flag < rhs.flag);
}
}bui[maxn<<];
struct Seg_tree
{
int sum,num[];
Seg_tree (){sum = ;}
}seg[maxn<<]; //正常来说4倍就够了，可是这题不是maxn而是2*maxn，所以要(2*maxn)*4倍
int vec[maxn*],ans[maxn*];
void build (int l,int r,int pos)
{
seg[pos].sum = ;
if (l == r)
return;
int mid = (l + r) >> ;
build(l,mid,pos<<);
build(mid+,r,pos<<|);
}
void _sort(int pos)
{
sort(seg[pos].num,seg[pos].num+seg[pos].sum);
seg[pos].sum = min(,seg[pos].sum);
}
void push_up(int pos)
{
int tot = ;
for (int i = ; i < seg[pos<<].sum; i++)
seg[pos].num[tot++] = seg[pos<<].num[i];
for (int i = ; i < seg[pos<<|].sum; i++)
seg[pos].num[tot++] = seg[pos<<|].num[i];
seg[pos].sum = tot;
_sort(pos);
}
void update(int l,int r,int pos,int p,int val)
{
if (l == r)
{
seg[pos].num[seg[pos].sum++] = val;
_sort(pos); //对当前节点内的高度进行排序
return;
}
int mid = (l + r) >> ;
if (p <= mid)
update(l,mid,pos<<,p,val);
else
update(mid+,r,pos<<|,p,val);
push_up(pos); //左右孩子合并 取出前10个高度
}
int pre_ans[],siz;
void query(int l,int r,int pos,int ua,int ub)
{
if (ua <= l && ub >= r)
{
for (int i = ; i < seg[pos].sum; i++)
pre_ans[siz++] = seg[pos].num[i];
sort(pre_ans,pre_ans+siz);
siz = min(,siz);
return;
}
int mid = (l + r) >> ;
if (ua <= mid)
query (l,mid,pos<<,ua,ub);
if (ub > mid)
query (mid+,r,pos<<|,ua,ub);
}
int main(void)
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
int n,m;
while (~scanf ("%d%d",&n,&m))
{
int tot = ;
for (int i = ; i < n + m ; i++)
{
int u,v,c;
scanf ("%d%d%d",&u,&v,&c);
bui[i] = Building (u,v,c);
if (i < n)
bui[i].flag = ;
else
bui[i].flag = ;
vec[tot++] = v;
bui[i].idx = i;
}
sort(vec,vec+tot);
sort(bui,bui+n+m);
tot = unique(vec, vec + tot) - vec;
build(,tot,);
for (int i = ; i < n + m; i++)
{
int p = + lower_bound(vec,vec+tot,bui[i].y) - vec;
if (bui[i].flag == )
update(,tot,,p,bui[i].k);
else
{
siz = ;
query(,tot,,,p);
if (bui[i].k > siz)
ans[bui[i].idx] = -;
else
ans[bui[i].idx] = pre_ans[bui[i].k-];
}
}
for (int i = n; i < n + m; i++)
printf("%d\n",ans[i]);
}
return ;
}