注意题面中每个位置的物品只有一个，相当于在这两个序列 $A, B$ 中选择若干点对，其它点与 $0$ 或 $d$ 匹配。

对每对匹配点连线，发现任意连线不能交叉，这样每一段区间内的连线都是单方向的。我们先假设没有点向 $0$ 连边，这样遍历序列，用 $res$ 记录 $A$ 中点数与 $B$ 中点数的差。$res$ 的正负体现了这段区间内连线的方向。

发现 $A,B$ 中的点不能同时连向 $0$，记录变量 $k$ 为连向 $0$ 的连线方向和数量，$k$ 为正即 $A$ 与 $0$ 相连。这样后面每一段的 $res$ 相当于减去 $k$。

总贡献为 $\sum_i Len_i|res_i-k|$。

使贡献最小的 $k$ 为 $res$ 的加权中位数，即 $\min{k}$ 使得 $\sum_{res_i\le k} Len_i \ge \frac{d}{2}$。

#include <bits/stdc++.h>
using namespace std;
int a[500005],b[500005];
long long f[500005],len[500005];
vector <long long> v[500005];
int main()
{
	int n;
	long long d;
	scanf("%d%lld",&n,&d);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		for(int j=1;j<=a[i];j++)
		{
			long long x;
			scanf("%lld",&x);
			v[i].push_back(x);
		}
	}
	for(int r=2;r<=n;r++)
	{
		int res=0,i=0,j=0,cnt=0,k;
		long long las=0;
		while(i<a[r-1]||j<a[r])
		{
			if(i==a[r-1]||j!=a[r]&&v[r][j]<v[r-1][i])
			{
				j++;
				if(v[r][j-1]!=las)
				{
					len[++cnt]=v[r][j-1]-las;
					b[cnt]=res;
				}
				res--;
				las=v[r][j-1];
			}
			else
			{
				i++;
				if(v[r-1][i-1]!=las)
				{
					len[++cnt]=v[r-1][i-1]-las;
					b[cnt]=res;
				}
				res++;
				las=v[r-1][i-1];
			}
		}
		len[++cnt]=d-las;
		b[cnt]=res;
		for(int i=1;i<=cnt+1;i++)
			f[b[i]+a[r]]+=len[i];
		long long sum=0,ans=0;
		for(int i=0;i<=a[r-1]+a[r];i++)
		{
			sum+=f[i];
			if(2*sum>=d)
			{
				k=i;
				break;
			}
		}
		for(int i=1;i<=cnt+1;i++)
			ans+=len[i]*abs(b[i]+a[r]-k);
		printf("%lld\n",ans);
		for(int i=1;i<=cnt+1;i++)
			b[i]=len[i]=0;
		for(int i=0;i<=a[r-1]+a[r];i++)
			f[i]=0;
	}
	return 0;
}