2018-ACetic_ACid/AugTrain-11/A

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int T=1<<20, N=2e5+5;

set<int> a[T];
int sz,n,vn;
int v[N*2];

struct point {
    int x,y;
    point(int x=0,int y=0):x(x),y(y) {}
} p[N];

struct query {
    int x,y;
    int type;   
} q[N];

inline ll sqr(ll x) { return x*x; }
ll dist(const point& p,const point& q)
{
    return sqr(p.x-q.x) + sqr(p.y-q.y);
}

int pos(int x) { return lower_bound(v+1,v+vn,x)-v; }

void insert(int x,int y,int val)
{
    //printf("ins %d %d %d\n",v[x],v[y],val);
    for(x+=sz-1,y+=sz+1;x^y^1;x>>=1,y>>=1) {
        if(~x&1) a[x^1].insert(val);
        if( y&1) a[y^1].insert(val);
    }
}

void erase(int x,int y,int val)
{
    for(x+=sz-1,y+=sz+1;x^y^1;x>>=1,y>>=1) {
        if(~x&1) a[x^1].erase(val);
        if( y&1) a[y^1].erase(val);
    }
}

void insert_p(int i)
{
    p[i]=point(q[i].x,q[i].y);
    int lb=pos(p[i].x-p[i].y), ub=pos(p[i].x+p[i].y);
    insert(lb,ub,i);
}

void erase_p(int i)
{
    int lb=pos(p[i].x-p[i].y), ub=pos(p[i].x+p[i].y);
    erase(lb,ub,i);
}

int check(const point& pt,int s)
{
    //printf("check %d %d %d\n",pt.x,pt.y,s);
    for(auto i:a[s]) {
        if(dist(p[i],pt)<sqr(p[i].y)) return i;
    }
    return 0;
}

void query(const point& pt)
{
    int s=upper_bound(v+1,v+vn,pt.x)-v;
    //printf("x=%d %d~%d\n",pt.x,v[s-1],v[s]);
    for(s+=sz;s;s>>=1) if(!a[s].empty()) {
        int ch=check(pt,s);
        if(ch) {
            printf("%d\n",ch);
            erase_p(ch);
            return;
        }
    }
    puts("-1");
}

int main()
{
    int i;
    scanf("%d",&n);
    vn=0;
    for(i=1;i<=n;i++) {
        scanf("%d%d%d",&q[i].type,&q[i].x,&q[i].y);
        if(q[i].type==1) {
            v[++vn]=q[i].x-q[i].y;
            v[++vn]=q[i].x+q[i].y;
        }
    }
    sort(v+1,v+vn+1);
    vn=unique(v+1,v+vn+1)-v;

    for(sz=1;sz<=vn;sz<<=1);

    for(i=1;i<=n;i++) {
        if(q[i].type==1) insert_p(i);
        else query(point(q[i].x,q[i].y));
    }
}
}}}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int T=1<<20, N=2e5+5;
set<int> a[T];
int sz,n,vn;
int v[N*2];
struct point {
    int x,y;
    point(int x=0,int y=0):x(x),y(y) {}
} p[N];
struct query {
    int x,y;
    int type;   
} q[N];
inline ll sqr(ll x) { return x*x; }
ll dist(const point& p,const point& q)
{
    return sqr(p.x-q.x) + sqr(p.y-q.y);
}
int pos(int x) { return lower_bound(v+1,v+vn,x)-v; }
void insert(int x,int y,int val)
{
    //printf("ins %d %d %d\n",v[x],v[y],val);
    for(x+=sz-1,y+=sz+1;x^y^1;x>>=1,y>>=1) {
        if(~x&1) a[x^1].insert(val);
        if( y&1) a[y^1].insert(val);
    }
}
void erase(int x,int y,int val)
{
    for(x+=sz-1,y+=sz+1;x^y^1;x>>=1,y>>=1) {
        if(~x&1) a[x^1].erase(val);
        if( y&1) a[y^1].erase(val);
    }
}
void insert_p(int i)
{
    p[i]=point(q[i].x,q[i].y);
    int lb=pos(p[i].x-p[i].y), ub=pos(p[i].x+p[i].y);
    insert(lb,ub,i);
}
void erase_p(int i)
{
    int lb=pos(p[i].x-p[i].y), ub=pos(p[i].x+p[i].y);
    erase(lb,ub,i);
}
int check(const point& pt,int s)
{
    //printf("check %d %d %d\n",pt.x,pt.y,s);
    for(auto i:a[s]) {
        if(dist(p[i],pt)<sqr(p[i].y)) return i;
    }
    return 0;
}
void query(const point& pt)
{
    int s=upper_bound(v+1,v+vn,pt.x)-v;
    //printf("x=%d %d~%d\n",pt.x,v[s-1],v[s]);
    for(s+=sz;s;s>>=1) if(!a[s].empty()) {
        int ch=check(pt,s);
        if(ch) {
            printf("%d\n",ch);
            erase_p(ch);
            return;
        }
    }
    puts("-1");
}
int main()
{
    int i;
    scanf("%d",&n);
    vn=0;
    for(i=1;i<=n;i++) {
        scanf("%d%d%d",&q[i].type,&q[i].x,&q[i].y);
        if(q[i].type==1) {
            v[++vn]=q[i].x-q[i].y;
            v[++vn]=q[i].x+q[i].y;
        }
    }
    sort(v+1,v+vn+1);
    vn=unique(v+1,v+vn+1)-v;
    for(sz=1;sz<=vn;sz<<=1);
    for(i=1;i<=n;i++) {
        if(q[i].type==1) insert_p(i);
        else query(point(q[i].x,q[i].y));
    }
}