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

F: Many Moves - AtCoder Regular Contest 073 | AtCoder

題意：
在一個一維的棋盤上，你有兩顆棋，一顆在 A 位置，另一顆在 B 位置。有 Q 次操作，第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後，可能的最低總花費是多少。

制約：
1≦N,Q≦200,000
1≦A,B≦N
1≦xi≦N

解法：
考慮動態規劃，可以發現狀態只需要紀錄其中一顆不在前一個詢問位置的旗子的位置，以及對應的最小花費。
轉移只有兩種，一種是將 X[ i - 1 ] 的棋子移動到 X[ i ]，狀態不變。
令一種是轉移到 X[ i - 1 ]，並從當前狀態的位置移動到 X[ i ]。
這可以用線段樹一併處理，前者只需要做區間加值。
後者的狀態和轉移式可以這樣描述：
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 ] )
可以發現，只要維護兩顆線段樹，一個存進去的時候都減掉自己的下標，另一個都加自己的下標，就只是純樸的 RMQ 問題。

時間 / 空間複雜度：
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;
}