关于此题

去年夏天，我就从朋友那里知道了这道题。

素不相识、相隔千里的几人竟然能互相敞开心扉，这是我那是坚持下去的一个重要因素。他说这题很有意思，我便不顾自己的水平就放入了做题计划，这一放，就是将近一年。

“线段树优化 DP，好厉害啊！”

“什么时候我也能会写线段树呢？”

一年中发生了太多的事，他已经不再那么热衷于 OI 了，我也从黄粱一梦中醒来。但是，仍然不变的，是一想到他就会燃起的小小斗志，是我不甘又无奈的形单影只。

也许我再也不是那个连背包问题都无法理解，只会对着题解研究代码的菜鸟了。但是……

分析

读完题面第一反应，就是把操作“离线”了。（没啥用，和纯数据结构题的离线不同）。

考虑完成 \(i\) 个操作时，一定有一个棋子在 \(x_i\) 的位置。那么可以设 \(f(i,j)\) 为完成了前 \(i\) 个操作，其中另一个棋子的位置在 \(j\)。

转移则有 2 种。

对于 \(f(i,j)\)，可以将 \(f(i-1,j)\) 中位置在 \(x_{i-1}\) 的棋子放过来，代价是 \(\Delta x = |x_i - x_{i-1}|\)。 \[ f(i,j) = f(i-1,j) + \Delta x \] 还可以将位置在另一个棋子放过来。由于状态无法直接表示，所以要枚举另一个棋子的位置 \(k\)。但是把「另一个棋子」放过来后，它位于 \(x_i\)，按照上文状态的设计，就转移到 \(f(i,x_{i-1})\) 了。

仔细想一想，\(f(i-1,k) \rightarrow f(i,x_{i-1})\) 这种情况还挺少见的，有点意思。😅 \[ f(i,x_{i-1}) = \min_{k \in [1,n]}{\{ f(i-1,k) + |k-x_i| \}} \] 直接这样做复杂度是 \(O(Qn)\) 的，考虑优化。

套路地把绝对值符号拆开，当 \(k > x_i\) 时，有 \[ f(i,x_{i-1}) = \min_{k \in [x_i+1,n]}{\{ f(i-1,k) + k \}} - x_i \] 当 \(k \le x_i\) 时，有 \[ f(i,x_{i-1}) = \min_{k \in [1,x_i]}{\{ f(i-1,k) - k \}} + x_i \] 这样问题就变成了，在 \([1,x_i]\) 中快速查找最小的 \(f(i-1,k)-k\)，在 \([x_i+1,n]\) 中快速查找最小的 \(f(i-1,k)+k\)。

而第一种转移其实变相地告诉我们，\(i-1\) 的状态是可以通过 \(\Delta x\) 转移到 \(i\) 的状态的。

实际上不难发现，对于第一种转移，只有 \(j=x_i\) 的时候才是最划算的，所以可以直接单点查询得到。但是这样就会被第二种转移中的 \(k=x_i\) 的情况覆盖了，所以可以完全无视第一种转移。

所以可以建立一棵线段树，维护 \(f(j)\) 这一层。

对于每个操作 \(i\)，维护 \(f(i-1,k)+k\) 与 \(f(i-1,k)-k\) 的值。全局加上 \(\Delta x\) 更新状态，最后单点修改 \(x_{i-1}\) 的值。

初始值 \(f(1,A) = |B-x_1|\)，\(f(1,B)=|A-x_1|\)

答案 \(\min_{k \in [1,n]}{\{ f(Q,k) \}}\)

由于只设计全局加，所以可以直接用打标记的方式实现。

复杂度 \(O(Q \log_2 n)\)。

CODE

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=200005;
const ll inf=1ll<<60;
int n, Q, a, b, x[N];
struct Segment_Tree {
	int l, r;
	ll tag, v[3];
    // tag是区间加标记
    // v[0]是f(i,k)，v[1]是f(i,k)-k，v[2]是f(i,k)+k
	#define l(u) t[u].l
	#define r(u) t[u].r
	#define tag(u) t[u].tag
	#define v(u) t[u].v[0]
	#define v1(u) t[u].v[1]
	#define v2(u) t[u].v[2]
} t[N<<2];
void maketag(int u,ll val) { tag(u)+=val, v(u)+=val, v1(u)+=val, v2(u)+=val; }
void pushup(int u) {
	v(u)=min(v(u<<1),v(u<<1|1));
	v1(u)=min(v1(u<<1),v1(u<<1|1));
	v2(u)=min(v2(u<<1),v2(u<<1|1));	
}
void pushdown(int u) {
	if(tag(u)) {
		maketag(u<<1,tag(u));
		maketag(u<<1|1,tag(u));
		tag(u)=0;
	}
}
void build(int u,int l,int r) {
	l(u)=l, r(u)=r;
	if(l==r) { v(u)=v1(u)=v2(u)=inf; return; }
    // 初始值
	int mid=(l+r)/2;
	build(u<<1,l,mid), build(u<<1|1,mid+1,r);
	pushup(u);
}
void modify(int u,ll p,ll val) {
    // 单点修改
	if(l(u)==r(u)) {
		v(u)=val, v1(u)=val-p, v2(u)=val+p;
		return;
	}
	pushdown(u);
    int mid=(l(u)+r(u))/2;
	if(p<=mid) modify(u<<1,p,val);
    else modify(u<<1|1,p,val);
	pushup(u);
}
ll query(int u,int l,int r,int id) {
    // 区间查询
	if(l<=l(u)&&r(u)<=r) { return t[u].v[id]; }
	pushdown(u);
	int mid=(l(u)+r(u))/2;
	ll ans=(1ll<<60);
	if(l<=mid) ans=min(ans,query(u<<1,l,r,id));
	if(r>mid) ans=min(ans,query(u<<1|1,l,r,id));
	return ans;
}
int main() {
	scanf("%d%d%d%d",&n,&Q,&a,&b);
	for(int i=1;i<=Q;++i) scanf("%d",&x[i]);
	build(1,1,n);
	modify(1,a,abs(b-x[1]));
	modify(1,b,abs(a-x[1]));
	for(int i=2;i<=Q;++i) {
		ll dlt=abs(x[i]-x[i-1]), r1=(1ll<<60), r2, r3;
//		r1=query(1,x[i],x[i],0)+dlt;
		r2=query(1,1,x[i],1)+x[i];
		r3=query(1,x[i]+1,n,2)-x[i];
		r1=min(r1,min(r2,r3));
		maketag(1,dlt); // 全局加上dlt
		modify(1,x[i-1],r1); // 修改f(i,x[i-1])
	}
	printf("%lld\n",v(1)); // 全局最小值
}