自动搬运

查看原文

来自洛谷，原作者为

	xyin 写个 ST 表能怎样？

搬运于2025-08-24 22:29:32，当前版本为作者最后更新于2024-08-14 21:18:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

双倍经验

手玩样例，我们能发现一些特殊性质：

• 对于每一个雪球来说，能对它的质量产生贡献的位置和起来是一个区间。

顺着这个思路往下想，就能想到对每一个雪球维护一个能延伸到的最远的端点值（前提条件是对它的质量有贡献），最终的答案就是 $r_i-l_i$。

怎么维护这个端点值呢？

解法一：

考虑枚举天数，根据每一天的风力强度 $W_j$ 和上一次的坐标（设为 $last$）更新 $i$ 的端点值，最后直接输出就行。

记得在更新端点值的时候比较相邻两个雪球的端点值（看是否对 $i$ 产生贡献），判断是否能更新。

此时你有了一份 $O(nq)$ 的代码，得分 $33$ 分，记录详情。

signed main(){
	n=read();q=read();
	for (int i=1;i<=n;i++)
	  last[i]=l[i]=r[i]=read();
	for (int i=1;i<=q;i++)
	  w[i]=read();
	for (int i=1;i<=q;i++)//枚举天数 
		for (int j=1;j<=n;j++){//枚举雪球 
	  	last[j]+=w[i];
	  	if (last[j]<l[j]){//如果新的位置小于左端点->“尝试 ”更新 
	  		if (j==1) l[j]=last[j];
	  		else if (last[j]>=r[j-1]) //能更新 
	  		  l[j]=last[j];
	  		else l[j]=r[j-1];//不能 
		  }
		else if (last[j]>r[j]){//如果新的位置大于右端点 
			if (j==n) r[j]=last[j];
			else if (last[j]<=l[j+1])//同上 
			  r[j]=last[j];
			else r[j]=l[j+1];//同上 
		}
	  }
	for (int i=1;i<=n;i++)
	  printf("%lld\n",r[i]-l[i]);
	return 0;
}

解法二：

考虑能不能优化上述方法，我们其实还能发现一些其它性质：

• 经过 $Q$ 天以后，雪球 $i$ 的运动路径其实是一条折线（不断做往复运动），折线的端点其实并没有 $Q$ 这么多。

我们尝试将折线的几次沿这直线的运动（不折返）浓缩为一次，直到它折返。

但这只是我们对常数的小优化，实际复杂度还是 $O(nq)$，别对它报什么期望。得分 $33$ 分，记录详情能看出确实比之前快了不少（还多过了两个点），但还是 T 了很多点___*( ￣皿￣)/#____。

//cnt 记录浓缩后的段数 
//tag的含义：1->此时正在处理>0的数，0->正在处理<=0的数 
signed main(){
	n=read();q=read();
	for (int i=1;i<=n;i++)
	  last[i]=l[i]=r[i]=read();
	for (int i=1,x;i<=q;i++){
		x=read();
		if (i==1) {
			if (x>0) tag=1;
			else tag=0;
			tot+=x;
		}
	  	else if (x<=0){
	  		if (tag==1) 
			  w[++cnt]=tot,tag=0,tot=x;
	  		else tot+=x;
		  }
		else {
			if (tag==1) tot+=x;
			else w[++cnt]=tot,tag=1,tot=x;
		}
	}
	w[++cnt]=tot;
	for (int i=1;i<=cnt;i++)//这一部分与之前一样 
	{
		for (int j=1;j<=n;j++){
	  	last[j]+=w[i];
	  	if (last[j]<l[j]){
	  		if (j==1) l[j]=last[j];
	  		else if (last[j]>=r[j-1]) 
	  		  l[j]=last[j];
	  		else l[j]=r[j-1];
		  }
		else if (last[j]>r[j]){
			if (j==n) r[j]=last[j];
			else if (last[j]<=l[j+1])
			  r[j]=last[j];
			else r[j]=l[j+1];
		}
	  }
	}
	for (int i=1;i<=n;i++)
	  printf("%lld\n",r[i]-l[i]);
	return 0;
}

解法三：

终于来到了正解，我们考虑能优化哪一维，最终输出答案时你肯定必须枚举雪球（怎么都甩不开），所以只能在 $q$ 上下功夫。

观察数据范围 $1\le N,Q \le 2\times 10^5$，最终复杂度肯定是 $O(n\log q)$ 的，说实话，看到 $\log$ 你应该考虑考虑二分的。

我们来看看答案是否具有二分的性质：

• 端点值的更新肯定是单调的（只会扩张不会缩减）。

• 当某天雪球滚动完之后，若它和它相邻的雪球，在左（右）端点值更新时出现了冲突之后，该点的左（右）端点值再也不会更新，同样相邻点的右（左）端点值也再也不会更新。

• 当两个相邻的雪球出现冲突时，这段冲突区间到底是谁的贡献（根据风的正负）其实很好判断。

有了这几个性质就万事大吉了，我们直接二分冲突时间 $t$ 就行了，复杂度 $O(n\log q)$，得分 $100$ 分，记录详情。

代码写得重复啰嗦，马蜂丑陋。

int last,q,n,a[maxn],ans1,ans2;
int L[maxn],R[maxn],w[maxn];
bool check1(int x,int i){
	if (a[i-1]+R[x]>a[i]+L[x]) return 0;
	return 1;
}
bool check2(int x,int i){
	if (a[i+1]+L[x]<a[i]+R[x]) return 0;
	return 1;
}
int solve(int i,int k1,int k2){
	int ans=0;
	ans+=R[k2]-L[k1];
	if (i==1) ans+=-L[q];
	else if (k1<q&&w[k1+1]<0)
	  ans+=a[i]+L[k1]-a[i-1]-R[k1];
	if (i==n) ans+=R[q];
	else if (k2<q&&w[k2+1]>0)
	  ans+=a[i+1]+L[k2]-a[i]-R[k2];
	return ans; 
}
signed main(){
	n=read();q=read();
	for (int i=1;i<=n;i++) 
	  a[i]=read();
	for (int i=1;i<=q;i++){
		w[i]=read();last+=w[i];
		R[i]=R[i-1];L[i]=L[i-1];
		if (last>R[i]) R[i]=last;
		else if (last<L[i]) L[i]=last;
	}
	for (int i=1;i<=n;i++){
		ans1=ans2=0;
		if (i!=1){
			int l=1,r=q;
			while (l<=r){
				int mid=(l+r)>>1;
				if (check1(mid,i)) 
				  l=mid+1,ans1=mid;
				else r=mid-1;
			}
		}
		if (i!=n){
			int l=1,r=q;
			while (l<=r){
				int mid=(l+r)>>1;
				if (check2(mid,i))
				  l=mid+1,ans2=mid;
				else r=mid-1;
			}
		}
		printf("%lld\n",solve(i,ans1,ans2));
	}
	return 0;
}