题目大意
给定\(n\)个三维空间的平面，由高度\(z\)、\(x\)的范围\([xl,xr]\)和\(y\)的范围\([yl,yr]\)来表示。有\(m\)次射击，每次射击点\((x,y)\)，摧毁包含此点的\(z\)值最小的平面，输出此平面编号，若摧毁不了任何平面，输出\(0\)。
题解
点查平面不好做，于是可以转化为平面查点，先将平面按高度排序从小到大，而后查询一个平面内时间最靠前的点，将查到的点删去。
是个裸的kdt板子。
#include <bits/stdc++.h>
using namespace std;
inline int read() {
int x = 0, flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
const int MAXN = 2e5 + 50, B = 317, INF = 998244353;
int n, m, Ans[MAXN], rt, cnt = 0;
int DY[MAXN], Cl = 0;
struct Point {
int x, y, id;
} P[MAXN];
struct Ques {
int X1, Y1, X2, Y2, id, h;
} Q[MAXN];
struct Tree {
int X, Y, Min, ls, rs, dat, fa;
int mx[2], my[2];
void clean() {
X = Y = ls = rs = mx[1] = my[1] = fa = 0;
mx[0] = my[0] = dat = Min = INF;
}
} T[MAXN];
int MIN(int a, int b) { return a < b ? a : b; }
bool cmp3(Point a, Point b) { return a.y < b.y; }
bool cmp2(Point a, Point b) { return a.x < b.x; }
bool cmp(Ques a, Ques b) { return a.h < b.h; }
void update(int cur) {
T[cur].Min = MIN(T[T[cur].rs].Min, T[T[cur].ls].Min);
T[cur].Min = MIN(T[cur].Min, T[cur].dat);
T[cur].mx[0] = MIN(MIN(T[T[cur].rs].mx[0], T[T[cur].ls].mx[0]), T[cur].mx[0]);
T[cur].my[0] = MIN(MIN(T[T[cur].rs].my[0], T[T[cur].ls].my[0]), T[cur].my[0]);
T[cur].mx[1] = max(max(T[T[cur].rs].mx[1], T[T[cur].ls].mx[1]), T[cur].mx[1]);
T[cur].my[1] = max(max(T[T[cur].rs].my[1], T[T[cur].ls].my[1]), T[cur].my[1]);
}
void build(int &cur, int L, int R, int D, int fa) {
if(L > R) return ;
if(!cur) cur = ++ cnt;
int mid = (L + R) >> 1;
T[cur].fa = fa;
if(L == R) {
int x = P[L].x, y = P[L].y;
T[cur].mx[0] = T[cur].mx[1] = T[cur].X = x;
T[cur].my[0] = T[cur].my[1] = T[cur].Y = y;
T[cur].dat = T[cur].Min = P[L].id;
DY[P[L].id] = cur;
return ;
}
if(D == 0) nth_element(P + L, P + mid, P + 1 + R, cmp2);
else nth_element(P + L, P + mid, P + 1 + R, cmp3);
T[cur].dat = P[mid].id, T[cur].X = P[mid].x, T[cur].Y = P[mid].y;
T[cur].mx[0] = T[cur].mx[1] = T[cur].X;
T[cur].my[0] = T[cur].my[1] = T[cur].Y;
DY[P[mid].id] = cur;
build(T[cur].ls, L, mid - 1, D ^ 1, cur);
build(T[cur].rs, mid + 1, R, D ^ 1, cur);
update(cur); return ;
}
bool out(int x, int X1, int Y1, int X2, int Y2) { return (T[x].mx[0] > X2 || T[x].mx[1] < X1 || T[x].my[0] > Y2 || T[x].my[1] < Y1); }
bool in(int x, int X1, int Y1, int X2, int Y2) { return (T[x].mx[0] >= X1 && T[x].mx[1] <= X2 && T[x].my[0] >= Y1 && T[x].my[1] <= Y2); }
int query(int now, int X1, int Y1, int X2, int Y2) {
int Min = INF;
if(T[now].X >= X1 && T[now].Y >= Y1 && T[now].X <= X2 && T[now].Y <= Y2) Min = T[now].dat;
if(out(now, X1, Y1, X2, Y2) || !now) return Min;
if(in(now, X1, Y1, X2, Y2)) return min(T[now].Min, T[now].dat);
if(T[now].ls) Min = MIN(Min, query(T[now].ls, X1, Y1, X2, Y2));
if(T[now].rs) Min = MIN(Min, query(T[now].rs, X1, Y1, X2, Y2));
return Min;
}
void Go(int x, int t) {
if(! x) return ;
if(T[x].dat == t) T[x].dat = INF;
update(x); Go(T[x].fa, t);
return ;
}
int main() {
n = read(); T[0].clean();
for(int i = 1 ; i <= n ; i ++) Ans[i] = -1;
for(int i = 1 ; i <= n ; i ++) {
Q[i].X1 = read(), Q[i].X2 = read();
Q[i].Y1 = read(), Q[i].Y2 = read();
Q[i].h = read(), Q[i].id = i;
} rt = 0;
m = read();
sort(Q + 1, Q + 1 + n, cmp);
for(int i = 1 ; i <= m ; i ++) {
P[i].x = read(), P[i].y = read();
P[i].id = i;
}
build(rt, 1, m, 0, 0);
for(int i = 1 ; i <= n; i ++) {
int t = query(rt, Q[i].X1, Q[i].Y1, Q[i].X2, Q[i].Y2);
if(t == 998244353 || !t) continue;
Ans[t] = Q[i].id, Go(DY[t], t);
}
for(int i = 1 ; i <= m ; i ++) printf("%d\n", max(Ans[i], 0));
return 0;
}