Codeforces Round #590 (Div. 3) E

用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('
');
    return 0;
}
/*
5 5
5 1 4 2 2
10 11
10 9 8 9 8 10 1 10 2 9 5
*/