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



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Runtime Error

Solution code:
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())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  assert time() - start < 0.2

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  assert time() - start < 0.5
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  assert time() - start < 1.0

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Runtime Error

Solution code:
#####segfunc######
def segfunc(x,y):
    return x + y

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

n, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))
Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
Qs.sort(key=lambda x:x[2])  

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

ans = [-1]*Q
dic = {}
b = 1
 
for i,l,r in Qs:
  if b < r + 1:
    st = set()
    for j in range(b,r+1):
      if not Cs[j] in st and Cs[j] in dic:
        update(dic[Cs[j]], 0)
      st.add(Cs[j])
      dic[Cs[j]] = j
    for s in st:
      update(dic[s], 1)
    b = r + 1
  ans[i] = query(l,r+1)
    
for a in ans:
  print(a)

Submission status: Runtime Error

Solution code:
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_most = {}
J = [[] for _ in range(max(ball)+1)]
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L_most:
    L_most[b]=i
    h.add(i+1,1)
    on.add(i+1)
  J[b].append(i)
    
for i in range(n+1):
  for j in range(len(J[i])):
    if j+1<len(J[i]):
      jump[J[i][j]+1] = J[i][j+1]+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 = {}
#print(on)

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

for q in LOO:
  print(ans[q])

Submission status: Runtime Error

Solution code:
# Python3 code to find number of  
# distinct numbers in a subarray 
MAX = 1000001
  
# structure to store queries 
class Query: 
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 
  
# updating the bit array 
def update(idx, val, bit, n): 
    while idx <= n: 
        bit[idx] += val 
        idx += idx & -idx 
  
# querying the bit array 
def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def answeringQueries(arr, n, queries, q): 
  
    # initialising bit array 
    bit = [0] * (n + 1) 
  
    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX
  
    # answer for each query 
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        # Setting last_visit[arr[i]] as i and  
        # updating the bit array accordingly 
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        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
  
    # print answer for each query 
    for i in range(q): 
        print(ans[i]) 
  
# Driver Code 
if __name__ == "__main__":
    n,q = map(int,input().split())
    a = list(map(int,input().split()))
    # n = len(a)
    queries =[]
    for i in range(q):
        l,r = map(int,input().split())
        l-=1
        r-=1
        queries.append(Query(i,r,l))
    # queries = [Query(0, 4, 0),
    #            Query(1, 3, 1),
    #            Query(2, 4, 2)]
    # q = len(queries)
  
    queries.sort(key = lambda x: x.r) 
    answeringQueries(a, n, queries, q) 
  
# This code is contributed by 
# sanjeev2552

Submission status: Runtime Error

Solution code:
"""
    Satwik_Tiwari ;) .
    30th AUGUST , 2020  - SUNDAY
"""

#===============================================================================================
#importing some useful libraries.
from __future__ import division, print_function

from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase

from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
#If the element is already present in the list,
# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect
#If the element is already present in the list,
# the right most position where element has to be inserted is returned

#==============================================================================================
#fast I/O region
BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

#===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType
def iterative(f, stack=[]):
  def wrapped_func(*args, **kwargs):
    if stack: return f(*args, **kwargs)
    to = f(*args, **kwargs)
    while True:
      if type(to) is GeneratorType:
        stack.append(to)
        to = next(to)
        continue
      stack.pop()
      if not stack: break
      to = stack[-1].send(to)
    return to
  return wrapped_func
#### END ITERATE RECURSION ####

#===============================================================================================
#some shortcuts

mod = 1000000007
def inp(): return sys.stdin.readline().rstrip("\r\n") #for fast input
def out(var): sys.stdout.write(str(var))  #for fast output, always take string
def lis(): return list(map(int, inp().split()))
def stringlis(): return list(map(str, inp().split()))
def sep(): return map(int, inp().split())
def strsep(): return map(str, inp().split())
# def graph(vertex): return [[] for i in range(0,vertex+1)]
def zerolist(n): return [0]*n
def nextline(): out("\n")  #as stdout.write always print sring.
def testcase(t):
    for pp in range(t):
        solve(pp)
