0w1

CFR 522 D. Closest Equals ( Segment Tree )

Problem - 522D - Codeforces

題意:
給你長度 N 的數列 A[]。
M 筆詢問,問 [ L, R ] 中,最近的相同元素距離是多少。若不存在,輸出 -1。

制約:
1 ≤ N, M ≤ 5e5
abs( A[ i ] ) ≤ 1e9

解法:
可以很快想到,給每一個位置 i 紀錄前一個 A[ i ] 的位置 pre[ i ]。
如此一來,[ L, R ] 這個詢問就等價於求 [ L, R ] 中最小的 i - pre[ i ],其中 L ≤ pre[ i ]。
最後一個條件不難處理,透過依照左界排序詢問,可以把過期的元素刪掉。

複雜度:
O( N lg N )

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

const int MAXN = int( 5e5 );
const int MAXM = int( 5e5 );

int N, M;
int A[ MAXN ];
int L[ MAXM ], R[ MAXM ];
int ord[ MAXM ];
int pre[ MAXN ];
int nxt[ MAXN ];

int minv[ 1 << 20 ];

int ans[ MAXM ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M;
  for( int i = 0; i < N; ++i ) {
    cin >> A[ i ];
    static map< int, int > pos;
    if( pos.count( A[ i ] ) ) {
      nxt[ pre[ i ] = pos[ A[ i ] ] ] = i;
    } else {
      pre[ i ] = 0xc0c0c0c0;
    }
    pos[ A[ i ] ] = i;
  }
  for( int i = 0; i < M; ++i ) {
    cin >> L[ i ] >> R[ i ];
    --L[ i ];
    ord[ i ] = i;
  }
  sort( ord, ord + M, [ & ]( int i, int j ) { return L[ i ] < L[ j ]; } );
  function< void( int, int, int ) > build = [ & ]( int t, int lb, int rb ) {
    if( lb + 1 == rb ) return minv[ t ] = lb - pre[ lb ], void();
    build( t << 1, lb, lb + rb >> 1 );
    build( t << 1 | 1, lb + rb >> 1, rb );
    minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
  };
  build( 1, 0, N );
  for( int i = 0; i < M; ++i ) {
    function< void( int, int, int, int ) > kill = [ & ]( int t, int lb, int rb, int k ) {
      if( lb + 1 == rb ) return minv[ t ] = 0x3f3f3f3f, void();
      k < lb + rb >> 1 ? kill( t << 1, lb, lb + rb >> 1, k ) : kill( t << 1 | 1, lb + rb >> 1, rb, k );
      minv[ t ] = min( minv[ t << 1 ], minv[ t << 1 | 1 ] );
    };
    for( int j = i == 0 ? 0 : L[ ord[ i - 1 ] ]; j < L[ ord[ i ] ]; ++j ) {
      kill( 1, 0, N, nxt[ j ] );
    }
    function< int( int, int, int, int, int ) > query = [ & ]( int t, int lb, int rb, int ql, int qr ) {
      if( ql <= lb and rb <= qr ) return minv[ t ];
      if( qr <= lb or rb <= ql ) return 0x3f3f3f3f;
      return min( query( t << 1, lb, lb + rb >> 1, ql, qr ), query( t << 1 | 1, lb + rb >> 1, rb, ql, qr ) );
    };
    int x = query( 1, 0, N, L[ ord[ i ] ], R[ ord[ i ] ] );
    ans[ ord[ i ] ] = x > N ? - 1: x;
  }
  for( int i = 0; i < M; ++i ) {
    cout << ans[ i ] << "\n";
  }
  return 0;
}