一个显然的\(dp\)，设\(dp_{i,j}\)表示其中一个棋子在\(x_i\)点，另一个棋子在\(j\)点的最小花费

显然\(dp_{i,j}\)有两种转移

第一种是把\(x_i\)上的棋子移到\(x_{i+1}\)，那么那么就是\(dp_{i+1,j}=\min(dp_{i,j}+|x_{i+1}-x_i|)\)

第二种就是把\(j\)上的棋子移动到\(x_{i+1}\)，那么就是\(dp_{i+1,x_i}=\min(dp_{i,j}+|j-x_{i+1}|)\)

这是\(O(nQ)\)的，考虑优化

发现第一种转移形式非常固定，于是直接整体\(dp\)。第一种转移其实就是全局加，我们维护一个加法标记就可以了。

第二种转移都是转移到\(dp_{i+1,x_i}\)，绝对值看起来比较讨厌，考虑将绝对值拆开，当\(j\geq x_{i+1}\)时，\(dp_{i+1,x_i}=dp_{i,j}+j-x_{i+1}\)；当\(j\leq x_{i+1}\)时，\(dp_{i+1,x_i}=dp_{i,j}-j+x_{i+1}\)，于是考虑直接使用线段树来维护\(dp_{i,j}+j\)和\(dp_{i,j}-j\)的最小值，查一下这两个区间就能转移了。

代码

#include
    
     #define re register#define LL long longinline int read() {    char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;}const LL inf=1e15;const int maxn=2e5+5;int l[maxn<<2],r[maxn<<2];LL mx[maxn<<2][2],tag;int pos[maxn],d[maxn],n,A,B,Q;inline LL min(LL a,LL b) {return a
     
      >1;    build(x,mid,i<<1),build(mid+1,y,i<<1|1);}void change(int x,LL v,int o) {    x=pos[x];mx[x][o]=min(v,mx[x][o]);x>>=1;    while(x) mx[x][o]=min(mx[x][o],v),x>>=1;}LL query(int x,int y,int i,int o) {    if(x<=l[i]&&y>=r[i]) return mx[i][o];    int mid=l[i]+r[i]>>1;LL now=inf;    if(x<=mid) now=min(now,query(x,y,i<<1,o));    if(y>mid) now=min(now,query(x,y,i<<1|1,o));    return now;}inline LL ABS(LL x) {return x>=0?x:-x;}int main() {    n=read(),Q=read(),A=read(),B=read();    for(re int i=1;i<=Q;i++) d[i]=read();    build(1,n,1);    change(A,ABS(d[1]-B)+A,0);change(A,ABS(d[1]-B)-A,1);    change(B,ABS(d[1]-A)+B,0);change(B,ABS(d[1]-A)-B,1);    for(re int i=2;i<=Q;i++) {        LL x=query(d[i],n,1,0)-d[i],y=query(1,d[i],1,1)+d[i];        x=min(x,y);        LL a=min(mx[pos[d[i-1]]][0]-d[i-1],mx[pos[d[i-1]]][1]+d[i-1]);        if(x