题目
Description
CDQZ是一个偏远的小学校，FGD在学校里中了一排树。他却不喜欢这些树的顺序，因为他们高高矮矮显得那么 参差不齐。FGD定义这些树的不整齐程度为相邻两树的高度差的和。设树高分别为h1,h2,h3,…,hn。那么不整齐程 度定义为：$\vert h_1-h_2\vert+\vert h_2-h_3\vert +……+\vert h_{n-1}-h_n\vert$。不过，重新栽种这些树是一件麻烦的事情，所以FGD最多只想交换 其中两个树的位置。现在请你帮助他，他应该怎么交换使得整个一排树的不整齐程度最小。
Input
第一行包含一个整数n(2<=n<=50000)，接下来第二行包含n个正整数h1,h2,h3,…,hn，分别表示树的高度。（1 <=hi<=100000000）
Output
应该包含n行，每行一个整数，第i行表示若交换的其中一棵树编号为i，则能获得的最小不整齐程度为多少。
Sample Input
样例输入1
5
7 4 5 2 5
样例输入2
5
1 2 3 4 5
Sample Output
样例输出1
7
7
8
7
7
样例输出2
4
4
4
4
4
题解
分情况讨论，假设交换的是$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+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;
}
