自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 23:09:24，当前版本为作者最后更新于2025-02-06 16:31:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

好像大家都是同一个难写做法，这里分享我一个赛时的简单做法。

题解

一个初步结论是：

• 路线一定形如 $(X,0) \rightarrow (x_i,0) \rightarrow (0,y_i) \rightarrow (0,Y) $ 。

这是因为我们绕路的目的是避开一些 $(x_i,0) \rightarrow (0,y_i)$ 的线段，对于任意一条路线，我们都可以通过调整成上述形式使答案不劣。具体可以手玩一下。

令我们选择的中转点为 $(x',0),(0,y')$，那么一条线段 $(x_i,0) \rightarrow (0,y_i)$ 的限制可以表示为：

• $\forall x'< x_i,y'<y_i$。

• $\forall x'> x_i,y'>y_i$。

当 $x'$ 确定时，上述限制确定了合法的 $y'$ 为一个区间 $[l,r]$，显然我们存在以下贪心策略：

• $l>Y$：选取 $y'=l$。

• $r<Y$：选取 $y'=r$。

• $Y \in [l,r]$：选取 $y'=Y$。

到这里我们有一个 $O(n^2)$ 的暴力：对每个 $x'$ 暴力维护合法区间 $[l,r]$，每次加入线段后暴力枚举 $x'$ 更新答案。

重新思考上述过程，我们有以下观察：

• $\forall x_1 < x_2$，其对应的合法区间 $[l_1,r_1],[l_2,r_2]$ 有：$l_1 \leq l_2,r_1 \leq r_2$。

从这个结论下手分析：我们考察 $x_1 < x_2 \leq X,r_1 < Y$。如果 $r_2 < Y$，那么 $x_2$ 肯定优于 $x_1$，这种情况下最优的 $x'$ 肯定是 $\leq X$ 中最大的；若 $l_2 > Y$ 或 $Y \in [l_2,r_2]$，那么 $l_2/Y$ 一定是 $\geq Y$ 的所有合法 $y'$ 中最小的。

按照上面的分析，我们可以总结得出：

• 我们把不可能作为中转点的 $x_i,y_i$ 删去（即对应合法区间 $[l,r]$ 为空），最优解选择的中转点一定满足 $x_i$ 是 $\leq X$ 最大的；$x_i$ $\geq X$ 最小的；$y_i$ 是 $\leq Y$ 最大的；$y_i$ $\geq Y$ 最小的其中之一。

于是我们用树状数组维护每个 $x_i,y_i$ 对应的合法区间 $[l,r]$，每次取出上述 $O(1)$ 个 $x_i,y_i$ 得到答案即可。时间复杂度 $O(n \log n)$。

#include<bits/stdc++.h>
using namespace std;

const int N=3e5+10,M=1e6+10;
set<int> X1,X2,Y1,Y2;
vector<int> vec[N];
int n,T,xx[N],yy[N]; 
struct BIT1
{
	int C[M];
	BIT1(){for(int i=0;i<M;i++) C[i]=M-1;}
	inline void add(int x,int y){for(;x;x-=x&-x) C[x]=min(C[x],y);}
	inline int query(int x){int res=M-1;for(;x<M;x+=x&-x) res=min(res,C[x]);return res;}
}Xpre,Ypre;
struct BIT2
{
	int C[M];
	inline void add(int x,int y){if(!x) return;for(;x<M;x+=x&-x) C[x]=max(C[x],y);}
	inline int query(int x){int res=0;for(;x;x-=x&-x) res=max(res,C[x]);return res;}
}Xsuc,Ysuc;
inline void ins(int x,int y)
{
	if(x!=xx[0])
	{
		Xpre.add(x-1,y);Xsuc.add(x+1,y);
		Ypre.add(y-1,x);Ysuc.add(y+1,x);	
	}
	if(x<=xx[0]) X1.insert(x);else X2.insert(x);
	if(y<=yy[0]) Y1.insert(y);else Y2.insert(y);
}
inline int calcx(int x,int l,int r)
{
	if(r<yy[0]) return abs(x-xx[0])+yy[0]-r+sqrt(1ll*x*x+1ll*r*r);
	if(l>yy[0]) return abs(x-xx[0])+l-yy[0]+sqrt(1ll*x*x+1ll*l*l);
	return abs(x-xx[0])+sqrt(1ll*x*x+1ll*yy[0]*yy[0]);
}
inline int calcy(int x,int l,int r)
{
	if(r<xx[0]) return abs(x-yy[0])+xx[0]-r+sqrt(1ll*x*x+1ll*r*r);
	if(l>xx[0]) return abs(x-yy[0])+l-xx[0]+sqrt(1ll*x*x+1ll*l*l);
	return abs(x-yy[0])+sqrt(1ll*x*x+1ll*xx[0]*xx[0]);
}
inline int query()
{
	int ans=1e7;
	while(!X1.empty())
	{
		auto it=X1.end();--it;
		int rs=Xpre.query(*it),ls=Xsuc.query(*it);
		if(ls>rs) X1.erase(it);
		else
		{
			ans=min(ans,calcx(*it,ls,rs));
			break;
		}
	}
	while(!X2.empty())
	{
		auto it=X2.begin();
		int rs=Xpre.query(*it),ls=Xsuc.query(*it);
		if(ls>rs) X2.erase(it);
		else
		{
			ans=min(ans,calcx(*it,ls,rs));
			break;
		}
	}
	while(!Y1.empty())
	{
		auto it=Y1.end();--it;
		int rs=Ypre.query(*it),ls=Ysuc.query(*it);
		if(ls>rs) Y1.erase(it);
		else
		{
			ans=min(ans,calcy(*it,ls,rs));
			break;
		}
	}
	while(!Y2.empty())
	{
		auto it=Y2.begin();
		int rs=Ypre.query(*it),ls=Ysuc.query(*it);
		if(ls>rs) Y2.erase(it);
		else
		{
			ans=min(ans,calcy(*it,ls,rs));
			break;
		}
	}
	return ans;
}
int main()
{
	scanf("%d%d%d%d",&n,&T,&xx[0],&yy[0]);vec[0].push_back(0);
	for(int i=1;i<=n;i++)
	{
		int t;
		scanf("%d%d%d",&t,&xx[i],&yy[i]);
		vec[t].push_back(i);
	}
	for(int o=0;o<T;o++)
	{
		for(auto i:vec[o]) ins(xx[i],yy[i]);
		printf("%d\n",query());
	}
	return 0;
}