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):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    indices = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append(r)
        indices[l].append(i)

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for i, r in zip(indices[l], queries[l]):
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    class BIT():
        def __init__(self, n, x=1):
            self.n = n
            self.T = [0]*(n+1)

        def add(self, i, x):
            while i <= self.n:
                self.T[i] += x
                i += i & -i

        def lsum(self, i):
            ret = 0
            while i > 0:
                ret += self.T[i]
                i ^= i & -i
            return ret

    A = BIT(N)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            A.add(cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-A.lsum(r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.dat[i]
            i -= i & -i
        return s

n, q = LI()
ans = [0] * q
C = LI()
Q = defaultdict(list)
for i in range(q):
    l, r = LI()
    Q[r - 1] += [(i, l - 1)]

last = [-1] * (n + 1)
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for qi, li in Q[i]:
        ans[qi] = bit.sum(i) - bit.sum(li - 1)


print(*ans, sep="\n")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.dat[i]
            i -= i & -i
        return s

n, q = LI()
ans = [0] * q
C = LI()
Q = [[] for _ in range(n)]
for i in range(q):
    l, r = LI()
    Q[r - 1] += [(i, l - 1)]

last = [-1] * (n + 1)
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for qi, li in Q[i]:
        ans[qi] = bit.sum(i) - bit.sum(li - 1)


print(*ans, sep="\n")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.dat[i]
            i -= i & -i
        return s


n, q = LI()
ans = [0] * q
C = LI()
Q = [[] for _ in range(n)]
for i in range(q):
    l, r = LI()
    Q[r - 1] += [(i, l - 1)]

last = [-1] * (n + 1)
DD = {}
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for qi, li in Q[i]:
        ans[qi] = bit.sum(i) - bit.sum(li - 1)


print(*ans, sep="\n")

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

    def sum(self, i):
        i += 1
        s = 0
        while i > 0:
            s += self.dat[i]
            i -= i & -i
        return s


n, q = LI()
ans = [0] * q
C = LI()
Q = [[] for _ in range(n)]
for i in range(q):
    l, r = LI()
    Q[l - 1] += [(False, i)]
    Q[r - 1] += [(True, i)]


last = [-1] * (n + 1)
DD = {}
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for flg, qi in Q[i]:
        if flg:
            ans[qi] = bit.sum(i) - bit.sum(DD[qi] - 1)
        else:
            DD[qi] = i




print(*ans, sep="\n")

Solution (Python):


import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()
 
class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit
 
    def __getitem__(self, i):
        return self._tree[i + self._n]
 
    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])
 
    def add(self, i, v):
        self.update(i, self[i] + v)
 
    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from operator import add
def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))
 
    A = [0] * n
    used = [0] * n
    for i, c in enumerate(C):
        if used[c]:
            continue
        used[c] = 1
        A[i] = 1
    tree = SegmentTree(A, add, 0)
 
    next = [-1] * n
    used = [-1] * n
    for i in range(n - 1, -1, -1):
        c = C[i]
        if used[c] != -1:
            next[i] = used[c]
        used[c] = i
 
    queries = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        queries[i] = (l - 1 << 40) + (r << 20) + i
    queries.sort(reverse = 1)
    
    m = (1 << 20) - 1
    ans = [0] * q
    for l in range(n):
        while queries and queries[-1] >> 40 == l:
            lri = queries.pop()
            l = lri >> 40
            r = (lri >> 20) & m
            i = lri & m
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)
 
    print(*ans, sep = '\n')
resolve()

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from operator import add, itemgetter
def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))

    A = [0] * n
    used = [0] * n
    for i, c in enumerate(C):
        if used[c]:
            continue
        used[c] = 1
        A[i] = 1
    tree = SegmentTree(A, add, 0)

    next = [-1] * n
    used = [-1] * n
    for i in range(n - 1, -1, -1):
        c = C[i]
        if used[c] != -1:
            next[i] = used[c]
        used[c] = i

    queries = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        queries[i] = (l - 1, r, i)
    queries.sort(key = itemgetter(0), reverse = 1)

    ans = [0] * q
    for l in range(n):
        while queries and queries[-1][0] == l:
            l, r, i = queries.pop()
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)

    print(*ans, sep = '\n')
