CodeForces 522D Closest Equals

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// Reference: https://www.cnblogs.com/AC-Phoenix/p/4347347.html
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 500001, INF = 0x3f3f3f3f;
int n, m, a[N], l[N], r[N], order[N], ans[N], tr[N];
unordered_map<int , int> mp;
int main() {
    int i, j;
    scanf("%d%d", &n ,&m);
    for (i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (i = 1; i <= m; ++i) scanf("%d%d", &l[i], &r[i]), order[i] = i;
    memset(tr, 0x3f, sizeof(tr));
    memset(ans, 0x3f, sizeof(ans));
    sort(order + 1, order + 1 + m, [&] (int i, int j) {
        return r[i] < r[j]; // sort queries by r.
    });
    for (i = j = 1; i <= m; ++i) { // for each query.
        int o = order[i];
        while (j <= r[o]) { // deal with numbers within [1, r].
            if (mp[a[j]]) { // have met a[j] before.
                int pos = mp[a[j]];
                for(int k = pos; k; k -= k & -k)
                    // stored the info (min value) into binary indexed tree.
                    tr[k] = min(tr[k], j - pos);
            }
            mp[a[j]] = j;
            ++j;
        }
        for(int k = l[o]; k <= r[o]; k += k & -k)
            ans[o] = min(ans[o], tr[k]);
    }
    for(i = 1; i <= m; ++i)
        printf("%d\n", ans[i] == INF? -1: ans[i]);
}