def printlist(a) :
    for p in range(0,len(a)):
        out(str(a[p]) + ' ')
def google(p):
    print('Case #'+str(p)+': ',end='')
def lcm(a,b): return (a*b)//gcd(a,b)
def power(x, y, p) :
    res = 1     # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0) :
        return 0
    while (y > 0) :
        if ((y & 1) == 1) : # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1      # y = y/2
        x = (x * x) % p
    return res
def ncr(n,r): return factorial(n)//(factorial(r)*factorial(max(n-r,1)))
def isPrime(n) :
    if (n <= 1) : return False
    if (n <= 3) : return True
    if (n % 2 == 0 or n % 3 == 0) : return False
    i = 5
    while(i * i <= n) :
        if (n % i == 0 or n % (i + 2) == 0) :
            return False
        i = i + 6
    return True

#===============================================================================================
# code here ;))

def solve(case):
    n,q = sep()
    c = lis()
    bsize = floor(n**0.5)
    blocks = [ceil(n/bsize)]
    query = []
    for i in range(q):
        l,r = sep()
        l-=1
        r-=1
        query.append((l//bsize,r,l,i))

    query = sorted(query)
    ans = [0]*(q)
    currl = 0
    currr = 0
    prev = 1
    have = {c[0]:1}
    # print(query)
    for i in range(q):
        l = query[i][2]
        r = query[i][1]
        # print(l,r)
        # print(currl,currr,prev)
        while(currl>l):
            currl-=1
            if(c[currl] not in have):
                have[c[currl]] = 1
                prev+=1
            else:
                have[c[currl]] +=1
        while(currl<l):
            if(have[c[currl]] == 1):
                prev-=1
                del have[c[currl]]
            else:
                have[c[currl]]-=1
            currl+=1
        while(currr<r):
            currr+=1
            if(c[currr] not in have):
                have[c[currr]] = 1
                prev+=1
            else:
                have[c[currr]] +=1
        while(currr>r):
            if(have[c[currr]]==1):
                prev-=1
                del have[c[currr]]
            else:
                have[c[currr]]-=1
            currr-=1
        ans[query[i][3]]= prev

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



testcase(1)
# testcase(int(inp()))

Submission status: Runtime Error

Solution code:
N, Q = map(int, input().split())
colors = list(map(int, input().split()))

n = len(set(colors))
right = [[0] * n]

for idx, c in enumerate(colors):
    if idx != 0:
        right.append(right[idx-1].copy())
    right[idx][c-1] += 1

for _ in range(Q):
    l, r = map(int, input().split())

    if l==r:
        print(1)
    elif l==1:
        print(len(set(right[r-1])) - (0 in right[r-1]))
    else:
        e = 0
        for l, r in zip(right[l-2], right[r-1]):
            if r - l >= 1:
                e += r - l
        print(e)

Submission status: Runtime Error

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()
 
    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret
 
    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)
 
    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
 
    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_
 

n,q = inpl()
c = inpl()
queries = [inpl().append(_) for _ in range(q)]
res = [-1] * q
d = [-1] * n
sec = []
for i,x in enumerate(c):
    if d[x-1] != -1:
        sec.append([d[x-1], i+1])
    d[x-1] = i+1
sec_ln = len(sec)
sec.sort(reverse = True)
queries.sort(reverse = True)
# print(queries)
bit = BIT(n)
sec_ind = que_ind = 0
for i in range(1,n+1)[::-1]:
    while sec_ind < sec_ln and sec[sec_ind][0] >= i:
        x = sec[sec_ind][1]
        bit.bitadd(x-1,1)
        sec_ind += 1
    
    while que_ind < q and queries[que_ind][0] >= i:
        _,x,ind = queries[que_ind]
        res[ind] = x-_+1 - bit.bitsum(0,x)
        que_ind += 1
print(*res)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cl = list(map(int, input().split()))
flg = 0
for i in range(n):
    l,r = list(map(int, input().split()))
    for j in range(l -1, r):
      flg += 1
print(flg)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cl = list(map(int, input().split()))
for i in range(n):
    l,r = list(map(int, input().split()))
print(2)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cl = list(map(int, input().split()))
print(cl)
for i in range(n):
    flg = [1] * 500000
    #print(flg)
    l,r = list(map(int, input().split()))
    pt = 0
    for j in range(l -1, r):
        #print("j",j, "cl" , cl[j])
        pt += flg[cl[j]]
        flg[cl[j]] = 0
    #print(flg)
    print(pt)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cl = list(map(int, input().split()))
for i in range(n):
    flg = [1] * n
    l,r = list(map(int, input().split()))
    pt = 0
    for j in range(l -1, r):
        pt += flg[cl[j]]
        flg[cl[j]] = 0
    print(pt)

Submission status: Runtime Error

Solution code:
n, q = list(map(int, input().split()))
cl = list(map(int, input().split()))
for i in range(n):
    flg = [1] * n
    l,r = list(map(int, input().split()))
    pt = 0
    for j in range(l -1, r):
        #print(cl[j], flg[cl[j]])
        pt += flg[cl[j]]
        flg[cl[j]] = 0
    print(pt)

Submission status: Runtime Error

Solution code:
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]] + 2, -1)
    add(i + 2, 1)
    l[c[i]] = i
    for j in Q[i]:
        a[j[1]] = query(1 << 19) - query(j[0] + 1)
