传送门

我竟然可以独立做出远古ARC的压轴题。我记得上一次做四题 ARC D 还是一道Hall定理+扫描线的神题。

分析：

首先你发现，假设我们已经处理完了前 \(i\) 个询问，则必须有一个棋子在 \(q_{i}\) 的位置。所以我们只关注另外一个棋子的位置，设 \(f_{i,j}\) 是前 \(i\) 轮，另外一个棋子在 \(j\) 位置的最小答案，我们考虑 \(f\) 的转移：

• 移动在 \(q_i\) 位置上的棋子：\(f_{i+1,j}=f_{i,j}+|q_{i+1}-q_{i}|\)。

• 移动在 \(j\) 位置上的棋子：\(f_{i+1,q_i}=\min\{f_{i,j}+|q_{i+1}-j|\}\)。

考虑特殊考虑初始位置，或者说，考虑前 \(i\) 轮仅动了第一个或者第二个棋子的情况。我们设 \(pre_1(i)\) 是仅移动第一个棋子完成前 \(i\) 个要求的答案，\(pre_2(i)\) 是第二个。那么有：

• \(f_{i+1,q_i}=pre_1(i)+|q_{i+1}-b|\)。

• \(f_{i+1,q_i}=pre_2(i)+|q_{i+1}-a|\)。

最后答案应为 \(\min\{f(Q,i)\}\)，然后和 \(pre_1(Q)\) 和 \(pre_2(Q)\) 取 \(\min\)。

现在这个东西是 \(O(nQ)\) 的，考虑线段树优化 DP：

对于第一种操作是一个区间加的过程。

第二种操作我们对绝对值分讨，则要求区间里 \(f_{i,j}-j\) 和 \(f_{i,j}+j\) 的最小值，可以结合操作 \(1\) 直接维护。

后面的所有操作都是单点修改，可以每次暴力 \(O(\log n)\) 找点去修改，不影响上面的懒标记过程。

所以总复杂度为 \(O(n\log n)\)。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define Max(a,b) (a>b?a:b)
#define Min(a,b) (a<b?a:b)
#define next Cry_For_theMoon
#define il inline
#define pb(x) push_back(x)
#define is(x) insert(x)
#define sit set<int>::iterator
#define mapit map<int,int>::iterator
#define pi pair<int,int>
#define ppi pair<int,pi>
#define pp pair<pi,pi>
#define fr first
#define se second
#define vit vector<int>::iterator
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef double db;
using namespace std;
const ll MAXN=2e5+10,INF=1e15;
ll n,q,a,b,pos[MAXN],ans=INF;
ll pre[2][MAXN];
struct SegmenTree{
	ll val[MAXN<<2],tag[MAXN<<2];
	ll minn1[MAXN<<2],minn2[MAXN<<2];
	void pushup(int x){
		minn1[x]=min(minn1[lc(x)],minn1[rc(x)]);
		minn2[x]=min(minn2[lc(x)],minn2[rc(x)]);
	}
	void pushdown(int x,int l,int r){
		int mid=(l+r)>>1;
		if(l==mid){val[lc(x)]+=tag[x];}
		if(mid+1==r){val[rc(x)]+=tag[x];} 
		minn1[lc(x)]+=tag[x];minn2[lc(x)]+=tag[x];
		minn1[rc(x)]+=tag[x];minn2[rc(x)]+=tag[x];
		tag[lc(x)]+=tag[x];tag[rc(x)]+=tag[x];tag[x]=0;
	} 
	void build(int x,int l,int r){
		if(l==r){
			val[x]=INF;
			minn1[x]=minn2[x]=INF;
			return;
		}
		int mid=(l+r)>>1;
		build(lc(x),l,mid);build(rc(x),mid+1,r);
		pushup(x);
	}
	void update(int x,int l,int r,int ql,int qr,ll val1){
		if(ql<=l && qr>=r){
			if(l==r){val[x]+=val1;}
			minn1[x]+=val1;minn2[x]+=val1;
			tag[x]+=val1;
			return;
		}
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		if(ql<=mid)update(lc(x),l,mid,ql,qr,val1);
		if(qr>mid)update(rc(x),mid+1,r,ql,qr,val1);
		pushup(x); 
	}
	void modify(int x,int l,int r,int pos,ll num){
		if(l==r){
			val[x]=min(val[x],num);
			minn1[x]=val[x]-l;
			minn2[x]=val[x]+l;
			return;
		}
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		if(pos<=mid)modify(lc(x),l,mid,pos,num);
		else modify(rc(x),mid+1,r,pos,num); 
		pushup(x); 
	}
	ll query(int x,int l,int r,int pos){
		if(l==r)return val[x];
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		ll ans;
		if(pos<=mid)ans=query(lc(x),l,mid,pos);
		else ans=query(rc(x),mid+1,r,pos);
		pushup(x);return ans;
	}
	ll query1(int x,int l,int r,int ql,int qr){
		if(ql<=l && qr>=r)return minn1[x];
		pushdown(x,l,r);
		int mid=(l+r)>>1;ll ret=INF;
		if(ql<=mid)ret=min(ret,query1(lc(x),l,mid,ql,qr));
		if(qr>mid)ret=min(ret,query1(rc(x),mid+1,r,ql,qr));
		return ret;
	}
	ll query2(int x,int l,int r,int ql,int qr){
		if(ql<=l && qr>=r)return minn2[x];
		pushdown(x,l,r);
		int mid=(l+r)>>1;ll ret=INF;
		if(ql<=mid)ret=min(ret,query2(lc(x),l,mid,ql,qr));
		if(qr>mid)ret=min(ret,query2(rc(x),mid+1,r,ql,qr));
		return ret;
	}
}tree;
int main(){
	cin>>n>>q>>a>>b;
	rep(i,1,q){
		cin>>pos[i];
	}
	rep(i,1,q){
		if(i==1){
			pre[0][i]=abs(a-pos[1]);
			pre[1][i]=abs(b-pos[1]);
		}else{
			pre[0][i]=pre[0][i-1]+abs(pos[i-1]-pos[i]);
			pre[1][i]=pre[1][i-1]+abs(pos[i-1]-pos[i]);
		}
	}
	tree.build(1,1,n);
	rep(i,2,q){
		ll tmp=INF;
		tmp=min(tmp,pos[i]+tree.query1(1,1,n,1,pos[i]));
		if(pos[i]!=n){
			tmp=min(tmp,tree.query2(1,1,n,pos[i]+1,n)-pos[i]);
		}
		tree.update(1,1,n,1,n,abs(pos[i]-pos[i-1]));
		tree.modify(1,1,n,pos[i-1],tmp);
		tree.modify(1,1,n,pos[i-1],pre[0][i-1]+abs(pos[i]-b));
		tree.modify(1,1,n,pos[i-1],pre[1][i-1]+abs(pos[i]-a));
	}
	ans=min(ans,pre[0][q]);
	ans=min(ans,pre[1][q]);
	rep(i,1,n){
		ans=min(ans,tree.query(1,1,n,i));
	}
	cout<<ans<<endl;
	return 0;
}