题目链接：https://codeforces.com/group/xrTA2IaQje/contest/254939/attachments
题目大意：1表示加一个中心在x,y的靶子，半径为y，2表示往x,y射一枪，如果一个靶子都射不中输出-1，否则输出被射中的靶子是第几个操作被加入的并删除这个靶子，保证每个靶子之间没有交叉
题目思路：
方法1：
直接暴力分块，每左边x-y能到-2e9,右边能到2e9，分4e6一个块，分成1000块，然后每次都对(x-y)/4e6~(x+y)/4e6中的块都加入这个圆，每次射击就查询这个块中有没有被射中且没被删除的，删除以后vis变1即可。此方法非常佛系，能不能过得看运气，但是代码很短，当实在没思路时不失为一种选择
方法2：
使用线段树动态开点，与众不同的是线段树每个点都是一个set，这个非常神奇。对x-y到x+y的点全都加这个圆的编号，不需要push_up,push_down,因为查询的时候一直到查询到或者实在没了才会return，没找到会一直下去，所以只要乖乖呆在路径上总能被找到
以下是代码：
方法1：
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(int i=a;i<=b;i++) #define per(i,a,b) for(int i=a;i>=b;i--) #define ll long long #define inf 0x3f3f3f3f const int MAXN = 2e5+5; const int MOD = 1e9+7; int n,t,x,y; struct node{ int x,y; }a[MAXN]; vector<int>v[MAXN]; int vis[MAXN]; int main() { while(~scanf("%d",&n)){ rep(i,0,1e3)v[i].clear(); memset(vis,0,sizeof(vis)); rep(i,1,n){ scanf("%d%d%d",&t,&x,&y); if(t==1){ int l=(x-y+2e9)/4e6,r=(x+y+2e9)/4e6; rep(j,l,r){ v[j].push_back(i); } a[i].x=x,a[i].y=y; } else{ int pos=(x+2e9)/4e6; int len=v[pos].size(),flag=0; rep(j,0,len-1){ int u=v[pos][j]; if(vis[u])continue; if((ll)(a[u].x-x)*(a[u].x-x)+(ll)(a[u].y-y)*(a[u].y-y)<(ll)a[u].y*a[u].y){ flag=1; printf("%d\n",u); vis[u]=1; } }if(!flag)puts("-1"); } } } return 0; }
方法2：
#include<bits/stdc++.h> using namespace std; #define rep(i,a,b) for(ll i=a;i<=b;i++) #define per(i,a,b) for(ll i=a;i>=b;i--) #define ll long long #define inf 0x3f3f3f3f const ll MAXN = 2e5+5; const ll MOD = 1e9+7; ll n,t,x,y,rt; ll cnt; set<ll>s[MAXN*20]; ll lson[MAXN*20],rson[MAXN*20],ans; struct node{ ll x,y; }a[MAXN]; void update(ll &rt,ll l,ll r,ll L,ll R,ll val,ll flag){ if(!rt)rt=++cnt; if(L<=l&&r<=R){ if(flag)s[rt].insert(val); else s[rt].erase(val); return; } ll mid=(l+r)>>1; if(L<=mid)update(lson[rt],l,mid,L,R,val,flag); if(R>mid)update(rson[rt],mid+1,r,L,R,val,flag); } void query(ll rt,ll l,ll r,ll x,ll y){ if(!rt)return; if(l<=x&&x<=r){ for(set<ll>::iterator it=s[rt].begin();it!=s[rt].end();it++){ ll pos=*it; if((a[pos].x-x)*(a[pos].x-x)+(a[pos].y-y)*(a[pos].y-y)<a[pos].y*a[pos].y){ ans=pos; return; } } } if(l==r)return; ll mid=(l+r)>>1; if(x<=mid)query(lson[rt],l,mid,x,y); else query(rson[rt],mid+1,r,x,y); } int main() { while(~scanf("%I64d",&n)){ rep(i,1,20*n)s[i].clear(); memset(lson,0,sizeof(lson)); memset(rson,0,sizeof(rson)); rt=0; cnt=0; rep(i,1,n){ scanf("%I64d%I64d%I64d",&t,&x,&y); a[i].x=x,a[i].y=y; if(t==1){ update(rt,-1e9,1e9,x-y,x+y,i,1); } else{ ans=-1; query(rt,-1e9,1e9,x,y); if(ans==-1)puts("-1"); else { printf("%I64d\n",ans); update(rt,-1e9,1e9,a[ans].x-a[ans].y,a[ans].x+a[ans].y,ans,0); } } } } return 0; }
