【题解】CF44G Shooting Gallery

题目大意

给定\(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;
}