resolve()

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




def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))



class BIT:
	def __init__(self, n):
		self.n = n
		self.data = [0]*(n+1)
		self.el = [0]*(n+1)
	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s
	def add(self, i, x):
		
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i
	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)


def main():
	n,q=MI()
	C=[0]+LI()

	lr=[]

	for i in range(q):
		l,r=MI()
		lr.append([l,r,i])
	lr.sort(key=lambda x:x[1])
	
	R=[-1]*(n+1)

	B=BIT(n)
	now=1
	ans=[-1]*(q)
	for l,r,i in lr:
		while now<=r:
			if R[C[now]]!=-1:
				B.add(R[C[now]],-1)
			R[C[now]]=now
			B.add(R[C[now]],1)
			now+=1
		
		
		ans[i]=B.get(l-1,r)
	print(*ans,sep="\n")



if __name__ == "__main__":
	main()

Solution (Python):
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for i in range(Q)]

qs = [[] for _ in range(N)]
for i,(l,r) in enumerate(LR):
    qs[l-1].append((i,r-1))

from collections import defaultdict
hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1,-1,-1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): 
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): 
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): 
        return self._sum(r) - self._sum(l)
    def __str__(self): 
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bit = BinaryIndexedTree(N)

ans = [None] * Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l], -1)
    for i,r in qs[l]:
        ans[i] = r-l+1 + bit.sum(l,r+1)

print(*ans, sep='\n')

Solution (Python):
from numba import*
@njit(cache=1)
def main(N,Q,C,LR,A):
    data=[0]*(N+1)
    def add(i,x):
        i+=1
        while i<=N:
            data[i]+=x
            i+=i&-i
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
def input(): return sys.stdin.buffer.readline()
N,Q=map(int,input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
LR=np.array(sys.stdin.buffer.read().split(),dtype=np.int64).reshape(Q,2)
A=np.argsort(LR[:,1])
print(*main(N,Q,C,LR,A),sep='\n')

Solution (Python):
from sys import stdin

class BIT:
    def __init__(self, n):
        self.data = [0] * (n + 10)
        
    def upd(self, pos, val = 1):
        pos += 1
        while pos < len(self.data):
            self.data[pos] += val
            pos += pos & -pos
            
    def get(self, pos):
        ans = 0
        pos += 1
        while pos > 0:
            ans += self.data[pos]
            pos -= pos & -pos
        return ans
    
    def get_range(self, l, r):
        return self.get(r) - self.get(l - 1)

def main():
    n, q = map(int, stdin.readline().split())
    color = list(map(int, stdin.readline().split()))
    
    queries = []
    for i in range(q):
        l, r = map(int, stdin.readline().split())
        queries.append((l, r, i))
    queries.sort(key = lambda val: val[1])
    
    ans = [0] * q
    prev_pos = [0] * (n + 1)
    bit = BIT(n + 1)
    
    f = 0
    for cur_pos, color in enumerate(color, 1):
        bit.upd(prev_pos[color], -1)
        bit.upd(cur_pos, 1)
        prev_pos[color] = cur_pos
        
        while f < q and queries[f][1] == cur_pos:
            ans[queries[f][2]] = bit.get_range(queries[f][0], queries[f][1])
            f += 1
    print('\n'.join(map(str, ans)))
    
main()

Solution (Python):





class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)  

    def init(self, ls):
        assert len(ls) <= self.n
        
        for i, x in enumerate(ls):  
            self.add(i, x)

    def add(self, i, x):
        '''i番目の要素にxを足し込む'''
        i += 1  
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        '''[i,j)の区間の合計を取得'''
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        '''[,i)の合計を取得'''
        
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret


class RangeAddBIT:  
    
    
    
    
    
    
    def __init__(self, n: int):
        self.n = n
        self.bit1 = BIT(n)  
        self.bit2 = BIT(n)  

    def add(self, l: int, r: int, x):
        '''[l,r)の要素にxを足し込む'''
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        '''[l,r)の区間の合計を取得'''
        return self._sum(r) - self._sum(l)

    def _sum(self, i: int):
        '''[,i)の合計を取得'''
        return self.bit1._sum(i) * i + self.bit2._sum(i)


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd
N, Q = ints()
C = ints()
L, R = read_col(Q)
query = defaultdict(lambda: list())  
for i, (l, r) in enu(zip(L, R)):  
    query[r].append((l - 1, i))

segtree = RangeAddBIT(N + 10)  
idxprev = defaultdict(lambda: -1)  

ans = [-1] * Q
r_now = 0  
for r in range(1, N + 1):
    prev = idxprev[C[r - 1]]
    segtree.add(prev + 1, r, 1)
    idxprev[C[r - 1]] = r - 1
    for l, i in query[r]:
        ans[i] = segtree.sum(l, l + 1)
print(*ans, sep='\n')

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A):
        n = 1 << (len(A) - 1).bit_length()
        tree = [0] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = tree[i << 1] + tree[i << 1 | 1]
        self._n = n
        self._tree = tree

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._tree[i << 1] + self._tree[i << 1 | 1]

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = 0
        while l < r:
            if l & 1:
                l_val = l_val + self._tree[l]
                l += 1
            if r & 1:
                r -= 1
                r_val = self._tree[r] + r_val
            l >>= 1
            r >>= 1
        return l_val + r_val


def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))

    A = [0] * n
    next = [-1] * n
    used = [-1] * n
    for i in range(n - 1, -1, -1):
        c = C[i]
        A[i] = 1
        if used[c] != -1:
            next[i] = used[c]
            A[used[c]] = 0
        used[c] = i

    tree = SegmentTree(A)
    queries = [[] for _ in range(n)]
    for i in range(q):
        l, r = map(int, input().split())
        queries[l - 1].append((r, i))

    ans = [0] * q
    for l in range(n):
        for r, i in queries[l]:
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)

    print(*ans, sep = '\n')
resolve()

Solution (Python):
from operator import add
import sys
input = sys.stdin.buffer.readline

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]


ilrs = sorted(((i, l-1, r-1) for i, (l, r) in enumerate(lrs)), key = lambda t: t[2])


duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i


ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

print(*ans, sep = '\n')

Solution (Python):
import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()
 
def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])
 
    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])
 
main()

Solution (Python):





class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)  

    def init(self, ls):
        assert len(ls) <= self.n
        
        for i, x in enumerate(ls):  
            self.add(i, x)

    def add(self, i, x):
        '''i番目の要素にxを足し込む'''
        i += 1  
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        '''[i,j)の区間の合計を取得'''
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        '''[,i)の合計を取得'''
        
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret


class RangeAddBIT:  
    
    
    
    
    
    
    def __init__(self, n: int):
        self.n = n
        self.bit1 = BIT(n)  
        self.bit2 = BIT(n)  

    def add(self, l: int, r: int, x):
        '''[l,r)の要素にxを足し込む'''
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        '''[l,r)の区間の合計を取得'''
        return self._sum(r) - self._sum(l)

    def _sum(self, i: int):
        '''[,i)の合計を取得'''
        return self.bit1._sum(i) * i + self.bit2._sum(i)


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) 
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    


MOD = 10**9 + 7
INF = 2**31  

from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  
from functools import reduce
from math import gcd
N, Q = ints()
C = ints()
L, R = read_col(Q)
query = defaultdict(lambda: list())  
for i, (l, r) in enu(zip(L, R)):
    query[r].append((l - 1, i))

segtree = RangeAddBIT(N + 10)  
idxprev = defaultdict(lambda: -1)  

ans = [-1] * Q
r_now = 0  
for r in sorted(query.keys()):
    for j in range(r_now, r):
        prev = idxprev[C[j]]
        segtree.add(prev + 1, j + 1, 1)
        idxprev[C[j]] = j
    r_now = j
    for l, i in query[r]:
        ans[i] = segtree.sum(l, l + 1)
print(*ans, sep='\n')