自动搬运

查看原文

来自洛谷，原作者为

	Dispwnl **

搬运于2025-08-24 21:49:08，当前版本为作者最后更新于2019-01-04 20:57:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

博客qwq

分情况讨论，假设交换的是$i,j$，则答案是$ans-val_i-val_j+\vert h_i-L_j\vert+\vert h_i-R_j\vert+\vert h_j-L_i\vert+\vert h_j-R_i\vert$，其中$val_i$表示原来$i$位置的答案，$L_i$表示$min(h_{i-1},h_{i+1})$，$R_i$表示$max(h_{i-1},h_{i+1})$，这样就有了$3\times 3=9$种情况（……）：

$h_i<L_j,h_i>R_j,L_j\le h_i\le R_j$

$j$同理

这样就可以用线段树+扫描线做了，写起来还是挺麻烦的写出一种情况然后ctrl+A+C+V改改就行了

代码

# include<iostream>
# include<cstring>
# include<cstdlib>
# include<cstdio>
# include<algorithm>
# define tl (k<<1)
# define tr (k<<1|1)
# define mid (l+r>>1)
# define LL long long
using namespace std;
const int MAX=5e4+5;
struct p{
	LL x;
}s[MAX<<2];
struct q{
	int x,id;
	bool operator< (const q &a)
	const{
		return x<a.x;
	}
}A[MAX],val[MAX],val_l[MAX],val_r[MAX];
int n,m,_n;
LL Ans;
int h[MAX],H[MAX],_h[MAX],HL[MAX],HR[MAX],_H[MAX],_L[MAX],_R[MAX],__L[MAX],__R[MAX];
LL ans[MAX];
bool use[MAX];
bool cmp(q a,q b) {return a.x>b.x;}
void pus(int k) {s[k].x=min(s[tl].x,s[tr].x);}
void change(int l,int r,int k,int x,LL dis)
{
	if(l==r) return void(s[k].x=min(s[k].x,dis));
	if(x<=mid) change(l,mid,tl,x,dis);
	else change(mid+1,r,tr,x,dis);
	pus(k);
}
void update(int l,int r,int k,int x,LL dis)
{
	if(l==r) return void(s[k].x=dis);
	if(x<=mid) update(l,mid,tl,x,dis);
	else update(mid+1,r,tr,x,dis);
	pus(k);
}
LL ask(int l,int r,int k,int L,int R)
{
	if(r<L||R<l) return 1e18;
	if(l>=L&&r<=R) return s[k].x;
	return min(ask(l,mid,tl,L,R),ask(mid+1,r,tr,L,R));
}
int read()
{
	int x(0);
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar());
	for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
	return x;
}
int look(int x)
{
	int l=1,r=n,ans;
	while(l<=r)
	{
		if(_h[mid]<=x) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}
int _look(int x)
{
	int l=1,r=n,ans;
	while(l<=r)
	{
		if(_h[mid]>=x) ans=mid,r=mid-1;
		else l=mid+1;
	}
	return ans;
}
void Init()
{
	memcpy(_h,h,sizeof(h));
	sort(_h+1,_h+1+n);
	for(int i=1;i<=n;++i)
	  {
		if(i!=1) _H[i]+=abs(h[i]-h[i-1]);
		if(i!=n) _H[i]+=abs(h[i]-h[i+1]);
		if(i!=1&&i!=n) HL[i]=min(h[i-1],h[i+1]),HR[i]=max(h[i-1],h[i+1]),_L[i]=_look(HL[i]),_R[i]=look(HR[i]),__L[i]=look(HL[i]),__R[i]=look(HR[i]);
	  }
	for(int i=2;i<=n;++i)
	  Ans+=abs(h[i]-h[i-1]);
	for(int i=1;i<=n;++i)
	  ans[i]=Ans;
	LL x;
	for(int i=1;i<=n;++i)
	  {
	  	if(i>2) ans[1]=min(ans[1],x=Ans-_H[i]-_H[1]+abs(h[i]-h[2])+abs(h[1]-h[i-1])+(i!=n?abs(h[1]-h[i+1]):0)),ans[i]=min(ans[i],x);
	  	if(i<n-1) ans[n]=min(ans[n],x=Ans-_H[i]-_H[n]+abs(h[i]-h[n-1])+abs(h[n]-h[i+1])+(i!=1?abs(h[n]-h[i-1]):0)),ans[i]=min(ans[i],x);
	  	if(i!=1) ans[i]=min(ans[i],Ans-(i!=n?abs(h[i]-h[i+1]):0)-(i>2?abs(h[i-1]-h[i-2]):0)+((i!=n&&i!=1)?abs(h[i-1]-h[i+1]):0)+(i>2?abs(h[i]-h[i-2]):0));
	  	if(i!=n) ans[i]=min(ans[i],Ans-(i!=1?abs(h[i]-h[i-1]):0)-(i<n-1?abs(h[i+1]-h[i+2]):0)+((i!=n&&i!=1)?abs(h[i-1]-h[i+1]):0)+(i<n-1?abs(h[i]-h[i+2]):0));
	  }
	for(int i=1;i<=n;++i)
	  val[i]=(q){h[i],i},val_l[i]=(q){HL[i],i},val_r[i]=(q){HR[i],i};
}
void Solve1()
{
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	sort(val+2,val+n),sort(val_r+2,val_r+n);
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_r[L].x<=val[i].x&&L<n) x=val_r[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]-HR[x]-2*h[x]-_H[x]),++L;
	  	x=val[i].id;
		if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,1,__L[x])-_H[x]+2*h[x]+HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]-HR[x-1]-2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]-HR[x+1]-2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]-HR[x]-2*h[x]-_H[x]);
	  }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_r[L].x<=val[i].x&&L<n) x=val_r[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]-HR[x]+2*h[x]-_H[x]),++L;
		x=val[i].id;
		if(use[x-1])
		update(1,n,1,H[x-1],1e18);
		if(use[x+1]) 
		update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,__R[x],n)-_H[x]+2*h[x]-HL[x]-HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]-HR[x-1]+2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]-HR[x+1]+2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]-HR[x]+2*h[x]-_H[x]);
	  }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_r[L].x<=val[i].x&&L<n) x=val_r[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]-HR[x]-_H[x]),++L;
	  	x=val[i].id;
		if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,_L[x],_R[x])-_H[x]+2*h[x]-HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]-HR[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]-HR[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]-HR[x]-_H[x]);
	  }
}
void Solve2()
{
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	sort(val+2,val+n,cmp),sort(val_l+2,val_l+n,cmp);
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_l[L].x>=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],HL[x]+HR[x]-2*h[x]-_H[x]),++L;
	  	x=val[i].id;
		if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,1,__L[x])-_H[x]-2*h[x]+HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],HL[x-1]+HR[x-1]-2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],HL[x+1]+HR[x+1]-2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],HL[x]+HR[x]-2*h[x]-_H[x]);
	  }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_l[L].x>=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],HL[x]+HR[x]+2*h[x]-_H[x]),++L;
	  	x=val[i].id;
		if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,__R[x],n)-_H[x]-2*h[x]-HL[x]-HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],HL[x-1]+HR[x-1]+2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],HL[x+1]+HR[x+1]+2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],HL[x]+HR[x]+2*h[x]-_H[x]);
	  }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,x;i<n;++i)
	  {
	  	while(val_l[L].x>=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],HL[x]+HR[x]-_H[x]),++L;
	  	x=val[i].id;
	  	if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,_L[x],_R[x])-_H[x]-2*h[x]-HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],HL[x-1]+HR[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],HL[x+1]+HR[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],HL[x]+HR[x]-_H[x]);
	  }
}
void Solve3()
{
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	sort(val+2,val+n),sort(val_l+2,val_l+n),sort(val_r+2,val_r+n);
	for(int i=2,L=2,R=2,x;i<n;++i)
	  {
	  	while(val_l[L].x<=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]+HR[x]-2*h[x]-_H[x]),++L;
	  	while(val_r[R].x<val[i].x&&R<n) x=val_r[R].id,use[x]=0,update(1,n,1,H[x],1e18),++R;
	  	x=val[i].id;
	  	if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,1,__L[x])-_H[x]+HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]+HR[x-1]-2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]+HR[x+1]-2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]+HR[x]-2*h[x]-_H[x]);
	   }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,R=2,x;i<n;++i)
	  {
	  	while(val_l[L].x<=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]+HR[x]+2*h[x]-_H[x]),++L;
	  	while(val_r[R].x<val[i].x&&R<n) x=val_r[R].id,use[x]=0,update(1,n,1,H[x],1e18),++R;
	  	x=val[i].id;
	  	if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,__R[x],n)-_H[x]-HL[x]-HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]+HR[x-1]+2*h[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]+HR[x+1]+2*h[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]+HR[x]+2*h[x]-_H[x]);
	   }
	memset(s,1,sizeof(s));
	memset(use,0,sizeof(use));
	for(int i=2,L=2,R=2,x;i<n;++i)
	  {
	  	while(val_l[L].x<=val[i].x&&L<n) x=val_l[L].id,use[x]=1,change(1,n,1,H[x],-HL[x]+HR[x]-_H[x]),++L;
	  	while(val_r[R].x<val[i].x&&R<n) x=val_r[R].id,use[x]=0,update(1,n,1,H[x],1e18),++R;
	  	x=val[i].id;
	  	if(use[x-1]) update(1,n,1,H[x-1],1e18);
		if(use[x+1]) update(1,n,1,H[x+1],1e18);
		if(use[x]) update(1,n,1,H[x],1e18);
		ans[x]=min(ans[x],Ans+ask(1,n,1,_L[x],_R[x])-_H[x]-HL[x]+HR[x]);
		if(use[x-1]) update(1,n,1,H[x-1],-HL[x-1]+HR[x-1]-_H[x-1]);
		if(use[x+1]) update(1,n,1,H[x+1],-HL[x+1]+HR[x+1]-_H[x+1]);
		if(use[x]) update(1,n,1,H[x],-HL[x]+HR[x]-_H[x]);
	   }
}
int main()
{
	n=read();
	for(int i=1;i<=n;++i)
	  h[i]=read(),A[i]=(q){h[i],i};
	if(n==2) return printf("%d\n%d",abs(h[1]-h[2]),abs(h[1]-h[2])),0;
	sort(A+1,A+1+n);
	for(int i=1;i<=n;++i)
	  H[A[i].id]=i;
	Init(),Solve1(),Solve2(),Solve3();
	for(int i=1;i<=n;++i)
	  printf("%lld\n",ans[i]);
	return 0;
}