CFR 522 D. Closest Equals ( Segment Tree )
題意:
給你長度 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; }