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
from numba import njit


def input(): return sys.stdin.readline()

N,Q = map(int,input().split())

C=np.array(input().split(), int)



queries=np.empty((Q,2),int)


for q in range(Q):
	l,r=map(int,input().split())
	
	queries[q][0] = l
	queries[q][1] = r
	



orderByR=np.argsort(queries[:,1])


mostRightColorIndex = np.zeros(N+1, int)

bitArray=np.zeros(N+1,int)

@njit
def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	
	
	ans=[0]*Q
	
	qindex = 0

	for n in range(N):
		

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			
			
			
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			
			qindex += 1

	return ans

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

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

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    
    LR.sort(reverse=True, key=lambda x:x[0])
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ft.add(ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ft.sum(r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))

Solution (Python):


import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append(i+(l-1)*10**6+(r-1)*10**12)

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort()
last = [None]*n
ans = [None]*q
nr = -1
for i in query:
    r = i//10**12
    l = i%10**12//10**6
    idx = i%10**6
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
print(*ans)

Solution (Python):
import sys
from operator import itemgetter
def input(): return sys.stdin.readline().rstrip()

class BinaryIndexedTree:  
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  

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

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

    def query(self, l, r):  
        return self.sum(r) - self.sum(l)



n, q = (int(x) for x in input().split())
C = list(int(x) - 1 for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(q)]

bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for i, (l, r) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for i, l, r in queries:
    while k <= r and k <= n:
        color = C[k]
        if color_right_index[color] != -1:
            bit.add(color_right_index[color], -1)
        color_right_index[C[k]] = k
        bit.add(k, 1)
        k += 1
    ANS[i] = bit.query(l, r + 1)

for ans in ANS:
    print(ans)

Solution (Python):
def examA():
    X = I()
    if X<30:
        ans = "No"
    else:
        ans = "Yes"
    print(ans)
    return

def examB():
    N, D = LI()
    cnt = 0
    for _ in range(N):
        x, y = LI()
        if x**2+y**2<=D**2:
            cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    N = 10**7
    K = I()
    cur = 0
    now = 1
    ans = -1
    for i in range(N):
        cur += 7 * now
        cur %= K
        if cur==0:
            ans = i+1
            break
        now *= 10
        now %= K
    print(ans)
    return

def examD():
    N = I()
    C = SI()
    cnt = 0
    l = 0; r = N-1
    while(l<r):
        while(l<N):
            if C[l]=="W":
                break
            l += 1
        while(0<=r):
            if C[r]=="R":
                break
            r -= 1
        if l<r:
            cnt += 1
            l += 1
            r -= 1
    ans = cnt
    print(ans)
    return

def examE():
    N, K = LI()
    A = LI()
    if K==0:
        print(max(A))
        return
    l = 0; r = inf
    while(r-l>1):
        now = (l+r)//2
        cnt = 0
        for a in A:
            cur = a//now
            if a%now==0:
                cur -= 1
            cnt += cur
        if cnt<=K:
            r = now
        else:
            l = now
        
        
    ans = r

    print(ans)
    return

def examF():
    
    class Bit():
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
            return

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

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

        def search(self, x):
            
            
            i = 0
            s = 0
            step = 1 << ((self.size).bit_length() - 1)
            while step:
                if i + step <= self.size and s + self.tree[i + step] < x:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return i

        def debug(self, k):
            return [self.sum(i) for i in range(k)]

        def inversion(self, A=[3, 10, 1, 8, 5]):
            res = 0
            for i, p in enumerate(A):
                self.add(p, 1)
                res += i + 1 - self.sum(p)
            return res
    N, Q = LI()
    C = LI()
    LR = []
    lastAppeared = [-1]*(N+1)
    for i in range(Q):
        l, r = LI()
        LR.append((l,r,i))
    LR.sort(key=lambda x:x[1])
    
    bit = Bit(N+2)
    ans = [0]*Q
    r = 1
    now = 0
    while(r<=N):
        if now==Q:
            break
        l0, r0, i0 = LR[now]
        while(r<=r0):
            c = C[r-1]
            if lastAppeared[c]>0:
                bit.add(lastAppeared[c],-1)
            lastAppeared[c] = r
            bit.add(lastAppeared[c])
            r += 1
        

        while(now<Q):
            l0,r0,i0 = LR[now]
            if r!=r0+1:
                break
            
            ans[i0] = bit.sum(r0)
            if l0>=1:
                ans[i0] -= bit.sum(l0-1)
            now += 1

    for v in ans:
        print(v)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep,alphabet_convert
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<60
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 9

sys.setrecursionlimit(10**5)

if __name__ == '__main__':
    examF()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

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

class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class ListList:
    """ tupleを一番目の添え字に関してソートする"""
    def __init__(self, max_value_list):
        """
        :param max_value_list: tuple = (i, j, k) を考えた時、  max_value_list = (j_max, k_max)
        """
        self.list_list = []
        self.separation = [0]
        self.max_value_list = list(map(lambda x: x.bit_length(), max_value_list))
        for a in self.max_value_list:
            self.separation.append(self.separation[-1] + a)
        self.separation.reverse()
        self.mask = list(map(lambda x: x-1, self.separation))

    def append(self, array):
        temp = 0
        for x, i in zip(array, self.separation):
            temp += x<<i
        self.list_list.append(temp)

    def sort(self, reverse=False):
        return self.list_list.sort(reverse=reverse)

    def __getitem__(self, item):
        temp = self.list_list[item]
        array = []
        for a in self.max_value_list:
            array = [temp&((1<<a)-1)] + array
            temp>>=a
        array = [temp] + array
        return array

    def __iter__(self):
        for i in range(len(self.list_list)):
            yield self[i]

    def __str__(self):
        text = []
        for a in self:
            text.append("[" + ", ".join(list(map(str, a))) + "]")
        return "[" + ", ".join(text) + "]"

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.Q = len(query)
        self.query = ListList((len(array),self.Q))
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((r,l,i))
        self.query.sort()
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * self.Q
        r0 = 0
        for r, l, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res



