Closest Equals (Codeforces 522D)
Tags: Others, *special

You are given sequence a1, a2, ..., an and m queries lj, rj (1 ≤ lj ≤ rj ≤ n). For each query you need to print the minimum distance between such pair of elements ax and ay (x ≠ y), that:  both indexes of the elements lie within range [lj, rj], that is, lj ≤ x, y ≤ rj;  the values of the elements are equal, that is ax = ay. The text above understands distance as |x - y|.

Input: The first line of the input contains a pair of integers n, m (1 ≤ n, m ≤ 5·105) — the length of the sequence and the number of queries, correspondingly. The second line contains the sequence of integers a1, a2, ..., an ( - 109 ≤ ai ≤ 109). Next m lines contain the queries, one per line. Each query is given by a pair of numbers lj, rj (1 ≤ lj ≤ rj ≤ n) — the indexes of the query range limits.

Output: Print m integers — the answers to each query. If there is no valid match for some query, please print -1 as an answer to this query.


Sample Inputs:
5 3
1 1 2 3 2
1 5
2 4
3 5

6 5
1 2 1 3 2 3
4 6
1 3
2 5
2 4
1 6

Sample Outputs:
1
-1
2

2
2
3
-1
2

Solution (Python):
import sys

class Fenwick(object):

    def __init__(self, n):
        self.n = n
        self.a = [10 ** 9 for i in range(n)]
        self.w = 10 ** 9

    def zag(self, i, zn):
        self.w = min(self.w, zn)
        while i < self.n:
            self.a[i] = min(self.a[i], zn)
            i = i | i + 1

    def pol(self, r):
        ans = 10 ** 9
        while r >= 0:
            if ans > self.a[r]:
                ans = self.a[r]
            if ans == self.w:
                break
            r = (r & r + 1) - 1
        return ans
(n, m) = [int(x) for x in sys.stdin.readline().split()]
a = [int(x) for x in sys.stdin.readline().split()]
nd = [-1 for i in range(0, len(a))]
vi = {}
for i in range(0, len(a)):
    if a[i] in vi:
        nd[i] = vi[a[i]]
    vi[a[i]] = i
inp = sys.stdin.readlines()
och = [[] for i in range(n)]
for i in range(m):
    (l, r) = inp[i].split()
    och[int(r) - 1].append((int(l) - 1, i))
der = Fenwick(2 ** 19)
ans = [None for i in range(0, m)]
le = -1
for r in range(n):
    if nd[r] != -1:
        der.zag(500000 - nd[r] + 1, r - nd[r])
        le = max(le, nd[r])
    for (l, ind) in och[r]:
        if l > le:
            ans[ind] = -1
            continue
        zn = der.pol(500000 - l + 1)
        if zn == 10 ** 9:
            zn = -1
        ans[ind] = zn
print('\n'.join((str(zn) for zn in ans)))

Solution (Python):
import sys

class Fenwick(object):

    def __init__(self, n):
        self.n = n
        self.a = [10 ** 9 for i in range(n)]
        self.w = 10 ** 9

    def zag(self, i, zn):
        self.w = min(self.w, zn)
        while i < self.n:
            self.a[i] = min(self.a[i], zn)
            i = i | i + 1

    def pol(self, r):
        ans = 10 ** 9
        while r >= 0:
            if ans > self.a[r]:
                ans = self.a[r]
            if ans == self.w:
                break
            r = (r & r + 1) - 1
        return ans
(n, m) = [int(x) for x in sys.stdin.readline().split()]
a = [int(x) for x in sys.stdin.readline().split()]
nd = [-1 for i in range(0, len(a))]
vi = {}
for i in range(0, len(a)):
    if a[i] in vi:
        nd[i] = vi[a[i]]
    vi[a[i]] = i
inp = sys.stdin.readlines()
och = [[] for i in range(n)]
for i in range(m):
    (l, r) = inp[i].split()
    och[int(r) - 1].append((int(l) - 1, i))
