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):
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):  
        assert i > 0
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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])

lr.sort(key=lambda x: x[1])

rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]]+1, -1)
    rightest[c[i]] = i
    bit.add(i+1, 1)

    while current_q < Q and lr[current_q][1] == i:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1] + 1) - bit.sum(lr[current_q][0])
        current_q += 1

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

Solution (Python):
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

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

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)

Solution (Python):
from time import time
start = time()



class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    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 query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  
  X = []
  for i in range(Q):
    l,r = q[i]
    
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()

Solution (Python):
from sys import stdin
input = stdin.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
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
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 = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)

Solution (Python):
from sys import stdin
input = stdin.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

n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
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 = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)

Solution (Python):
import sys
input = sys.stdin.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
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")

Solution (Python):
from typing import Union
import sys
from operator import itemgetter

Num = Union[int, float]


class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.bit = [0] * (self.size + 1)
    
    def add(self, k: int, x: Num) -> None:
        """
        (0-index で) k 番目の要素に x をたす。
        >>> b = FenwickTree(5)
        >>> b.add(0, 10)
        >>> b.bit
        [0, 10, 10, 0, 10, 0]
        """
        if not 0 <= k < self.size:
            raise IndexError(f"FenwickTree.add(): size is {self.size}. accessed [{k}]")
        k += 1    
        while k <= self.size:
            self.bit[k] += x
            LSB = k & (-k)
            k += LSB
    
    def _accum_sum(self, k: int) -> Num:
        """ (1-index, 内部関数) bit の 1 ~ k 番目の要素の和を求める。"""
        s = 0
        while k > 0:
            s += self.bit[k]
            LSB = k & (-k)
            k -= LSB
        return s
    
    def sum(self, l: int, r: int) -> Num:
        """
        (0-index で) [l, r) 区間の和を求める。
        >>> b = FenwickTree(5)
        >>> b.add(1, 10)
        >>> b.add(2, 20)
        >>> b.sum(1, 3)
        30
        """
        if not 0 <= l <= r <= self.size:
            raise IndexError(f"FenwickTree.sum(): size is {self.size}. got slice is [{l}:{r}]")
        
        return self._accum_sum(r) - self._accum_sum(l)



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

def mi(): return map(int, input().split())

def mi_0(): return map(lambda x: int(x)-1, input().split())


def solve(n, q, interval, query):
    """
    [s, t] なる点を含むリスト interval
    [l, r(, query-number)] (0-index) なるクエリを q 個含むリスト query。l <= s and t <= r なる点の個数は何個か？
    """
    query_to_ans = [-1] * q
    query.sort(key=itemgetter(0))
    interval.sort(key=itemgetter(0))
    ft = FenwickTree(5 * 10 ** 5 + 5)
    
    for l, r, query_num in reversed(query):
        
        while interval and l <= interval[-1][0]:
            _, t = interval.pop()
            ft.add(t, 1)
        query_to_ans[query_num] = (r - l + 1) - ft.sum(0, r+1)
    
    for ans in query_to_ans:
        print(ans)



def main():
    n, q = mi()
    L = tuple(mi())
    prev = dict()
    intervals = []
    for i in range(n):
        if L[i] not in prev:
            prev[L[i]] = i
        else:
            intervals.append((prev[L[i]], i))
            prev[L[i]] = i
    query = []
    for i in range(q):
        l, r = mi_0()
        query.append((l, r, i))
    solve(n, q, intervals, query)
    


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

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

Solution (Python):
import sys

input = sys.stdin.buffer.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

Solution (Python):
import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

Solution (Python):
def segfunc(x,y):
  return x+y
ide_ele=0
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree([0]*n,segfunc,ide_ele)
lr=[[]for _ in range(n+1)]
for i in range(q):
  l,r=map(int,input().split())
  lr[r]+=[(l,i)]
d={}
for i in range(n):
  if not d.get(c[i]):d[c[i]]=[i]
  else:d[c[i]]+=[i]
for i in d:
  st.update(d[i][-1],1)
ans=[0]*q
r=n
while r>0:
  if lr[r]:
    l,i=lr[r].pop()
    ans[i]=st.query(l-1,r)
  while not lr[r] and r>0:
    if d[c[r-1]]:st.update(d[c[r-1]].pop(),0)
    if d[c[r-1]]:st.update(d[c[r-1]][-1],1)
    r-=1
for i in ans:print(i)

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

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()

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

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()

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

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()

Solution (Python):
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Solution (Python):
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Solution (Python):


class FenwickTree:

    def __init__(self, size):
        self.size = size
        self.array = [0]*size

    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)

    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer

    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def read_int():
    return int(input().strip())


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

def read_query():
    l, r = read_ints()
    return l-1, r-1

def solve():
    N, Q = read_ints()
    C = [c-1 for c in read_ints()]
    colour_to_index = [-1]*N
    queries = [read_query() for _ in range(Q)]
    answer = [-1]*Q
    queries_sorted_index = sorted(list(range(Q)), key=lambda i: queries[i][1])
    fenwick_tree = FenwickTree(N+1)
    last_r = -1
    for i in queries_sorted_index:
        l, r = queries[i]
        for j in range(last_r+1, r+1):
            colour = C[j]
            if colour_to_index[colour] != -1:
                fenwick_tree.add(colour_to_index[colour]+1, -1)
            colour_to_index[colour] = j
            fenwick_tree.add(colour_to_index[colour]+1, 1)
        answer[i] = fenwick_tree.rangesum(l+1, r+1)
        last_r = r
    print(*answer, sep='\n')


