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

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

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sort_index = sorted(list(range(len(sect))), key=lambda i: sect[i][0])

    bit = [0] * (N + 1)

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

    def sum(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i & -i
        return res

    ans = [0] * Q
    for i in sort_index:
        r, l, n = sect[i]
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def add(self, idx, x):
        while idx <= self.n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

n, q = map(int, input().split())
a = list(map(int, input().split()))
pi = [-1] * (n + 1)  
ps = [[] for i in range(n)]

for i in range(n):
    l = pi[a[i]]
    
    if l != -1:
        ps[l].append(i)
    
    pi[a[i]] = i

qs = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))

d = BIT(n)
ans = [0] * q


for x in range(n - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    
    for r, i in qs[x]:
        
        ans[i] = (r - x + 1) - d.query(r)

print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,q= map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) + [i] for i in range(q)]
for i in range(q):
    C[i][0] -= 1
    C[i][1] -= 1
for i in range(n):
    A[i] -= 1

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
  
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
  
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

B = Bit(n+1)
ANS = [-1] * q
C.sort(key=lambda x:x[1])
G = [-1] * (max(A)+1)
ind = 0
for i in range(n):
    a = A[i]
    if G[a] != -1:
        
        B.add(G[a]+1, -1)
    G[a] = i
    
    B.add(G[a]+1, 1)
    while ind < q and C[ind][1] == i:
        
        ANS[C[ind][2]] = B.sum(C[ind][1]+1) - B.sum(C[ind][0]+1-1)
        ind += 1

for i in range(q):
    print(ANS[i])

Solution (Python):
import numpy as np

def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    N, Q = inp[:2]
    C = inp[2: 2+N]
    L, R = inp[2+N::2] - 1, inp[3+N::2] - 1

    just_left = {}
    segments = []
    for i in range(N):
        c = C[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(Q):
        segments.append((R[i], 1, L[i], i))

    segments.sort()
    bit = np.zeros(N + 2, dtype=np.int64)
    ans = np.zeros(Q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, N + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))

    return ans

def main():
    inp = np.fromstring(open(0).read(), dtype=np.int64, sep=' ')
    ans = solve(inp)
    print("\n".join(map(str,ans)))
    

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    from my_module import solve
    main()

Solution (Python):

import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline

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

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def add(self, idx, x):
        while idx <= n:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

n, q = map(int, input().split())
a = list(map(int, input().split()))
pi = [-1] * (n + 1)  
ps = [[] for i in range(n)]

for i in range(n):
    l = pi[a[i]]
    if l != -1:
        ps[l].append(i)
    pi[a[i]] = i

qs = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    qs[l].append((r, i))

d = BIT(n)
ans = [0] * q

for x in range(n - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    
    for r, i in qs[x]:
        ans[i] = (r - x + 1) - d.query(r)

print(*ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

N, Q = MAP()
c = LIST()
ps = [[] for _ in range(N+1)]
qs = [[] for _ in range(N+1)]
for i in range(Q):
    l, r = MAP()
    qs[l].append((r, i))

checked = [-1]*(N+1)
for i, x in enumerate(c):
    if checked[x] != -1:
        ps[checked[x]].append(i+1)
    checked[x] = i+1

ans = [-1]*Q
bit = Bit(N)

for x in range(N, 0, -1):
    for y in ps[x]:
        bit.add(y, 1)
    for r, i in qs[x]:
        ans[i] = r-x+1-bit.sum(r)

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

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))




LEN=N+3

BIT=[0]*(LEN+1) 

def update(v,w): 
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) 

def getvalue(v): 
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) 
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    
    
    ANS[ind]=getvalue(y)

print(*ANS)

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))




LEN=N+3

BIT=[0]*(LEN+1) 

def update(v,w): 
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) 

def getvalue(v): 
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) 
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    
    
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")

Solution (Python):
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
for i in range(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in range(N)]
for i,x in enumerate(c):A[x].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
def G(i):
	s=0
	while i:s+=B[i];i-=i&-i
	return s
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=x>>40
	r=x>>20&N
	i=x&N
	while t+1<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	o[i]=G(r)-G(l-1)
for i in o:print(i)

Solution (Python):

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [[i,LI()] for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
for i in range(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in range(N)]
for i,x in enumerate(c):A[x].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
def G(i):
	s=0
	while i:s+=B[i];i-=i&-i
	return s
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=x>>40
	r=x>>20&N
	i=x&N
	while t+1<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	o[i]=G(r)-G(l-1)
for i in o:print(i)

Solution (Python):
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
for i in range(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in range(N)]
for i,x in enumerate(c):A[x].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
def G(i):
	s=0
	while i:s+=B[i];i-=i&-i
	return s
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=x>>40
	r=x>>20&N
	i=x&N
	while t+1<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	o[i]=G(r)-G(l-1)
for i in o:print(i)

Solution (Python):
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self, N):
        for i in range(N):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = [a-1 for a in LIST()]