print(*a, sep="\n")

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time

def main():
    input=stdin.readline
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lri=[]
    # O(n)
    for i in range(q):
        l,r=map(int, input().split())
        l-=1
        r-=1
        lri.append((l,r,i))
    size=n+1
    seg=[0]*size
    def add(idx,val):
        idx+=1
        for _ in range(100):
            seg[idx]+=val
            idx+=idx&(-idx)
            if idx<size:break
    def sum(idx):
        idx+=1
        res=0
        for _ in range(100):
            res+=seg[idx]
            idx-=idx&(-idx)
            if idx>0:break
        return res
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]-1]!=-1:
            rr[bfr[c[i]-1]]=i
        bfr[c[i]-1]=i
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time

def main():
    input=stdin.readline
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lri=[]
    # O(n)
    for i in range(q):
        l,r=map(int, input().split())
        l-=1
        r-=1
        lri.append((l,r,i))
    size=n+1
    seg=[0]*size
    def add(idx,val):
        idx+=1
        for _ in range(20):
            seg[idx]+=val
            idx+=idx&(-idx)
            if idx<size:break
    def sum(idx):
        idx+=1
        res=0
        for _ in range(20):
            res+=seg[idx]
            idx-=idx&(-idx)
            if idx>0:break
        return res
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]-1]!=-1:
            rr[bfr[c[i]-1]]=i
        bfr[c[i]-1]=i
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys.stdin import readline
from time import time
input=readline