N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []
for i in range(Q):
    l, r = map(int, input().split())
    query.append((l,r))



RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

Solution (Python):
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=[0]+L()
Q=[L()+[i] for i in range(q)]
Q.sort(key=lambda x:x[1])
ans=[0]*(q)
lastapp=[0 for i in range(n+1)]

No=2**19
BIT=[0]*(No+1)
def addbit(i,x):
    while i<=No:
        BIT[i]+=x
        i+= i&-i
def getsum(i):
    s=0
    while i:
        s+=BIT[i]
        i-= i&-i
    return s
def sumbit(l,r):
    return getsum(r)-getsum(l-1)

j=1
for l,r,i in Q:
    while j<=r:
        t=c[j]
        if lastapp[t]:
            addbit(lastapp[t],-1)
        addbit(j,1)
        lastapp[t]=j
        j+=1
    ans[i]=sumbit(l,r)
print(*ans, sep = "\n")

Solution (Python):
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=[0]+L()
Q=[L()+[i] for i in range(q)]
Q.sort(key=lambda x:x[1])
ans=[0]*(q)
lastapp=[0 for i in range(n+1)]

No=2
while No<=n:
    No*=2
BIT=[0]*(No+1)
def addbit(i,x):
    while i<=No:
        BIT[i]+=x
        i+= i&-i
def getsum(i):
    s=0
    while i:
        s+=BIT[i]
        i-= i&-i
    return s
def sumbit(l,r):
    return getsum(r)-getsum(l-1)

j=1
for l,r,i in Q:
    while j<=r:
        t=c[j]
        if lastapp[t]:
            addbit(lastapp[t],-1)
        addbit(j,1)
        lastapp[t]=j
        j+=1
    ans[i]=sumbit(l,r)
for i in ans:
    print(i)

Solution (Python):
import sys

def main():
	n, q = map(int, sys.stdin.readline().split())
	c = list(map(int, sys.stdin.readline().split()))
	fenwick = [0] * n
	
	def add(i, v):
		while i < n:
			fenwick[i] += v
			i = (i | (i + 1))
	
	def get(r):
		res = 0
		while r >= 0:
			res += fenwick[r]
			r = (r & (r + 1)) - 1
		return res
	
	def get_seg(l, r):
		return get(r) - get(l - 1)
		
	by_r = [[] for i in range(n)]
	for t in range(q):
		l, r = map(int, sys.stdin.readline().split())
		l, r = l - 1, r - 1
		by_r[r].append((l, t))
	last_ent = [-1] * (n + 1)
	ans = [0] * q
	for r in range(n):
		p = last_ent[c[r]]
		if p != -1:
			add(p, -1)	
		last_ent[c[r]] = r
		add(r, 1)
		for quer in by_r[r]:
			l, num = quer
			ans[num] = get_seg(l, r)
	print('\n'.join([str(x) for x in ans]))
	
main()

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

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def update(x,i):
    if good[x]==-1:
        good[x]=i
        bit.add(i,1)
    else:
        bit.add(good[x],-1)
        good[x]=i
        bit.add(good[x],1)
    return
    
N,Q=map(int,read().split())
c=tuple(map(int,read().split()))
Query=[]
for i in range(Q):
    l,r=map(lambda x:int(x)-1,read().split())
    Query.append(r*10**12+l*10**6+i)
Query.sort()
ans=[-1]*Q
good=[-1]*(N+1)
bit=BIT(N)

i=0
for w in Query:
    R=w//10**12
    w%=10**12
    L=w//10**6
    w%=10**6
    while(i<=R):
        update(c[i],i)
        i+=1
    ans[w]=bit.cum(L,R+1)

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

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

class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+2)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array, start=1):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        i += 1
        while i <= self.n:
            self.tree[i] += x
            i += i & -i

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = 0    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos-1, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res



N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []
for i in range(Q):
    l, r = map(int, input().split())
    query.append((l,r))

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

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

class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res



N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []
for i in range(Q):
    l, r = map(int, input().split())
    query.append((l,r))

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

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

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def update(x,i):
    if good[x]==-1:
        good[x]=i
        bit.add(i,1)
    else:
        bit.add(good[x],-1)
        good[x]=i
        bit.add(good[x],1)
    return
    
N,Q=map(int,read().split())
c=tuple(map(int,read().split()))
Query=[]
for i in range(Q):
    l,r=map(lambda x:int(x)-1,read().split())
    Query.append((l,r,i))
Query.sort(key=lambda x:x[1])
ans=[-1]*Q
good=[-1]*(N+1)
bit=BIT(N)

i=0
for L,R,w in Query:
    while(i<=R):
        update(c[i],i)
        i+=1
    ans[w]=bit.cum(L,R+1)

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

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

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=list(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()

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

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    li=[list(map(lambda x:int(x)-1,read().split()))+[i] for i in range(Q)]
    Query=[(li[i][0],li[i][1],i) for i in range(Q)]
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()