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
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 = [-1]+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
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = 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 sys
input = sys.stdin.buffer.readline

n,Q = map(int,input().split())
c = [0] + list(map(int,input().split()))
dg = 10**6
dg2 = 10**12
res = [0]*Q
LRI = []
for i in range(Q):
    l,r = map(int,input().split())
    LRI.append(l*dg2 + r*dg + i)
LRI.sort()


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

fi = [[] for i in range(n+1)]
nxt = [-1]*(n+1)
for i in range(1,n+1):
    num = c[i]
    if len(fi[num]) == 0:
        BIT_update(i,1)
    else:
        nxt[fi[num][-1]] = i
    fi[num].append(i)

idx = 0

for i in range(1,n+1):

    while idx < Q:
        l,ri = divmod(LRI[idx],dg2)
        if l != i:
            break
        r,resi = divmod(ri,dg)
        res[resi] = BIT_query(r)
        idx += 1
    BIT_update(i,-1)
    if nxt[i] != -1:
        BIT_update(nxt[i],1)


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

Solution (Python):

from operator import add


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array):
        _len = len(array)
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [0] * self.__size + \
            array + [0] * (self.__size - _len)
        self.__ie = 0

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = self.__tree[i * 2] + self.__tree[i * 2 + 1]

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__tree[i * 2] + self.__tree[i * 2 + 1]

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = 0
        while l < r:
            if l & 1:
                ret += self.__tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.__tree[r]
            l //= 2
            r //= 2
        return ret

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


@mt
def slv(N, Q, C, LR):
    LR.sort(key=lambda x: x[2])
    ans = [-1] * Q

    st = SegmentTree([0]*(N+1))
    la = [-1] * (N+1)
    p = 0
    for i, l, r in LR:
        l -= 1
        r -= 1
        for j in range(p, r+1):
            c = C[j]
            if la[c] != -1:
                st.update(la[c], st[la[c]]-1)
            la[c] = j
            st.update(j, st[j]+1)
        p = r+1
        ans[i] = st.query(l, r+1)
    return ans


def main():
    N, Q = read_int_n()
    C = read_int_n()
    LR = [[_, *read_int_n()] for _ in range(Q)]
    print(*slv(N, Q, C, LR), sep='\n')


if __name__ == '__main__':
    main()

Solution (Python):
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 = [-1]+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
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = 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 sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = [int(x) - 1 for x in input().split()]

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



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

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

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

que.sort(key=lambda x: -x[1])
ans = [None] * q
last = [-1] * n
BIT = SegTree(n)

for i in range(1, n+1):
    if last[c[i-1]] != -1:
        BIT.add(last[c[i-1]], -1)
    last[c[i-1]] = i
    BIT.add(i, 1)

    while que and que[-1][1] == i:
        l, r, x = que.pop()
        ans[x] = BIT.sum(r) - BIT.sum(l-1)

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

Solution (Python):

from operator import add


import sys


buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = self.__tree[i * 2] + self.__tree[i * 2 + 1]

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__tree[i * 2] + self.__tree[i * 2 + 1]

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret += self.__tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret += self.__tree[r]
            l //= 2
            r //= 2
        return ret

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


@mt
def slv(N, Q, C, LR):
    LR.sort(key=lambda x: x[2])
    ans = [-1] * Q

    st = SegmentTree([0]*(N+1), add, 0)
    la = [-1] * (N+1)
    p = 0
    for i, l, r in LR:
        l -= 1
        r -= 1
        for j in range(p, r+1):
            c = C[j]
            if la[c] != -1:
                st.update(la[c], st[la[c]]-1)
            la[c] = j
            st.update(j, st[j]+1)
        p = r+1
        ans[i] = st.query(l, r+1)
    return ans

def main():
    N, Q = read_int_n()
    C = read_int_n()
    LR = [[_, *read_int_n()] for _ in range(Q)]
    print(*slv(N, Q, C, LR), sep='\n')

    
    
    
    
    
    
    
    
    
    



if __name__ == '__main__':
    main()

Solution (Python):
NN = 19
BIT = [0] * (2 ** NN + 1)
def addbit(i, x=1):
    while i <= 2**NN:
        BIT[i] += x
        i += i & (-i)
def getsum(i):
    ret = 0
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret

N, Q = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    X[r-1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addbit(1, N)
for r in range(N):
    c = C[r]
    addbit(last[c] + 2, -1)
    addbit(r + 2)
    last[c] = r
    for l, i in X[r]:
        ANS[i] = getsum(1 << NN) - getsum(l + 1)
print(*ANS, sep = "\n")

Solution (Python):

import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lri=[list(map(int,input().split()))+[i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  
  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)

  bt=BIT(n+1)
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      bt.add(dc[x],-1)
    bt.add(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=bt.get(l-1,r)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  
  
  main()

Solution (Python):
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 = [-1]+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((l,r,q))
queries.sort(key = lambda x:x[1])

curR = 0
for i in range(Q):
    l,r,q = queries[i]
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = 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 sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	
	def calc(self, a, b):
		return a + b

	
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = self.calc(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m


def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N

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

	LR.sort(key = lambda x:x[0])
	Seg = SegmentTree(N)
	right = 0
	for r, l, i in LR:
		while right <= r:
			itr = c[right] - 1
			if lastappeared[itr] == None:
				Seg.update(right, 1)
			else:
				Seg.update(lastappeared[itr], 0)
				Seg.update(right, 1)
			lastappeared[itr] = right
			right += 1

		if l == 0:
			anspre = Seg.query(0, r)
		else:
			anspre = Seg.query(l, r)
		ans[i] = anspre

	for i in range(Q):
		print(ans[i])



if __name__ == '__main__':
	main()

Solution (Python):

import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  
  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)

  bt=BIT(n+1)
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      bt.add(dc[x],-1)
    bt.add(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=bt.get(l-1,r)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  
  
  main()

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


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = []
OFFSET = 10 ** 6
for i in range(q):
    l, r = map(int, input().split())
    query.append(i + OFFSET * l + OFFSET * OFFSET * r)


bit = BIT(n)
memo = {}
ans = [0] * q
query.sort()
ind = 0

for tmp in query:
    i = tmp % OFFSET
    l = (tmp // OFFSET) % OFFSET
    r = tmp // (OFFSET * OFFSET)
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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

Solution (Python):

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


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

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    
    for ans in ANS:
        print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

by_R = [[] for _ in range(N+1)]
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	by_R[r+1].append((l, i))

s = [0] * N
def update(pos, dif):
	while pos < N:
		s[pos] += dif
		pos |= pos + 1

def query(pos):
	res = 0
	while pos > 0:
		res += s[pos-1]
		pos &= pos - 1
	return res

diff = 0
ans = [-1] * Q
last = [-1] * (N+1)

for i, v in enumerate(C):
	if last[v] != -1:
		update(last[v], -1)
	else:
		diff += 1

	update(i, 1)
	last[v] = i

	for l, j in by_R[i+1]:
		ans[j] = diff - query(l)

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

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l - 1, r - 1, i)
    return res


def solve():
    n, q = LI()
    c = LI()
    lr = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        lr[i] = (l - 1, r - 1, i)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1]<= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return



if __name__ == '__main__':
    solve()

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

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

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

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

    def lower_bound(self, x):
        if x <= 0:
            return 0
        k = 1
        while k * 2 <= self.size:
            k *= 2
        j = 0
        while k > 0:
            if j + k <= self.size and self.bit[j + k] < x:
                x -= self.bit[j + k]
                j += k
            k //= 2
        return j

N, Q = map(int, input().split())
c = [0] + list(map(int, input().split()))
queries = [list(map(int, input().split())) + [i] for i in range(Q)]
queries.sort(key=lambda q: q[1])
last = [-1] * (N+1)
ans = [0] * Q
bit = BIT(N + 1)
j = 0
for l, r, i in queries:
    while j < r:
        j += 1
        if last[c[j]] != -1:
            bit.add(last[c[j]], -1)
        bit.add(j, 1)
        last[c[j]] = j
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep='\n')

Solution (Python):
def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 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

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()

Solution (Python):

from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l-1, r-1, i)
    return res


def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1]<= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return



if __name__ == '__main__':
    solve()

Solution (Python):
import sys
input = sys.stdin.readline
class BIT:
    """
    Binary Index Tree
    

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): 
                k-=self.L[res+i]
                res+=i
            
            i//=2
        return res+1



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


pos=sorted(pos,key=lambda x:x[1])

last_appeared=[0]*(N+1)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r-1]]
        if last==0:
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r-1]]=cur_r 
        cur_r+=1

    assert l>=1
    ans[i]=B.sum(r)-B.sum(l-1)


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

Solution (Python):

import math
from queue import PriorityQueue
import bisect
import copy
import time
from collections import Counter


MAX = 1000001
  

class Query: 
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 
  

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

def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def answeringQueries(arr, n, queries, q): 
  
    
    bit = [0] * (n + 1) 
  
    
    
    
    last_visit = [-1] * MAX
  
    
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        
        
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        
        
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        
        
        while query_counter < q and queries[query_counter].r == i: 
            ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) -  query(queries[query_counter].l, bit, n) 
            query_counter += 1
  
    
    for i in range(q): 
        print(ans[i]) 

n,q=map(int,input().split())
l=[int(x) for x in input().split()]
que=[]
for i in range(q):
	a,b=map(int,input().split())
	que.append(Query(a-1,b-1,i))
que.sort(key = lambda x: x.r)
answeringQueries(l,n,que,q)

Solution (Python):
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j 
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: 
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: 
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0]*N)
li = [[] for i in range(N+1)]
for i in range(Q):
    l, r = map(int, input().split())
    li[r].append((i, l-1))

now = 0
for r in range(1, N+1):
    for i, l in li[r]:
        while now < r:
            c = C[now]
            pre_idx, last_appeared[c] = last_appeared[c], now
            if pre_idx >= 0:
                st.update(pre_idx, 0)
            st.update(now, 1)
            now += 1
        ans[i] = st.query(l, r)


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

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    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 lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    query = []
    for q in range(Q):
        query.append(list(map(int, input().split())))
        query[-1].append(q)
    query.sort(key=lambda x: x[1])

    last = [0] * (N+1)
    for i, c in enumerate(C):
        if i > query[0][1]-1:
            break
        last[c] = i+1

    bit = Bit(N)
    for i in range(1, N+1):
        if last[i]:
            bit.add(last[i], 1)
    r_prev = query[0][1]
    ans = [0] * Q
    for l, r, q in query:
        if r > r_prev:
            for i in range(r_prev+1, r+1):
                j = last[C[i-1]]
                if j:
                    bit.add(j, -1)
                last[C[i-1]] = i
                bit.add(i, 1)
            r_prev = r
        ans[q] = bit.sum(r) - bit.sum(l-1)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()