der = Fenwick(2 ** 19)
ans = [None for i in range(0, m)]
le = -1
for r in range(n):
    if nd[r] != -1:
        der.zag(500000 - nd[r] + 1, r - nd[r])
        le = max(le, nd[r])
    for (l, ind) in och[r]:
        if l > le:
            ans[ind] = -1
            continue
        zn = der.pol(500000 - l + 1)
        if zn == 10 ** 9:
            zn = -1
        ans[ind] = zn
print('\n'.join((str(zn) for zn in ans)))

Solution (Python):
import sys
readline = sys.stdin.readline

class Dual_Segment_Tree:

    def __init__(self, N, f_act, e_act, operate, lst):
        self.N = N
        self.f_act = f_act
        self.e_act = e_act
        self.operate = operate
        self.lst = [None] * self.N
        for (i, x) in enumerate(lst):
            self.lst[i] = x
        self.segment_tree_act = [self.e_act] * (self.N + self.N)

    def __getitem__(self, i):
        if type(i) is int:
            if -self.N <= i < 0:
                i += self.N * 2
            elif 0 <= i < self.N:
                i += self.N
            else:
                raise IndexError('list index out of range')
            self.Propagate_Above(i)
            return self.Operate_At(i)
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None or a < -self.N:
                a = 0
            elif self.N <= a:
                a = self.N
            elif a < 0:
                a += self.N
            if b == None or self.N <= b:
                b = self.N
            elif b < -self.N:
                b = 0
            elif b < 0:
                b += self.N
            return self.lst[slice(a, b, c)]

    def Operate_At(self, i):
        return self.operate(self.lst[i - self.N], self.segment_tree_act[i])

    def Propagate_At(self, i):
        self.segment_tree_act[i << 1] = self.f_act(self.segment_tree_act[i << 1], self.segment_tree_act[i])
        self.segment_tree_act[i << 1 | 1] = self.f_act(self.segment_tree_act[i << 1 | 1], self.segment_tree_act[i])
        self.segment_tree_act[i] = self.e_act

    def Propagate_Above(self, i):
        H = i.bit_length() - 1
        for h in range(H, 0, -1):
            self.Propagate_At(i >> h)

    def Operate_Range(self, a, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        L0 = L // (L & -L)
        R0 = R // (R & -R) - 1
        self.Propagate_Above(L0)
        self.Propagate_Above(R0)
        while L < R:
            if L & 1:
                self.segment_tree_act[L] = self.f_act(self.segment_tree_act[L], a)
                L += 1
            if R & 1:
                R -= 1
                self.segment_tree_act[R] = self.f_act(self.segment_tree_act[R], a)
            L >>= 1
            R >>= 1

    def Update(self):
        for i in range(1, self.N):
            self.Propagate_At(i)
            self.segment_tree_act[i] = self.e_act

    def __str__(self):
        import copy
        segment_tree_act = copy.deepcopy(self.segment_tree_act)
        for i in range(1, self.N):
            segment_tree_act[i << 1] = self.f_act(segment_tree_act[i << 1], segment_tree_act[i])
            segment_tree_act[i << 1 | 1] = self.f_act(segment_tree_act[i << 1 | 1], segment_tree_act[i])
            segment_tree_act[i] = self.e_act
            segment_tree_act[i] = self.e_act
        return '[' + ', '.join(map(str, [self.operate(x, a) for (x, a) in zip(self.lst, segment_tree_act[self.N:])])) + ']'
(N, M) = map(int, readline().split())
A = list(map(int, readline().split()))
query = [[] for r in range(N + 1)]
for m in range(M):
    (l, r) = map(int, readline().split())
    l -= 1
    query[r].append((l, m))
ans_lst = [None] * M
prev = {}
inf = 1 << 30
DST = Dual_Segment_Tree(N + 1, min, inf, min, [inf] * (N + 1))
for r in range(1, N + 1):
    if A[r - 1] in prev:
        i = prev[A[r - 1]]
        DST.Operate_Range(r - 1 - i, 0, i + 1)
    prev[A[r - 1]] = r - 1
    for (l, q) in query[r]:
        ans = DST[l]
        if ans == inf:
            ans = -1
        ans_lst[q] = ans
print(*ans_lst, sep='\n')