# ARC 073 F - Many Moves ( DP, Segment Tree )

F: Many Moves - AtCoder Regular Contest 073 | AtCoder

1≦N,Q≦200,000
1≦A,B≦N
1≦xi≦N

dp[ i ][ j ]: i 次操作後，一顆棋子在 X[ i - 1 ] 位置，另一顆棋子在 j 位置，此時最小總花費
dp[ i ][ X[ i - 1 ] ] = min( dp[ i - 1 ][ j ] + abs( X[ i ] - j ) )
= min( min( dp[ i - 1 ][ j ] - j for j in [ 0, x ) ) + X[ i ], min( dp[ i - 1 ][ j ] + j for j in [ X[ i ], N ] ) - X[ i ] )

O( N lg N + Q lg N ) / O( N )

```#include <bits/stdc++.h>
using namespace std;

const int MAXN = int( 2e5 );
const int MAXQ = int( 2e5 );

int N, Q, A, B;
int X[ MAXQ + 1 ];

const long long INF64 = 0x3f3f3f3f3f3f3f3fLL;

#define minus __myminus // collision with namespace
#define plus __myplus

struct itvt {
long long minv[ MAXN << 2 ];
long long tag[ MAXN << 2 ];
void init() {
memset( minv, INF64, sizeof( minv ) );
}
void pull( int t ) {
minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
}
void push( int t ) {
minv[ t << 1 ] += tag[ t ];
tag[ t << 1 ] += tag[ t ];
minv[ t << 1 | 1 ] += tag[ t ];
tag[ t << 1 | 1 ] += tag[ t ];
tag[ t ] = 0;
}
void update( int t, int lb, int rb, int k, long long v ) {
if( lb + 1 == rb ) {
minv[ t ] = min( minv[ t ], 1LL * v );
return;
}
int mid = lb + rb >> 1;
push( t );
if( k < mid ) update( t << 1, lb, mid, k, v );
else update( t << 1 | 1, mid, rb, k, v );
pull( t );
}
long long query( int t, int lb, int rb, int ql, int qr ) {
if( qr <= lb or rb <= ql ) return INF64;
if( ql <= lb and rb <= qr ) return minv[ t ];
int mid = lb + rb >> 1;
push( t );
long long res = min( query( t << 1, lb, mid, ql, qr ), query( t << 1 | 1, mid, rb, ql, qr ) );
pull( t );
return res;
}
} minus, plus;

signed main() {
ios::sync_with_stdio( 0 );
cin >> N >> Q >> A >> B;
--A, --B;
for( int i = 1; i <= Q; ++i ) {
cin >> X[ i ];
--X[ i ];
}
X[ 0 ] = A;
minus.init();
plus.init();
minus.update( 1, 0, N, B, -B );
plus.update( 1, 0, N, B, B );
for( int i = 1; i <= Q; ++i ) {
int x = X[ i ];
long long to_x = min( x + minus.query( 1, 0, N, 0, x ), plus.query( 1, 0, N, x, N ) - x );
minus.minv[ 1 ] += abs( X[ i ] - X[ i - 1 ] );
minus.tag[ 1 ] += abs( X[ i ] - X[ i - 1 ] );
plus.minv[ 1 ] += abs( X[ i ] - X[ i - 1 ] );
plus.tag[ 1 ] += abs( X[ i ] - X[ i - 1 ] );
minus.update( 1, 0, N, X[ i - 1 ], to_x - X[ i - 1 ] );
plus.update( 1, 0, N, X[ i - 1 ], to_x + X[ i - 1 ] );
}
long long ans = INF64;
for( int i = 0; i < N; ++i ) {
ans = min( ans, minus.query( 1, 0, N, i, i + 1 ) + i );
}
cout << ans << endl;
return 0;
}
```