自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 23:04:23，当前版本为作者最后更新于2024-11-01 19:45:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

做一些处理。

记 $a_{i,j}$ 表示第 $i$ 个无人机从第 $j-1$ 个门到第 $j$ 个门的耗时。

这个问题的模型实际上是对这 $n$ 个数组 $a_i$ 的一个顺序归并。一个经典的观察是，如果存在一个段 $[l,r]$，满足 $\forall l<i\le r,a_{p,i}\le a_{p,l}$，那么一旦 $(p,l)$ 被删除，$(p,l+1),\dots,(p,r)$ 都会被一并删除，也就是这些点是绑定的。这样极长地划分可以把一行划分成若干个段。

记 $d_i=s_i-s_{i-1},S=s_m$，则有 $\sum d_i=S\le 1.5\times10^5$。

注意到 $a_{i,j}=t_id_j$，同行 $a$ 的大小关系之和 $d$ 有关，所以实际上每行的段都是一样的，等于在 $d$ 中划分出来的段。

根据上诉的限制，段之间满足开头元素递增，即 $d_{l_1}<d_{l_2}<\dots<d_{l_m'}$，则，有 $m'\le O(\sqrt S)$。

记 $w'_{i,j}$ 表示第 $i$ 个人通过第 $j$ 段的耗时，则有 $w'_{i,j}=t_id_{l_j}$，同行 $w'$ 单增。

先考虑怎么计算全局的答案。

$i$ 的传送次数相当于 $i$ 完成比赛之前经过的轮数。由于同行 $w'$ 单增，等价于其他行的所有 $w'$ 中不超过 $w'_{i,m'}$ 的段的长度和。

形式化地：$\mathrm{ans}=\sum\limits_{i=1}^n\sum\limits_{j\ne i}\sum\limits_{k=1}^{m'}[w'_{j,k}\le w'_{i,m'}]l_k$，其中 $l_k$ 为第 $k$ 段的长度。

可以不钦定 $j\ne i$，最后减去 $j=i$ 的答案，即 $nm$。

由于 $k$ 范围较小，考虑固定 $i,k$ 计数：$[w'_{j,k}\le w'_{i,m'}]\Leftrightarrow t_j\le\dfrac{t_id_{m'}}{d_k}$，相当于提出一个对 $t_j$ 的限制 $t_j\le R_{i,k}$。

如果固定 $k$，把 $i$ 按 $t$ 从小到大枚举，这个边界是单调的，可以双指针扫一遍做到 $O(n\sqrt S)$。

对所有前缀的查询，相当于增加 $i,j\le x$ 的限制。

考虑计算 $\mathrm{ans}_x-\mathrm{ans}_{x-1}$，即 $i=x,j<x$ 的答案，以及 $i\le x,j=x$ 的答案。

• $i=x,j<x$：$\sum\limits_{j<x}\sum\limits_k[t_j\le R_{x,k}]l_k$。

  枚举 $k$，查询 $R_{x,k}$ 的前缀和 $S$，把 $Sl_k$ 贡献到答案，然后给 $t_x$ 单点加一。

  $O(n)$ 次单点修改，$O(n\sqrt S)$ 次前缀查询，可以根号平衡。

• $i\le x,j=x$：$\sum\limits_{i\le x}\sum\limits_k[t_x\le R_{i,k}]l_k$。

  枚举 $k$，给 $R_{x,k}$ 单点加 $l_k$。查询 $t_x$ 的后缀和，贡献到答案。

  $O(n\sqrt S)$ 次单点修改，$O(n)$ 次后缀查询，也可以根号平衡。

最后复杂度做到 $O(n(\sqrt n+\sqrt S))$。

const int N=1.5e5+5;
int n,m,tt=0,s[N],t[N],ln[N];
int id[N],rk[N];

typedef long long ll;
int lm[N][550];ll as[N];
const int B=400;
int I[N],L[N],R[N];
int s1[N],s2[N];ll s3[N],s4[N];
inline void U1(int p){
	for(int i=p;i<=R[I[p]];i++)s1[i]++;
	for(int i=I[p];i<=I[n];i++)s2[i]++;
}
inline int Q1(int p){return s2[I[p]-1]+s1[p];}
inline void U2(int p,int k){s3[p]+=k;s4[I[p]]+=k;}
inline ll Q2(int p){
	ll x=0;
	for(int i=I[p]+1;i<=I[n];i++)x+=s4[i];
	for(int i=p;i<=R[I[p]];i++)x+=s3[i];
	return x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&t[i]);
	iota(id+1,id+n+1,1);
	stable_sort(id+1,id+n+1,[&](int x,int y){return t[x]<t[y];});
	for(int i=1;i<=n;i++)rk[id[i]]=i;
	for(int i=1;i<=m;i++)scanf("%d",&s[i]);
	for(int i=m;i>=2;i--)s[i]-=s[i-1];
	for(int i=1,j;i<=m;i=j+1){
		for(j=i;j<m&&s[j+1]<=s[i];j++);
		ln[++tt]=j-i+1;s[tt]=s[i];
	}
	for(int j=1;j<=tt;j++)for(int i=1,p=0;i<=n;i++){
		while(p<n&&make_pair((ll)t[id[p+1]]*s[j],id[p+1])<=make_pair((ll)t[id[i]]*s[tt],id[i]))p++;
		lm[id[i]][j]=p;
	}
	for(int i=1;i<=n;i++)I[i]=(i-1)/B+1;
	for(int i=1;i<=I[n];i++){L[i]=R[i-1]+1;R[i]=R[i-1]+B;}R[I[n]]=n;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=tt;k++)U2(lm[i][k],ln[k]);
		as[i]=Q2(rk[i]);
		for(int k=1;k<=tt;k++)as[i]+=(ll)Q1(lm[i][k])*ln[k];
		U1(rk[i]);
	}
	for(int i=1;i<=n;i++)printf("%lld\n",as[i]+=as[i-1]-m);
	return 0;
}