One Occurrence (Codeforces 1000F)
Tags: Others, divide and conquer

You are given an array $$$a$$$ consisting of $$$n$$$ integers, and $$$q$$$ queries to it. $$$i$$$-th query is denoted by two integers $$$l_i$$$ and $$$r_i$$$. For each query, you have to find any integer that occurs exactly once in the subarray of $$$a$$$ from index $$$l_i$$$ to index $$$r_i$$$ (a subarray is a contiguous subsegment of an array). For example, if $$$a = [1, 1, 2, 3, 2, 4]$$$, then for query $$$(l_i = 2, r_i = 6)$$$ the subarray we are interested in is $$$[1, 2, 3, 2, 4]$$$, and possible answers are $$$1$$$, $$$3$$$ and $$$4$$$; for query $$$(l_i = 1, r_i = 2)$$$ the subarray we are interested in is $$$[1, 1]$$$, and there is no such element that occurs exactly once.Can you answer all of the queries?

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^5$$$).The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 5 \cdot 10^5$$$).The third line contains one integer $$$q$$$ ($$$1 \le q \le 5 \cdot 10^5$$$).Then $$$q$$$ lines follow, $$$i$$$-th line containing two integers $$$l_i$$$ and $$$r_i$$$ representing $$$i$$$-th query ($$$1 \le l_i \le r_i \le n$$$).

Output: Answer the queries as follows:If there is no integer such that it occurs in the subarray from index $$$l_i$$$ to index $$$r_i$$$ exactly once, print $$$0$$$. Otherwise print any such integer.


Sample Inputs:
6
1 1 2 3 2 4
2
2 6
1 2

Sample Outputs:
4
0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += len(tree) // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = max(tree[2 * i], tree[2 * i + 1])
        i //= 2
    return

def find(s, t):
    s += len(tree) // 2
    t += len(tree) // 2
    ans = 0
    while s <= t:
        if s % 2 == 0:
            s //= 2
        else:
            ans = max(ans, tree[s])
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = max(ans, tree[t])
            t = (t - 1) // 2
    return ans
n = int(input())
a = [0] + list(map(int, input().split()))
m = 5 * pow(10, 5) + 5
x = [[] for _ in range(m)]
for i in range(1, n + 1):
    x[a[i]].append(i)
q = int(input())
ans = [0] * q
y = [[] for _ in range(m)]
for i in range(q):
    (l, r) = map(int, input().split())
    y[l].append((r, i))
inf = pow(10, 7)
tree = make_tree(m)
nx = [inf] * m
for i in range(1, m):
    xi = x[i]
    for j in range(len(xi) - 1):
        nx[xi[j]] = xi[j + 1]
    if xi:
        nx[xi[-1]] += xi[-1]
        update(xi[0], nx[xi[0]])
for l in range(1, m):
    for (r, i) in y[l]:
        j = find(l, r)
        if j > r:
            ans[i] = a[j % inf]
    nxl = nx[l]
    if nxl < inf:
        update(nxl, nx[nxl])
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [[] for _ in range(n)]
for i in range(q):
    (l, r) = map(lambda x: int(x) - 1, input().split())
    query[r].append((l, i))
m = 5 * 10 ** 5 + 10
left = [-1] * n
memo = [-1] * m
for i in range(n):
    left[i] = memo[a[i]] + 1
    memo[a[i]] = i
inf = 1 << 60
mask = (1 << 30) - 1
seg = segtree([inf for i in range(n)], min, inf)
ans = [0] * q
for r in range(n):
    if left[r] != -2:
        seg.update(left[r] - 1, inf)
    seg.update(r, (left[r] << 30) + a[r])
    for (l, idx) in query[r]:
        res = seg.query(l, r + 1)
        (res0, res1) = (res >> 30, res & mask)
        if res0 <= l:
            ans[idx] = res1
print('\n'.join(map(str, ans)))

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]

class segtree:

    def __init__(self, init, func, ide):
        self.n = len(init)
        self.func = func
        self.ide = ide
        self.size = 1 << (self.n - 1).bit_length()
        self.tree = [self.ide for i in range(2 * self.size)]
        for i in range(self.n):
            self.tree[self.size + i] = init[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.func(self.tree[2 * i], self.tree[2 * i | 1])

    def update(self, k, x):
        k += self.size
        self.tree[k] = x
        k >>= 1
        while k:
            self.tree[k] = self.func(self.tree[2 * k], self.tree[k * 2 | 1])
            k >>= 1

    def get(self, i):
        return self.tree[i + self.size]

    def query(self, l, r):
        l += self.size
        r += self.size
        l_res = self.ide
        r_res = self.ide
        while l < r:
            if l & 1:
                l_res = self.func(l_res, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_res = self.func(self.tree[r], r_res)
            l >>= 1
            r >>= 1
        return self.func(l_res, r_res)

    def debug(self, s=10):
        print([self.get(i) for i in range(min(self.n, s))])
n = int(input())
a = list(map(int, input().split()))
q = int(input())
query = [[] for _ in range(n)]
for i in range(q):
    (l, r) = map(lambda x: int(x) - 1, input().split())
    query[r].append((l, i))
m = 5 * 10 ** 5 + 10
left = [-1] * n
memo = [-2] * m
for i in range(n):
    left[i] = memo[a[i]] + 1
    memo[a[i]] = i
inf = 1 << 30
seg = segtree([(inf, inf) for i in range(n)], min, (inf, inf))
ans = [0] * q
for r in range(n):
    if left[r] != -2:
        seg.update(left[r] - 1, (inf, inf))
    seg.update(r, (left[r], a[r]))
    for (l, idx) in query[r]:
        res = seg.query(l, r + 1)
        if res[0] <= l:
            ans[idx] = res[1]
print('\n'.join(map(str, ans)))