LR = []
for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    LR.append((l, r, i))

LR.sort(key=itemgetter(1))
prev = [-1] * N
bit = BIT(N)
j = 0
ans = [0] * Q
for l, r, i in LR:
    while j <= r:
        if prev[A[j]] != -1:
            bit.add(prev[A[j]], -1)
        prev[A[j]] = j
        bit.add(j, 1)
        j += 1
    ans[i] = bit.get(l, r+1)

for a in ans:
    print(a)

Solution (Python):

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = [[i,LI()] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

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

    def __add(self, ind, num):
        while(ind <= self.n):
            self.bit[ind - 1] += num
            ind += ind & -ind

    def range_add(self, s, t, x):
        self.__add(s,x)
        self.__add(t+1,-x)

    def query(self, i):
        ret = 0
        while(i > 0):
            ret += self.bit[i-1]
            i -= i & -i
        return ret

n,q = map(int, input().split())
a = list(map(int, input().split()))
m = 10**6 + 1
prev = [-1]*m

query = []
for i in range(q):
    l,r = map(int, input().split())
    l,r = l-1,r-1
    query.append((l,r,i))
ans = [0]*q
query.sort(key=lambda x: x[1])

BIT = Binary_Indexed_Tree_RAQ(n+1)
cur = 0
for l,r,i in query:
    while cur <= r:
        ai = a[cur]
        BIT.range_add(prev[ai]+2, cur+1, 1)
        prev[ai] = cur
        cur += 1
    ans[i] = BIT.query(l+1)
print(*ans, sep="\n")

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



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

MaxLength = N
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): 
    for j in range(Depth):
        if index < len(FenwickTree[j]):
            FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): 
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Solution (Python):
def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append(i+l*(10**6)+r*(10**12))

    lr.sort()  
    d = {}  
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

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


    bit = BIT([0]*N)  
    a = 0  
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1:
            x = lr[a]
            r = x//(10**12)
            x %= 10**12
            l = x//(10**6)
            j = x % (10**6)
            if r == i:
                ANS[j] = bit.query(r)-bit.query(l-1)
                a += 1
            else:
                break

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


if __name__ == '__main__':
    main()

Solution (Python):
I = lambda:map(int,input().split())
N = 0xfffff
n, q = I()
c = list(I())
Q = []
for i in range(q):
    l, r = I()
    Q.append(l << 40 | r << 20 | i)

Q.sort()
A = [[] for i in range(N)]
for i, x in enumerate(c):
    A[x].append(i)

B = [0] * N
def P(i, x):
    i+=1
    while i <= n:
        B[i] += x
        i += i & -i

def G(i):
    s = 0
    while i:
        s += B[i]
        i -= i & -i
    return s

for i in A:
    if i:
        P(i[0], 1)
        i.reverse()

t = 0
o = [0] * q
for x in Q:
    l = x >> 40
    r = x >> 20 & N
    i = x & N
    while t+1 < l:
        b = A[c[t]]
        P(b[-1], -1)
        b.pop()
        if b:
            P(b[-1], 1)
        t += 1
    o[i] = G(r) - G(l-1)

for i in o:
    print(i)

Solution (Python):
import sys
I = lambda:map(int,sys.stdin.readline().split())
N = 0xfffff
n, q = I()
c = list(I())
Q = []
for i in range(q):
    l, r = I()
    Q.append(l << 40 | r << 20 | i)

Q.sort()
A = [[] for i in range(N)]
for i, x in enumerate(c):
    A[x].append(i)

B = [0] * N
def P(i, x):
    i+=1
    while i <= n:
        B[i] += x
        i += i & -i

def G(i):
    s = 0
    while i:
        s += B[i]
        i -= i & -i
    return s

for i in A:
    if i:
        P(i[0], 1)
        i.reverse()

t = 0
o = [0] * q
for x in Q:
    l = x >> 40
    r = x >> 20 & N
    i = x & N
    while t+1 < l:
        b = A[c[t]]
        P(b[-1], -1)
        b.pop()
        if b:
            P(b[-1], 1)
        t += 1
    o[i] = G(r) - G(l-1)

for i in o:
    print(i)

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

BIT = [0]*(N+1)  

