题解 CF44G 【Shooting Gallery】
Leianha
·
·
题解
博客阅读
我们考虑用靶子来匹配射击点，可以把靶子按 z 从小到大排序后，依次寻找范围内的编号最小的射击点，并将其删除，正确性显然。
考虑如何优化这个过程，实际上我们的操作分为两种:
$2.$ 在二维平面内删除点。
可以把射击点建出 $KDtree$ ，然后维护查询和删除 ，具体实现可以看代码。
```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#define lson tr[k].ls
#define rson tr[k].rs
using namespace std;
int n, m, root, cnt, nowk, ans;
const int N = 100010, inf = 1e8;
int fa[N], pos[N], Ans[N];
struct mb
{
int xl, yl, xr, yr, z, id;
friend bool operator <(const mb &a, const mb &b)
{return a.z < b.z;}
} B[N];
struct sj
{
int x, y, id;
friend bool operator <(const sj &a, const sj &b)
{return nowk ? a.x < b.x : a.y < b.y;}
} S[N];
struct shu
{
int mn, id, x, y, minx, miny, maxx, maxy, ls, rs;
} tr[N];
void pushup(int k)
{
tr[k].mn = tr[k].id;
if (lson)
{
tr[k].mn = min(tr[k].mn, tr[lson].mn);
tr[k].minx = min(tr[k].minx, tr[lson].minx); tr[k].miny = min(tr[k].miny, tr[lson].miny);
tr[k].maxx = max(tr[k].maxx, tr[lson].maxx); tr[k].maxy = max(tr[k].maxy, tr[lson].maxy);
}
if (rson)
{
tr[k].mn = min(tr[k].mn, tr[rson].mn);
tr[k].minx = min(tr[k].minx, tr[rson].minx); tr[k].miny = min(tr[k].miny, tr[rson].miny);
tr[k].maxx = max(tr[k].maxx, tr[rson].maxx); tr[k].maxy = max(tr[k].maxy, tr[rson].maxy);
}
}
void build(int FA, int &k, int l, int r, int KD)
{
if (l > r)return;
int mid = (l + r) >> 1; k = ++cnt; nowk = KD;
nth_element(S + l, S + mid, S + r + 1);
pos[S[mid].id] = k; fa[k] = FA;
tr[k].id = tr[k].mn = S[mid].id;
tr[k].x = tr[k].minx = tr[k].maxx = S[mid].x;
tr[k].y = tr[k].miny = tr[k].maxy = S[mid].y;
build(k, lson, l, mid - 1, KD ^ 1); build(k, rson, mid + 1, r, KD ^ 1);
pushup(k);
}
void ask(int k, int xl, int yl, int xr, int yr)
{
if (tr[k].maxx < xl || xr < tr[k].minx || tr[k].maxy < yl || yr < tr[k].miny)return;
if (xl <= tr[k].minx && tr[k].maxx <= xr && yl <= tr[k].miny && tr[k].maxy <= yr) {ans = min(ans, tr[k].mn); return;}
if (tr[k].id != inf && xl <= tr[k].x && tr[k].x <= xr && yl <= tr[k].y && tr[k].y <= yr) {ans = min(ans, tr[k].id);}
if (lson)ask(lson, xl, yl, xr, yr);
if (rson)ask(rson, xl, yl, xr, yr);
}
void shan(int x)
{
tr[x].id = inf;
while (x)
{
pushup(x);
x = fa[x];
}
}
int main()
{
cin >> n;
for (int i = 1, xl, xr, yl, yr, z; i <= n; ++i)
{
scanf("%d%d%d%d%d", &xl, &xr, &yl, &yr, &z);
B[i] = (mb) {xl, yl, xr, yr, z, i};
}
cin >> m;
for (int i = 1; i <= m; ++i)
scanf("%d%d", &S[i].x, &S[i].y), S[i].id = i;
build(0, root, 1, m, 0);
sort(B + 1, B + 1 + n);
for (int i = 1; i <= n; ++i)
{
ans = inf; ask(root, B[i].xl, B[i].yl, B[i].xr, B[i].yr);
if (ans != inf)
{
Ans[ans] = B[i].id;
shan(pos[ans]);
}
}
for (int i = 1; i <= m; ++i)printf("%d\n", Ans[i]);
return 0;
}
```