Problem:
 Score : 600 points    Problem Statement We have N colored balls arranged in a row from left to right; the color of the i -th ball from the left is c_i .  You are given Q queries. The i -th query is as follows: how many different colors do the l_i -th through r_i -th balls from the left have?      Constraints  1\leq N,Q \leq 5 \times 10^5  1\leq c_i \leq N  1\leq l_i \leq r_i \leq N  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  Q  c_1  c_2  \cdots  c_N  l_1  r_1  l_2  r_2  :  l_Q  r_Q       Output Print Q lines. The i -th line should contain the response to the i -th query.        Sample Input 1 4 3
1 2 1 3
1 3
2 4
3 3      Sample Output 1 2
3
1   The 1 -st, 2 -nd, and 3 -rd balls from the left have the colors 1 , 2 , and 1 - two different colors.  The 2 -st, 3 -rd, and 4 -th balls from the left have the colors 2 , 1 , and 3 - three different colors.  The 3 -rd ball from the left has the color 1 - just one color.        Sample Input 2 10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8      Sample Output 2 1
2
2
1
2
2
6
3
3
3

Solution (Python):
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

@njit((i8[:, :], ), cache=True)
def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

@njit((i8[:], i8[:, :]), cache=True)
def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0
    

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        
        answers[i] = ans
    return answers

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q,2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): 
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    m2 = m * m
    g = [0]*q
    for i in range(q):
        l, r = nm()
        g[i] = ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    b = BIT(m)
    last = [n + 5]*(n+1)
    cr = -1
    for r in g:
        i = r & mask
        r >>= 20
        l = r & mask
        r >>= 20
        while cr < r:
            cr += 1
            b.bitadd(last[c[cr]], -1)
            last[c[cr]] = cr
            b.bitadd(cr, 1)
        ans[i] = b.bitsum(l, r+1)
    prn(ans)
    return

solve()

Solution (Python):
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

class BIT():
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for i in range(Q):
	l, r = map(int, input().split())
	q.append((i, l, r))
q.sort(key=lambda x: x[2])
ans = [-1 for _ in range(Q)]
b = BIT(n+1)
last_appeared = [0 for _ in range(n+1)]
rm = 0
for i, l, r in q:
	for j in range(rm+1, r+1):
		if last_appeared[c[j-1]] > 0:
			b.PointAdd(last_appeared[c[j-1]], -1)
		last_appeared[c[j-1]] = j
		b.PointAdd(j, 1)
	rm = j
	ans[i] = b.Sum(r) - b.Sum(l-1)
print(*ans, sep="\n")

Solution (Python):
import sys
from operator import itemgetter

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, q = na()
a = na()
lasts = [-1] * (n+1)
rs = []
for i in range(n):
    if lasts[a[i]] != -1:
        rs.append((lasts[a[i]], i))
    lasts[a[i]] = i

rs.sort(key=itemgetter(0))

qs = []
for i in range(q):
    u = na()
    qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=itemgetter(0))

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ft = [0] * (n+10)
anss = [0] * q
p = len(rs)-1
for q in qs[::-1]:
    while p >= 0 and rs[p][0] >= q[0]:
        addfenwick(ft, rs[p][1], 1)
        p -= 1
    anss[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in anss:
    print(v)