def main():
    class Bit:
        def __init__(self,size):
            self.size=size+1
            self.seg=[0]*self.size
        def add(self,idx,val):
            idx+=1
            while idx<self.size:
                self.seg[idx]+=val
                idx+=idx&(-idx)
        def sum(self,idx):
            idx+=1
            res=0
            while idx>0:
                res+=self.seg[idx]
                idx-=idx&(-idx)
            return res

    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        lri.append((l,r,i))
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    bit=Bit(n)
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            bit.add(rr.get(lt),1)
        # O(
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(bit.sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
main()

Submission status: Runtime Error

Solution code:
import numpy as np
from numba import jit
[N, Q] = list(map(int, input().split()))

c = list(map(int, input().split()))
Qs = [None] * Q

Cs = [0] * (max(c)+1)
for i in range(max(c)+1):
    Cs[ c[i] ] += 1

loc = np.zeros(max(c)+1, dtype=np.int32)
CCs = [np.zeros(Cs[i], dtype=np.int32) for i in range(max(c)+1)]
for i in range(len(c)):
    CCs[c[i]][ loc[c[i]] ] = i+1
    loc[c[i]] += 1

@jit(nopython=True)
def ntype(CCs, l, r):
    ret = 0
    for i in range(1, len(CCs)):
        if np.searchsorted(CCs[i], r, side='right') > np.searchsorted(CCs[i], l, side='left'):
            ret += 1
    return(ret)

for i in range(Q):
    [l, r] = list(map(int, input().split()))
    print(ntype(CCs, l, r))

Submission status: Runtime Error

Solution code:
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 = [list(map(int,input().split()))+[i] for i in range(Q)]
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N)

ANS = []
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS.append((bit.sum(r)-bit.sum(l-1),i))
ANS.sort(key=lambda x: x[1])
for a,i in ANS:
    print(a)

Submission status: Runtime Error

Solution code:
class Bit:
  __arr = []
  __N = 0
  def __init__(self, N):
    self.__N = N
    self.__arr = [0] * (1 + self.__N)
        
  def __str__(self):
    return str(self.__arr)
  
  def add_(self, i, var):
    if i == 0 :
      print("Bit.add_ parameter 1 must not be 0.")
      exit()
    while i <= 1 + self.__N:
      self.__arr[i] += var
      i += i & -i
      
  def sum_(self, i):
    res = 0
    while i > 0:
      res += self.__arr[i]
      i -= i & -i
    return res
  
  def sub_sum_(self, i, j):
    if i == j:
      return 1
    return self.sum_(j) - self.sum_(i)

def quicksort(A, x):
  temp = list(map(list, set(map(tuple, A))))
  if len(temp) < 2:
    return A
  center = A.pop(0)
  left = []
  right = []
  for i in A:
    if i[x] > center[x]:
      right.append(i)
    else:
      left.append(i)
  left = quicksort(left, x)
  right = quicksort(right, x)
  left.append(center)
  left.extend(right)
  return left

N, Q = map(int, input().split())
C = list(map(int, input().split()))
q=[]
lastAppeared = {}
ans = []
BIT = Bit(N)

for i in range(Q):
  q.append(list(map(int, input().split())))
  
for i, _ in enumerate(q):
  q[i].insert(0, i)
q = quicksort(q, 2)  

ans = [0] * Q

r = 0
for i in q:
  while r < i[2]:
    r = r + 1
    if C[r-1] in lastAppeared:
      BIT.add_(lastAppeared[C[r-1]], -1)
      lastAppeared[C[r-1]] = r
      BIT.add_(lastAppeared[C[r-1]], 1)    
    else:
      lastAppeared[C[r-1]] = r
      BIT.add_(lastAppeared[C[r-1]], 1)   
  if r == i[1]:
    ans[i[0]] = 1
  else:
    ans[i[0]] = BIT.sub_sum_(i[1]-1, r)
  
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
class Bit:
  __arr = []
  __N = 0
  def __init__(self, N):
    self.__N = N
    self.__arr = [0] * (1 + self.__N)
        
  def __str__(self):
    return str(self.__arr)
  
  def add_(self, i, var):
    if i == 0 :
      print("Bit.add_ parameter 1 must not be 0.")
      exit()
    while i <= 1 + self.__N:
      self.__arr[i] += var
      i += i & -i
      
  def sum_(self, i):
    res = 0
    while i > 0:
      res += self.__arr[i]
      i -= i & -i
    return res
  
  def sub_sum_(self, i, j):
    if i == j:
      return 1
    return self.sum_(j) - self.sum_(i)

