Gym101630A Archery Tournament

题目链接：https://vjudge.net/problem/Gym-101630A

题目大意：

　　有\(n\)个操作，每次输入\(t\) \(x\) \(y\)\((t=1,2; -10^9 \le x,y \le 10^9; y > 0)\). 当\(t=1\)，在坐标平面上立一个圆心在\(x,y\)，半径为\(y\)的圆形靶子。当\(t=2\)，往点\(x,y\)射一箭，如果在这个点上有靶子，则输出这个靶子是在第几次操作中出现的，并把这个靶子销毁；如果这个点上没有靶子，则输出\("-1"\)。

知识点：　　线段树、离散化

解题思路：

　　首先，肯定要离散化处理数据。然后用线段树套\(<set>\)（目的是方便删除操作）维护区间中有什么靶子。更新和删除的时候只要找到合适的区间就可以进行操作然后\(return\)，不用\(push\) \(up\)或\(push\) \(down\)，查询的时候则直到找到合适的靶子或者\(l==r\)为止。

AC代码：

 #include <bits/stdc++.h>

 using namespace std;

 #define lson l,m,rt<<1

 #define rson m+1,r,rt<<1|1

 typedef pair<int,int> P;

 typedef long long ll;

 const int maxn=2e5+;

 struct Input{

     int t;

     ll x,y;

 }inp[maxn];

 ll xs[maxn<<];

 map<ll,int> ind;

 set<int> tree[maxn<<];

 void update(int L,int R,int c,int l,int r,int rt){

     if(L<=l&&r<=R){

         tree[rt].insert(c);

         return;

     }

     int m=(l+r)>>;

     if(L<=m)    update(L,R,c,lson);

     if(R>m)     update(L,R,c,rson);

 }

 void era(int L,int R,int c,int l,int r,int rt){

     if(L<=l&&r<=R){

         tree[rt].erase(c);

         return;

     }

     int m=(l+r)>>;

     if(L<=m)    era(L,R,c,lson);

     if(R>m)     era(L,R,c,rson);

 }

 int query(int pos,int _x,int _y,int l,int r,int rt){

     if(l<=pos&&pos<=r){

         set<int>::iterator it=tree[rt].begin();

         for(;it!=tree[rt].end();it++){

             int now=*it;

             if((inp[now].x-_x)*(inp[now].x-_x)+(inp[now].y-_y)*(inp[now].y-_y)<inp[now].y*inp[now].y)

                 return now;

         }

     }

     if(l==r)    return -;

     int m=(l+r)>>;

     if(pos<=m)    return query(pos,_x,_y,lson);

     else     return query(pos,_x,_y,rson);

 }

 int main(){

 //    freopen("in.txt","r",stdin);

     int n,cnt=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d%lld%lld",&inp[i].t,&inp[i].x,&inp[i].y);

         if(inp[i].t==)

             xs[cnt++]=inp[i].x-inp[i].y,xs[cnt++]=inp[i].x+inp[i].y;

     }

     sort(xs,xs+cnt);

     int m=unique(xs,xs+cnt)-xs;

     for(int i=;i<m;i++){

         ind[xs[i]]=i;

     }

     for(int i=;i<=n;i++){

         if(inp[i].t==)

             update(ind[inp[i].x-inp[i].y]+,ind[inp[i].x+inp[i].y],i,,m-,);

         else{

             int pos=-;

             int l=,r=m-;

             while(l<=r){

                 int mid=(l+r)>>;

                 if(xs[mid-]>inp[i].x)   r=mid-;

                 else if(xs[mid]<inp[i].x)  l=mid+;

                 else{

                     pos=mid;

                     break;

                 }

             }

             if(pos==-) printf("-1\n");

             else{

                 int ret=query(pos,inp[i].x,inp[i].y,,m-,);

                 if(ret==-)

                     printf("-1\n");

                 else{

                     printf("%d\n",ret);

                     era(ind[inp[ret].x-inp[ret].y]+,ind[inp[ret].x+inp[ret].y],ret,,m-,);

                 }

             }

         }

     }

     return ;

 }

巴特西

Gym101630A Archery Tournament

最新文章

热门文章