自动搬运

查看原文

来自洛谷，原作者为

	Shanganze **

搬运于2025-08-24 22:49:28，当前版本为作者最后更新于2023-08-16 19:48:53，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一篇不用二维线段树的题解。

题意：

对于一个点 $(x,y)$，可以由 $(i,j)$ 且 $(l1_x\le i\le r1_x,l2_y\le j\le r2_y)$ 花费 $a_{x,y}+a_{i,j}$ $(a_{i,j}=k_i+k_j-i-j)$ 到达。初始在 $(1,1)$ 求到达每个点的最短时间。

45 pts:

考虑暴力转移，$O(n^4)$，这里。

100 pts:

考虑题意，对于横坐标为 $j$ 的一整行，都会由 $l1_j-r1_j$ 这几行转移过来，我们可以用类似于悬线法的方式，把每一列 $l1_j-r1_j$ 的点取 $\min$ 归为一个点，可以用 $n$ 个线段树来维护每一列来实现这个操作，然后对于这合并出来的 $n$ 个点放到一棵线段树里，然后更新该行每个点答案，考虑无法到达的点答案加上 $inf$，由于 $dis_{x,y}=dis_{i,j}+a_{i,j}+a_{x,y}$，所以在更新完答案后都需加上本身的 $a_{i,j}$。最后答案减去自身 $a_{i,j}$ 即可，时间复杂度 $O(n^2\log n)$，空间复杂度 $O(n^2\log n)$。

注：写横纵坐标时不要写反。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e3+10;
int l1[N],l2[N],r1[N],r2[N],a[N][N],k[N],dis[N][N];
struct a1{int minn;}x[N][N<<2];
void X(int i,int l,int r,int p,int a,int dis){
	if(l==r){
		x[a][p].minn+=dis;
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=i)X(i,l,mid,p<<1,a,dis);
	else X(i,mid+1,r,p<<1|1,a,dis);
	x[a][p].minn=min(x[a][p<<1].minn,x[a][p<<1|1].minn);
}
int G(int L,int R,int l,int r,int p,int a){
	if(l>=L&&r<=R)return x[a][p].minn;
	int mid=(l+r)>>1;
	int ans=1e16;
	if(mid>=L)ans=G(L,R,l,mid,p<<1,a);
	if(mid<R) ans=min(ans,G(L,R,mid+1,r,p<<1|1,a));
	return ans;
}
signed main(){
	int n;
	cin>>n;
	for(int q=1;q<=n;q++){cin>>l1[q];if(l1[q]==0)l1[q]++;}
	for(int q=1;q<=n;q++){cin>>r1[q];}
	for(int q=1;q<=n;q++){cin>>l2[q];if(l2[q]==0)l2[q]++;}
	for(int q=1;q<=n;q++){cin>>r2[q];}
	for(int q=1;q<=n;q++)cin>>k[q];
	for(int q=1;q<=n;q++){
		for(int w=1;w<=n;w++){
			a[q][w]=k[q]+k[w]-q-w;
			X(q,1,n,1,w,a[q][w]);
		}
	}
	for(int q=2;q<=n;q++)X(1,1,n,1,q,1e10);
	for(int w=2;w<=n;w++){
		for(int i=1;i<=n;i++){
			X(i,1,n,1,n+1,G(l1[w],r1[w],1,n,1,i));
		}
		for(int i=1;i<=n;i++){
			if(r2[i]!=0)X(w,1,n,1,i,G(l2[i],r2[i],1,n,1,n+1));
			else X(w,1,n,1,i,1e10);
			X(w,1,n,1,i,a[w][i]);
		}
		for(int i=1;i<=n;i++){
			X(i,1,n,1,n+1,-G(l1[w],r1[w],1,n,1,i));
		}
	}
	for(int q=1;q<=n;q++){
		for(int w=1;w<=n;w++){
			int o=G(q,q,1,n,1,w)-a[q][w];
			if(o>=1e9)cout<<"inf ";
			else cout<<o<<" ";
		}
		cout<<"\n";
	}
	return 0;
}