def quicksort(A, x):
  temp = list(map(list, set(map(tuple, A))))
  if len(temp) < 2:
    return A
  center = A.pop(0)
  left = []
  right = []
  for i in A:
    if i[x] > center[x]:
      right.append(i)
    else:
      left.append(i)
  left = quicksort(left, x)
  right = quicksort(right, x)
  left.append(center)
  left.extend(right)
  return left

N, Q = map(int, input().split())
C = list(map(int, input().split()))
q=[]
lastAppeared = {}
ans = []
BIT = Bit(N)

for _ in range(Q):
  q.append(list(map(int, input().split())))
  
for i, _ in enumerate(q):
  q[i].insert(0, i)
q = quicksort(q, 2)  

ans = [0] * Q

r = 0
for i in q:
  while r < i[2]:
    r = r + 1
    if C[r-1] in lastAppeared:
      BIT.add_(lastAppeared[C[r-1]], -1)
      lastAppeared[C[r-1]] = r
      BIT.add_(lastAppeared[C[r-1]], 1)    
    else:
      lastAppeared[C[r-1]] = r
      BIT.add_(lastAppeared[C[r-1]], 1)   
  if r == i[1]:
    ans[i[0]] = 1
  else:
    ans[i[0]] = BIT.sub_sum_(i[1]-1, r)
  
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
/**In the name of Allah, the Most Merciful, the Most Merciful.**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define INF 9223372036854775806
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define PI 2*acos(0.0)
#define EPS 1e-9
ll max(ll a,ll b) {if(a>b) return a; else return b;}
ll min(ll a,ll b) {if(a<b) return a; else return b;}

struct ff{
    int l,r,idx;
    ff(int a,int b,int c){
        l=a; r=b; idx=c;
    }
};
vector<ff> v;
int K;
bool cmp(ff a,ff b){
    int b1=a.l/K; int b2=b.l/K;
    if(b1==b2) return a.r<b.r;
    return b1<b2;
}
int a[500005];

int dist=0;
int cnt[500005];
void add(int x){
    cnt[x]++;
    if(cnt[x]==1) dist++;
}
void del(int x){
    cnt[x]--;
    if(cnt[x]==0) dist--;
}

int main()
{
    int n,q,x,y;
    scanf("%d %d",&n,&q);
    K=sqrt(n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<=q;i++){
        scanf("%d %d",&x,&y);
        v.pb(ff(x,y,i));
    }

    sort(v.begin(),v.end(),cmp);

    int l=1,r=0;
    int ans[q+1]={0};
    for(auto it:v){
        while(r<it.r){
            r++;
            add(a[r]);
        }
        while(r>it.r){
            del(a[r]);
            r--;
        }
        while(l<it.l){
            del(a[l]);
            l++;
        }
        while(l>it.l){
            l--;
            add(a[l]);
        }
        ans[it.idx]=dist;
    }

    for(int i=1;i<=q;i++){
        printf("%d\n",ans[i]);
    }


    return 0;
}

Submission status: Runtime Error

Solution code:
import math

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
query = [tuple(list(map(int, input().split())) + [i]) for i in range(Q)]
query_result = [0 for i in range(Q)]

collar_pos = [-1] * N
bit = [0] * (N + 1)

def bit_add(index, num):
    while (index <= N):
        bit[index] += num
        index += index & -index
    return

def bit_sum(index):
    result = 0
    while (index > 0):
        result += bit[index]
        index -= index & -index
    return result

sorted_query = sorted(query, key=lambda query: query[1]) # sort by right

index = 1
for query in sorted_query:
    while (index <= query[1]):
        # update BIT
        if (collar_pos[c[index-1]] != -1):
            bit_add(collar_pos[c[index-1]], -1)
        bit_add(index, 1)
        # update collar_pos
        collar_pos[c[index-1]] = index
        index += 1
    query_result[query[2]] = bit_sum(query[1]) - bit_sum(query[0]-1)

for q in query_result:
    print(q)