def BIT_query(idx):  
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):  
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))  
lastAppeared = [-1]*(N+1)  
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)  
queries.sort()  

curR = 0  
for i in range(Q):
    query = queries[i]
    r = query//10**12
    l = (query//10**6)%(10**6)
    q = query % 10**6
    while curR < r:
        curR += 1
        color = c[curR]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)  
        lastAppeared[color] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)  
for i in range(Q):
    print(ans[i])

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



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

MaxLength = 2 ** 19
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): 
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): 
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Solution (Python):


import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline



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

MaxLength = 2 * N
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): 
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): 
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Solution (Python):
import sys

input = sys.stdin.buffer.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, r, i))
LR.sort(key=lambda x: x[1])


BIT = [0] * (n + 1)


def update(idx, val):
    while idx <= n:
        BIT[idx] += val
        idx += idx & (-idx)


def query(idx):
    res = 0
    while idx > 0:
        res += BIT[idx]
        idx -= idx & (-idx)
    return res


pos = [-1] * (n + 1)


def func(idx):
    temp = C[idx]
    if pos[temp] == -1:
        pos[temp] = idx + 1
        update(idx + 1, 1)
    else:
        pre = pos[temp]
        pos[temp] = idx + 1
        update(pre, -1)
        update(idx + 1, 1)


ans = [0] * (q)
idx = 0
for i in range(q):
    l, r, ans_num = LR[i]
    
    l -= 1
    r -= 1
    while idx < r + 1:  
        if idx < n:  
            func(idx)
            idx += 1
        else:
            break
    res = 0
    res += query(r + 1)
    if l > 0:
        res -= query(l)
    ans[ans_num] = res

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

Solution (Python):
class BIT: 
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out



import sys
input = sys.stdin.readline

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans

if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))

LR = []
ans = [0 for _ in range(Q)]
for i in range(Q):
  temp= list(map(int,input().split()))
  LR.append((temp,i)) 
LR.sort(key=lambda x : x[0][1]) 

CMAX = max(C)
Tree = BIT(N)
last = [-1 for _ in range(CMAX)] 
left,right = LR[0][0]
for j in range(right):
  mae = last[C[j]-1]
  last[C[j]-1] = j
  if mae !=-1:
    Tree.add(mae+1,-1) 
  Tree.add(last[C[j]-1]+1,1) 
  

D = []





temp = Tree.get(left,right)
ID = LR[0][1]
ans[ID] = temp
lastright = right  

for i in range(1,Q):
  left,right = LR[i][0]
  
  if lastright < right:
    for j in range(lastright,right):
      mae = last[C[j]-1]
      last[C[j]-1] = j
      
      if mae !=-1:
        
        Tree.add(mae+1,-1) 
      Tree.add(j+1,1) 
  temp = Tree.get(left,right)
  ID = LR[i][1]
  ans[ID] = temp
  lastright = right
  


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

Solution (Python):
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))

LR = []
ans = [0 for _ in range(Q)]
for i in range(Q):
  temp= list(map(int,input().split()))
  LR.append((temp,i)) 
LR.sort(key=lambda x : x[0][1]) 

CMAX = max(C)
Tree = BIT(N)
last = [-1 for _ in range(CMAX)] 
left,right = LR[0][0]
for j in range(right):
  mae = last[C[j]-1]
  last[C[j]-1] = j
  if mae !=-1:
    Tree.add(mae+1,-1) 
  Tree.add(last[C[j]-1]+1,1) 
  

D = []





temp = Tree.get(left,right)
ID = LR[0][1]
ans[ID] = temp
lastright = right  

for i in range(1,Q):
  left,right = LR[i][0]
  
  if lastright < right:
    for j in range(lastright,right):
      mae = last[C[j]-1]
      last[C[j]-1] = j
      
      if mae !=-1:
        
        Tree.add(mae+1,-1) 
      Tree.add(j+1,1) 
  temp = Tree.get(left,right)
  ID = LR[i][1]
  ans[ID] = temp
  lastright = max(right,lastright)
  


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

Solution (Python):
def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  

    N,Q = MI()
    c = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((i,l,r))

    from operator import itemgetter

    lr = sorted(lr,key=itemgetter(2))  
    a = 0
    d = {}  
    ANS = [0]*Q


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

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


    bit = BIT([0]*N)  
    for i in range(1,N+1):
        if not c[i] in d.keys():
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][2] == i:
            j,l,r = lr[a]
            ANS[j] = bit.query(r)-bit.query(l-1)
            a += 1

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


if __name__ == '__main__':
    main()