# CFR 522 D. Closest Equals ( Segment Tree )

Problem - 522D - Codeforces

M 筆詢問，問 [ L, R ] 中，最近的相同元素距離是多少。若不存在，輸出 -1。

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

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;
}
```