用O（n）的时间处理出来每种数字pos加一的影响和变成1的影响； 然后从 f（1）开始递推到f（n）【类似于差分】 拿加一的影响来说，现在数字x变成排列的第一个位置，那么比x小的数字之前pos已经加一，判断原序列中x的左右两个元素： 如果比x小，那么 inc[ x ]++ (所有大小为x的数字加一的影响) ，因为比x小的数pos之前已经+1，差的绝对值-1，因此当x pos变大时，要把它补回来； 如果比x大，那么inc[ x ]-- ,因为，x pos变大了，那么现在的两者pos差的绝对值变小。
同理可以处理出来 x pos变成1的总影响 作差算出绝对值差值的变化即可。
#include<cctype> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=2e5+5; const int inf=0x3f3f3f3f; const int mod=1e7+7; const LL maxn=1e18; #define fi first #define se second #define ls (i<<1) #define rs ((i<<1)|1) LL read() { LL x=0,t=1; char ch=getchar(); while(!isdigit(ch)){ if(ch=='-')t=-1; ch=getchar(); } while(isdigit(ch)){ x=10*x+ch-'0'; ch=getchar(); } return x*t; } LL inc[N],dec[N],a[N]; int main() { int n=read(),m=read(); for(int i=1;i<=m;i++) a[i]=read(); for(int i=1;i<=m;i++) { if(i>1) { if(a[i]>a[i-1]) inc[a[i] ]++; else if(a[i]<a[i-1]) inc[a[i] ]--; } if(i<m) { if(a[i]>a[i+1]) inc[a[i] ]++; else if(a[i]<a[i+1]) inc[a[i] ]--; } } for(int i=1;i<=m;i++) { if(i>1) { if(a[i]>a[i-1]) dec[a[i] ]+=a[i]-a[i-1]*2-1;//a[i]-(a[i-1]+1) -abs(1-(a[i-1]+1) ) ///a[i-1]+1,是因为 a[i] pos变为1时，a[i-1] pos增加了1 else if(a[i]<a[i-1]) dec[a[i] ]+=1-a[i]; } if(i<m) { if(a[i]>a[i+1]) dec[a[i] ]+=a[i]-a[i+1]*2-1; else if(a[i]<a[i+1]) dec[a[i] ]+=1-a[i]; } } LL ans=0; for(int i=2;i<=m;i++) ans+=abs(a[i]-a[i-1]); for(int i=1;i<=n;i++) { printf("%lld ",ans); ans+=inc[i]-dec[i+1]+dec[i]; ///把 i 从 “1”置回“i”， i加一 ，减掉 “i+1 ”变成 “1” 的影响 } putchar('\n'); return 0; } /* 5 5 5 1 4 2 2 10 11 10 9 8 9 8 10 1 10 2 9 5 */