题解：CF44G Shooting Gallery

· · 题解

题意

给定 n 个水平平面，平面有高度 z，不存在两个高度相同的平面，每次删掉包含点 (x,y)，且高度最小的平面，问删除的平面编号。

解法

由于题目涉及二维平面问题，考虑使用 2d-tree 处理，但 2d-tree 适合查询平面包含的点，而不是包含点的平面。考虑到 z 较小的平面会被优先删除，于是我们充分发扬人类智慧，用 2d-tree 存操作点（即删除操作给定的点），将平面按 z 升序排序处理，处理时找到平面包含的最先操作的操作点，将此点对应操作删除的平面记录为此平面，并删掉此操作点。

我们对所有操作点建 2d-tree，删除操作点时删点会比较麻烦，其实打 tag 即可。

这样做时间复杂度 \operatorname{O}(n\sqrt n)。

没错，就是这么简单。

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100009,M = 100009;
struct tar{
    int xmn,xmx,ymx,ymn,z,id;
    bool operator<(const tar &b)const{
        return z < b.z;
    } 
}t[N];
int sid[M];
struct kdtree{
    int x,y,xmn = 0x3f3f3f3f,ymn = 0x3f3f3f3f,xmx = -1,ymx = -1,t = 0x3f3f3f3f,mid;
    int lc,rc;
    bool dt;
}nd[M];
bool cmp1(kdtree tx,kdtree ty){
    return tx.x < ty.x;
}
bool cmp2(kdtree tx,kdtree ty){
    return tx.y < ty.y;
}
int build(int l,int r,int k){
    if(l > r)
        return 0;
    if(l == r){
        nd[l].xmn = nd[l].x;
        nd[l].ymn = nd[l].y;
        nd[l].xmx = nd[l].x;
        nd[l].ymx = nd[l].y;
        nd[l].mid = l;
        return l;
    }
    int u = (l + r) >> 1;
    nth_element(nd + l,nd + u,nd + r + 1,k == 0 ? cmp1 : cmp2);
    //printf(" %d %d\n",l,r); 
    nd[u].lc = build(l,u - 1,k ^ 1);
    nd[u].rc = build(u + 1,r,k ^ 1);
    //printf("%d %d\n",nd[u].x,nd[u].y);
    nd[u].xmn = min(nd[u].x,min(nd[nd[u].lc].xmn,nd[nd[u].rc].xmn));
    nd[u].ymn = min(nd[u].y,min(nd[nd[u].lc].ymn,nd[nd[u].rc].ymn));
    nd[u].xmx = max(nd[u].x,max(nd[nd[u].lc].xmx,nd[nd[u].rc].xmx));
    nd[u].ymx = max(nd[u].y,max(nd[nd[u].lc].ymx,nd[nd[u].rc].ymx));
    nd[u].mid = u;
    if(nd[nd[u].mid].t > nd[nd[nd[u].lc].mid].t)
        nd[u].mid = nd[nd[u].lc].mid;
    if(nd[nd[u].mid].t > nd[nd[nd[u].rc].mid].t)
        nd[u].mid = nd[nd[u].rc].mid;
    //printf("%d %d %d %d\n",nd[u].xmn,nd[u].ymn,nd[u].xmx,nd[u].ymx);
    return u;
}
void kill(int k,int px,int py,int pt){
    if(nd[k].xmn > px || nd[k].xmx < px || nd[k].ymn > py || nd[k].ymx < py)
        return;
    if(nd[k].x == px && nd[k].y == py && nd[k].t == pt){
        nd[k].dt = true;
        nd[k].x = 0x3f3f3f3f,nd[k].y = 0x3f3f3f3f,nd[k].t = 0x3f3f3f3f;
        nd[k].xmn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].x,min(nd[nd[k].lc].xmn,nd[nd[k].rc].xmn));
        nd[k].ymn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].y,min(nd[nd[k].lc].ymn,nd[nd[k].rc].ymn));
        nd[k].xmx = max(nd[k].dt ? -1 : nd[k].x,max(nd[nd[k].lc].xmx,nd[nd[k].rc].xmx));
        nd[k].ymx = max(nd[k].dt ? -1 : nd[k].y,max(nd[nd[k].lc].ymx,nd[nd[k].rc].ymx));
        nd[k].mid = 0;
        if(nd[nd[k].mid].t > nd[nd[nd[k].lc].mid].t)
            nd[k].mid = nd[nd[k].lc].mid;
        if(nd[nd[k].mid].t > nd[nd[nd[k].rc].mid].t)
            nd[k].mid = nd[nd[k].rc].mid;
        return;
    }
    kill(nd[k].lc,px,py,pt);
    kill(nd[k].rc,px,py,pt);
    nd[k].xmn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].x,min(nd[nd[k].lc].xmn,nd[nd[k].rc].xmn));
    nd[k].ymn = min(nd[k].dt ? 0x3f3f3f3f : nd[k].y,min(nd[nd[k].lc].ymn,nd[nd[k].rc].ymn));
    nd[k].xmx = max(nd[k].dt ? 0 : nd[k].x,max(nd[nd[k].lc].xmx,nd[nd[k].rc].xmx));
    nd[k].ymx = max(nd[k].dt ? 0 : nd[k].y,max(nd[nd[k].lc].ymx,nd[nd[k].rc].ymx));
    nd[k].mid = k;
    if(nd[nd[k].mid].t > nd[nd[nd[k].lc].mid].t)
        nd[k].mid = nd[nd[k].lc].mid;
    if(nd[nd[k].mid].t > nd[nd[nd[k].rc].mid].t)
        nd[k].mid = nd[nd[k].rc].mid;
    return;
}
int kid;
void fnd(int k,int qs){
    //printf("%d %d %d %d %d %d %d %d\n",t[qs].xmn,t[qs].ymn,t[qs].xmx,t[qs].ymx,nd[k].xmn,nd[k].ymn,nd[k].xmx,nd[k].ymx);
    if(t[qs].xmn > nd[k].xmx || t[qs].xmx < nd[k].xmn || t[qs].ymn > nd[k].ymx || t[qs].ymx < nd[k].ymn || nd[k].mid == 0)
        return;
    if(t[qs].xmx >= nd[k].xmx && t[qs].xmn <= nd[k].xmn && t[qs].ymx >= nd[k].ymx && t[qs].ymn <= nd[k].ymn){
        if(nd[kid].t > nd[nd[k].mid].t)
            kid = nd[k].mid;
        return;
    }
    else if(t[qs].xmx >= nd[k].x && t[qs].xmn <= nd[k].x && t[qs].ymx >= nd[k].y && t[qs].ymn <= nd[k].y){
        if(nd[kid].t > nd[k].t)
            kid = k;
    }
    fnd(nd[k].lc,qs);
    fnd(nd[k].rc,qs);
}
int n,m;
int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i ++){
        scanf("%d %d %d %d %d",&t[i].xmn,&t[i].xmx,&t[i].ymn,&t[i].ymx,&t[i].z);
        t[i].id = i;
    }
    sort(t + 1,t + n + 1);
    scanf("%d",&m);
    for(int i = 1; i <= m; i ++){
        scanf("%d %d",&nd[i].x,&nd[i].y);
        nd[i].t = i;
    }
    int rt = build(1,m,0);
    for(int i = 1; i <= n; i ++){
        kid = 0;
        fnd(rt,i);
        //printf("%d\n",nd[kid].t);
        if(kid != 0){
            sid[nd[kid].t] = t[i].id;
            kill(rt,nd[kid].x,nd[kid].y,nd[kid].t);
        }
    }
    for(int i = 1; i <= m; i ++)
        printf("%d\n",sid[i]);
    return 0;
}