ARC 073 F (嘘解法)

想定解法は segment tree だが、O(N^2) の DP を、隣の状態より strict に良い状態だけを残すような枝刈りしても通る。

発見した中でのワーストケースでは、
与えられる点が、
200000, 1, 100000, 50000, 75000, ...
のときに、保持する必要がある状態数が 20 近くになる。

#define N 200010
ll n, q, c, x[N];
set<P> dp[2];

int main(){
	cin>>n>>q>>x[0]>>c;
	rep(i, q) cin>>x[i+1];
	dp[0].insert(P(c, 0));
	for(int i = 1; i <= q; i++){
		int t = i%2;
		dp[t].clear();
		for(auto p: dp[!t]){
			dp[t].insert(P(x[i-1], p.snd+abs(x[i]-p.fst)));
			dp[t].insert(P(p.fst, p.snd+abs(x[i]-x[i-1])));
		}
		{
			auto it = dp[t].begin(), it2 = it; ++it2;
			while(it2!=dp[t].end()){
				while(it2!=dp[t].end() && it->snd+abs(it->fst-it2->fst)<=it2->snd){
					dp[t].erase(it2);
					it2 = it;
					++it2;
				}
				++it;
				if(it2!=dp[t].end()) ++it2;
			}
		}
		{
			auto it = dp[t].end();
			if(it!=dp[t].begin()) --it;
			auto it2 = it;
			if(it!=dp[t].begin()) --it2;
			while(it!=dp[t].begin()){
				while(it!=dp[t].begin() && it->snd+abs(it->fst-it2->fst)<=it2->snd){
					dp[t].erase(it2);
					it2 = it;
					if(it2!=dp[t].begin()) --it2;
				}
				if(it!=dp[t].begin()){
					--it;
					if(it2!=dp[t].begin()) --it2;
				}
			}
		}
	}
	ll res = 1e17;
	for(auto p: dp[q%2]) res = min(res, p.snd);
	cout<<res<<endl;
	return 0;
}