if __name__ == '__main__':
    solve()

Solution (Python):


class FenwickTree:

    def __init__(self, size):
        self.size = size
        self.array = [0]*size

    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)

    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer

    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))

def read_query():
    l, r = read_ints()
    return l-1, r-1

def solve():
    N, Q = read_ints()
    C = [c-1 for c in read_ints()]
    colour_to_index = [-1]*N
    queries = [read_query() for _ in range(Q)]
    answer = [-1]*Q
    queries_sorted_index = sorted(list(range(Q)), key=lambda i: queries[i][1])
    fenwick_tree = FenwickTree(N+1)
    last_r = -1
    for i in queries_sorted_index:
        l, r = queries[i]
        for j in range(last_r+1, r+1):
            colour = C[j]
            if colour_to_index[colour] != -1:
                fenwick_tree.add(colour_to_index[colour]+1, -1)
            colour_to_index[colour] = j
            fenwick_tree.add(colour_to_index[colour]+1, 1)
        answer[i] = fenwick_tree.rangesum(l+1, r+1)
        last_r = r
    for a in answer:
        print(a)


if __name__ == '__main__':
    solve()

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

from collections import defaultdict

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

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

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

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        
        
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

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

    def _sum(self, i):
        
        
        return self.bit1._sum(i)*i + self.bit2._sum(i)

def main():

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

    

    bit = RangeAddBIT(n)
    preidx = defaultdict(lambda: -1)
    ans = [-1]*q
    for r in range(n):
        p = preidx[C[r]]
        bit.add(p+1, r+1, 1)
        preidx[C[r]] = r
        for l, i in LI[r]:
            ans[i] = bit.sum(l, l+1)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

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

from collections import defaultdict

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

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

    def sum(self, i, j):
        
        
        return self._sum(j) - self._sum(i)

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

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

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        
        
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

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

    def _sum(self, i):
        
        
        return self.bit1._sum(i)*i + self.bit2._sum(i)

def main():

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

    

    bit = RangeAddBIT(n)
    preidx = defaultdict(lambda: -1)
    ans = [-1]*q
    for r in range(n):
        p = preidx[C[r]]
        bit.add(p+1, r+1, 1)
        preidx[C[r]] = r
        for l, i in LI[r]:
            ans[i] = bit.sum(l, l+1)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Solution (Python):
BIT = [0] * ((1 << 19) + 1)
def add(i, x):
    while i <= (1 << 19):
        BIT[i] += x
        i += i & -i
def query(i):
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    return res
n, q = map(int, input().split())
c = list(map(int, input().split()))
Q = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    Q[r - 1].append([l - 1, i])
l = [-1] * n
a = [-1] * q
add(1, n)
for i in range(n):
    add(l[c[i] - 1] + 2, -1)
    add(i + 2, 1)
    l[c[i] - 1] = i
    for j in Q[i]:
        a[j[1]] = query(1 << 19) - query(j[0] + 1)
print(*a, sep="\n")

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [0]*(n+1)

        def add(self,i,x):
            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

    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))
    bit = BIT(N)
    
    color = [0]*(N+1)

    ANS = [0]*Q
    LR.sort(key=lambda x: x[1])
    cur = 1
    for l,r,j in LR:
        for i in range(cur,r+1):
            c = C[i-1]
            if color[c] != 0:
                bit.add(color[c],-1)
            color[c] = i
            bit.add(i,1)
        cur = r+1
        ANS[j] = bit.sum(r)-bit.sum(l-1)
    for a in ANS:
        print(a)
main()

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def subtract(self, i, x):
        self.add(i, -x)
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.sum(j) - self.sum(i)
    
    def lower_bound(self, x):
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) >= x:
                r = index
            else:
                l = index
                
        if self.sum(l) >= x:
            return l
        return r
    
    def upper_bound(self, x):
        if x <= 0:
            return  0
        l, r = 0, self.n
        while r-l > 1:
            index = (r+l)//2
            if self.sum(index) <= x:
                l = index
            else:
                r = index
                
        if self.sum(r) <= x:
            return r
        return l

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    query = sorted([list(map(int, input().split())) + [i] for i in range(q)], key=itemgetter(1))
    
    bit = BIT(n)
    index = 0
    already = [0]*(n+1)
    ans = [0]*q
    index = 0
    for l, r, i in query:
        while index < r:
            bit.add(index+1, 1)
            if already[c[index]]:
                bit.subtract(already[c[index]], 1)
            already[c[index]] = index+1
            index += 1
            
        ans[i] = bit.get_sum(l-1, r)

    for a in ans:
        print(a)
        
    
    
    
    
if __name__ == "__main__":
    main()

Solution (Python):

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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i + 1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

(n, q), c, *d = [[*map(int, o.split())] for o in open(0)]

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

B = Bit(n)
ans = [-1] * q
last = [-1] * (n + 1)
ind = 0  
for i, (l, r) in d:
    for j in range(ind, r):
        if last[c[j]] != -1:
            B.add(last[c[j]], -1)
        B.add(j, 1)
        last[c[j]] = j
    ind = r
    ans[i] = B.sum(r) - B.sum(l - 1)
for a in ans:
    print(a)