自动搬运

查看原文

来自洛谷，原作者为

	Inui_Sana ばか！へんたい！うるさい！⠀

搬运于2025-08-24 22:04:11，当前版本为作者最后更新于2025-02-09 18:55:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

我觉得这题 $O((q+K)\sqrt K\log K)$ 非常自然而且非常可过吧，怎么题解区还没有。

一句话：每次询问枚举短的路线，在长的上二分，再记忆化可过。

考虑分析复杂度。记 $k=\sum K_i$。询问 $x,y$，令 $K_x<K_y$。若 $K_x\le\sqrt k$，显然每次不会枚举超过 $O(\sqrt k)$ 个位置。这部分是 $O(q\sqrt k\log k)$ 的。

否则，考虑每个位置被枚举了几次。因为 $K_y>\sqrt k$ 所以不同的 $y$ 最多有 $\sqrt k$ 个。记忆化之后，每个位置就会被枚举到不超过 $\sqrt k$ 次。所以这部分是 $O(k\sqrt k\log k)$ 的。

于是总复杂度 $O((q+k)\sqrt k\log k)$。实现的不太差就能通过。最慢点跑了 2.6s。

也讲一下二分的方法。注意到两车 $A,B$ 速度一样，所以 $A$ 车从 $u$ 直线到 $v$ 的过程中，两车最多相遇一次。同时容易证明，相遇的充要条件为两车位置的大小关系发生变化。于是二分 $B$ 车在 $A$ 分别在 $u,v$ 时的位置，判断大小关系是否变化即可。

代码非常清新。

code：

int n,q,c[N];
vector<int> g[N];
vector<ll> t[N];
map<pair<int,int>,int> mp;
il int getPos(int x,ll tm){
	int p=upper_bound(t[x].begin(),t[x].end(),tm)-t[x].begin()-1;
	return g[x][p+1]>g[x][p]?g[x][p]+tm-t[x][p]:g[x][p]-tm+t[x][p];
}
void Yorushika(){
	read(n,q);
	rep(i,1,n){
		read(c[i]);
		g[i].resize(c[i]+1),t[i].resize(c[i]+1);
		rep(j,1,c[i]){
			read(g[i][j]);
			t[i][j]=j==1?0:t[i][j-1]+abs(g[i][j]-g[i][j-1]);
		}
	}
	while(q--){
		int x,y;read(x,y);
		if(g[x].size()>g[y].size()||g[x].size()==g[y].size()&&x>y){
			swap(x,y);
		}
		if(mp.count(Mp(x,y))){
			printf("%d\n",mp[Mp(x,y)]);
			continue;
		}
		int ans=0;
		rep(i,1,c[x]-1){
			if(t[x][i]>=t[y][c[y]]){
				break;
			}
			ll l=t[x][i],r=min(t[x][i+1],t[y][c[y]]);
			int u1=g[x][i],v1=getPos(y,l),u2=g[x][i+1]>g[x][i]?u1+r-l:u1-r+l,v2=getPos(y,r);
			ans+=(u1>v1)^(u2>v2);
		}
		printf("%d\n",mp[Mp(x,y)]=ans);
	}
}
signed main(){
	int t=1;
	//read(t);
	while(t--){
		Yorushika();
	}
}