题解 [NEERC2017]Archery Tournament

a___ · 2021-02-17 19:46:55 · 题解

由于这些圆都与 x 轴相切且没有两圆相交，所以显然我们将这些圆全部投影到 x 轴上后任意一个点最多会被 \mathbf O (\log n) 个区间覆盖。所以我们每次只需要找到这 \mathbf O (\log n) 个圆就好。

考虑用线段树维护。每个节点开一个 unordered_set，每次修改向 [x_i-y_i,x_i+y_i] 全部加入编号 i。查询的时候直接遍历途径的每个节点的 unordered_set 就好。修改的复杂度是 \mathbf O(\log n) 的，查询的复杂度是 \mathbf O(\log n+\log n) 的，所以总复杂度为 \mathbf O(n\log n)。

代码：

#include<cstdio>
#include<unordered_set>
#include<algorithm>
const int N=2e5+10;
int n,t[N],x[N],y[N],a[N];
std::unordered_set<int>st[N<<2];
void update(int rt,int l,int r,int ql,int qr,int x)
{
    if(ql<=l&&r<=qr){x<0?(st[rt].erase(-x),0):(st[rt].insert(x),0);return;}
    int m=(l+r)>>1;
    if(ql<=m)update(rt<<1,l,m,ql,qr,x);
    if(qr>m)update(rt<<1|1,m+1,r,ql,qr,x);
}
void query(int rt,int l,int r,int p,int &ans)
{
    for(int i:st[rt])if(1ll*(x[p]-x[i])*(x[p]-x[i])+1ll*(y[p]-y[i])*(y[p]-y[i])<1ll*y[i]*y[i])ans=i;
    if(l==r)return; int m=(l+r)>>1;
    x[p]<=a[m]?query(rt<<1,l,m,p,ans):query(rt<<1|1,m+1,r,p,ans);
}
int main()
{
    int i,p;scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d%d%d",&t[i],&x[i],&y[i]),a[i]=x[i];
    std::sort(a+1,a+1+n);
    for(i=1;i<=n;i++)
    t[i]==1?(update(1,1,n,std::lower_bound(a+1,a+1+n,x[i]-y[i])-a,std::upper_bound(a+1,a+1+n,x[i]+y[i])-a-1,i),0):
    (p=-1,query(1,1,n,i,p),printf("%d\n",p),(~p)&&(update(1,1,n,std::lower_bound(a+1,a+1+n,x[p]-y[p])-a,std::upper_bound(a+1,a+1+n,x[p]+y[p])-a-1,-p),0));
    return 0;
}