题意：
分析：
前排先 stO 一眼切掉此题的巨佬
我们开始一步步考虑
首先，有一个 (O(qn^2)) 的暴力，然后我们发现，每一次转移时只会由一个询问点的位置转移向下一个询问点的位置，所以可以少记一个位置，复杂度降为 (O(qn))
，然后继续优化，我们先写出转移式，我们设 DP 状态 (f_{i,j}) 表示第 (i) 次询问时 一个点在 (q_i) 另一个点在 (j) 时的最小代价，有状态转移如下：
-
第一种转移，就是另一个点转移向下一个询问点
(min(f_{i-1,j}+|j-q_i|) o f_{i,q_{i-1}})
把绝对值拆开
[f_{i,q_{i-1}}= egin{cases} min(f_{i-1,j}+j-q_i) & jge q_i\ min(f_{i-1,j}+q_i-j) & jle q_i\ end{cases} ] -
第二种转移询问点转移向下一个询问点
(f_{i-1,j}+dis(q_{i-1},q_i) o f_{i,j})
我们发现，第二种转移相当于是全局加一个常量，第一种转移相当于是查询全局带权最小值，单点赋值
其中这个带权最小值的权是一个一次函数，可以上李超树直接做
但是我们发现这个一次函数的一次项常数恒为 (1) ，所以我们可以将 DP 维护的东西变一下，把这个一次函数放进 DP 状态里面，也就是说我们维护 (f_{i,j}-j) 和 (f_{i,j}+j) 的最小值，这样就变成了直接查询全局最小值，不需要考虑带权的影响
代码：
#include<bits/stdc++.h>
#define pii pair<int,int>
#define mk(x,y) make_pair(x,y)
#define lc rt<<1
#define rc rt<<1|1
#define pb push_back
#define fir first
#define sec second
#define inl inline
#define reg register
#define int long long
using namespace std;
namespace zzc
{
inline int read()
{
int x=0,f=1;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;
}
const int maxn = 2e5+5;
const int inf = 0x3f3f3f3f3f3f3f;
int n,qt;
int min1[maxn<<2],min2[maxn<<2],tag[maxn<<2],p[maxn<<2];
void pushup(int rt)
{
min1[rt]=min(min1[lc],min1[rc]);
min2[rt]=min(min2[lc],min2[rc]);
}
void add(int rt,int x)
{
tag[rt]+=x;
min1[rt]+=x;
min2[rt]+=x;
}
void pushdown(int rt)
{
if(tag[rt])
{
add(lc,tag[rt]);
add(rc,tag[rt]);
tag[rt]=0;
}
}
void modify(int rt,int l,int r,int pos,int x)
{
if(l==r)
{
min1[rt]=min(min1[rt],x-l);
min2[rt]=min(min2[rt],x+l);
return ;
}
pushdown(rt);
int mid=(l+r)>>1;
if(pos<=mid) modify(lc,l,mid,pos,x);
else modify(rc,mid+1,r,pos,x);
pushup(rt);
}
int query1(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return min1[rt];
pushdown(rt);
int mid=(l+r)>>1,res=inf;
if(ql<=mid) res=min(res,query1(lc,l,mid,ql,qr));
if(qr>mid) res=min(res,query1(rc,mid+1,r,ql,qr));
return res;
}
int query2(int rt,int l,int r,int ql,int qr)
{
if(ql<=l&&r<=qr) return min2[rt];
pushdown(rt);
int mid=(l+r)>>1,res=inf;
if(ql<=mid) res=min(res,query2(lc,l,mid,ql,qr));
if(qr>mid) res=min(res,query2(rc,mid+1,r,ql,qr));
return res;
}
int query(int rt,int l,int r)
{
if(l==r) return min(min1[rt]+l,min2[rt]-l);
pushdown(rt);
int mid=(l+r)>>1;
return min(query(lc,l,mid),query(rc,mid+1,r));
}
void work()
{
int a,b;
n=read();qt=read();a=read();b=read();p[0]=a;
memset(min1,0x3f,sizeof(min1));
memset(min2,0x3f,sizeof(min2));
modify(1,1,n,b,0);
for(int i=1;i<=qt;i++)
{
p[i]=read();
int res=min(query1(1,1,n,1,p[i])+p[i],query2(1,1,n,p[i],n)-p[i]);
add(1,llabs(p[i]-p[i-1]));
modify(1,1,n,p[i-1],res);
}
printf("%lld
",query(1,1,n));
}
}
signed main()
{
zzc::work();
return 0;
}