自动搬运

查看原文

来自洛谷，原作者为

	a___ 这个家伙很蒻，什么也没有留下qwq

搬运于2025-08-24 22:25:24，当前版本为作者最后更新于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;
}