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:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
# from math import sqrt
sys.setrecursionlimit(600000)
from math import ceil, log, floor
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# Code is referenced from https://geeksforgeeks.org


segment = [[] for i in range(1000)]


def build(i, s, e, arr):
    if s == e:
        segment[i].append(arr[s])
        return
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left
    # node of the segment tree
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


def query(node, l, r, a, b):
    left, right, result = [], [], []
    if b < l or a > r:
        return result
    if a <= l and r <= b:
        return segment[node]
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


def init(n):
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


def getDistinct(l, r, n):
    ans = query(1, 0, n - 1, l, r)
    print(answer(str(ans)))


n, q = sp()
arr = L()
init(n)
build(1, 0, n - 1, arr)
for _ in range(q):
    l, r = sp()
    getDistinct(l-1, r-1, n)

Submission status: Runtime Error

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
# from math import sqrt
from math import ceil, log, floor
sys.setrecursionlimit(600000)
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# Code is referenced from https://geeksforgeeks.org


segment = [[] for i in range(1000)]


def build(i, s, e, arr):
    if s == e:
        segment[i].append(arr[s])
        return
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left
    # node of the segment tree
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


def query(node, l, r, a, b):
    left, right, result = [], [], []
    if b < l or a > r:
        return result
    if a <= l and r <= b:
        return segment[node]
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


def init(n):
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


def getDistinct(l, r, n):
    ans = query(1, 0, n - 1, l, r)
    print(answer(str(ans)))


n, q = sp()
arr = L()
init(n)
build(1, 0, n - 1, arr)
for _ in range(q):
    l, r = sp()
    getDistinct(l-1, r-1, n)

Submission status: Runtime Error

Solution code:

# [temp1.py] => [29-07-2020 @ 10:25:10] 
# Author & Template by : Udit "luctivud" Gupta
# https://www.linkedin.com/in/udit-gupta-1b7863135/


import math;   from collections import *
import sys;    from functools import reduce
import time;   from itertools import groupby

# sys.setrecursionlimit(10**6)

def input()         : return sys.stdin.readline()
def get_ints()      : return map(int, input().strip().split())
def get_list()      : return list(get_ints())
def get_string()    : return list(input().strip().split())
def printxsp(*args) : return print(*args, end="")
def printsp(*args)  : return print(*args, end=" ")


DIRECTIONS = [(+0, +1), (+0, -1), (+1, +0), (+1, -1)] 
NEIGHBOURS = [(-1, -1), (-1, +0), (-1, +1), (+0, -1),\
              (+1, +1), (+1, +0), (+1, -1), (+0, +1)]


CAPS_ALPHABETS = {chr(i+ord('A')) : i for i in range(26)}
SMOL_ALPHABETS = {chr(i+ord('a')) : i for i in range(26)}
INF = float('inf')


# Custom input output is now piped through terminal commands.
# for _test_ in range(int(input())): 

maxn = int(5e5)
  
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 solve(arr, n, queries, q): 
    bit = [0] * (n + 1) 
    prev = [-1] * maxn  
    ans = [0] * q 
    count = 0
    for i in range(n): 
        if prev[arr[i]] != -1: 
            update(prev[arr[i]] + 1, -1, bit, n) 
        prev[arr[i]] = i 
        update(i + 1, 1, bit, n) 
        while count < q and queries[count][2] == i: 
            ans[queries[count][0]] = query(queries[count][2] + 1, bit, n) - query(queries[count][1], bit, n) 
            count += 1
    for i in range(q): 
        print(ans[i]) 

# main
n, q = get_ints()
a = get_list()
queries = []
for i in range(q):
	l, r = get_ints()
	queries.append((i, l-1, r-1))
queries = sorted(queries, key = lambda x: x[2]) 
solve(a, n, queries, q) 

# print("Time Elapsed: {}".format(float(S34p-S34t)))

# Binary Indexed Tree code taken from https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/

Submission status: Runtime Error

Solution code:
from math import ceil,log,floor 
  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment=[[] for i in range(5*(10**5)+1)] 
  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr): 
  
    # If start is equal to end then 
    # append the array element 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
  
    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
  
    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i]) 
  
    segment[i].append(segment[2 * i + 1]) 
  
# Query in an range a to b 
def query(node, l, r, a, b): 
    left, right, result=[],[],[] 
  
    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r): 
        return result 
  
    # If the range lies in this segment 
    if (a <= l and r <= b): 
        return segment[node] 
  
    # Else query for the right and left 
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
  
    # Return the result 
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d) 
  
# Initialize the segment tree 
def init(n): 
      
    # Get the height of the segment tree 
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n): 
      
    # Query for the range set 
    ans = query(1, 0, n - 1, l, r) 
  
    print(answer(str(ans))) 


N,Q=list(map(int,input().split()))
c=list(map(int,input().split()))
build(1,0,N-1,c)
for i in range(Q):
    l,r=list(map(int,input().split()))
    getDistinct(l-1,r-1,N)

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

Bsize = 700

@njit((i8[:, :], ), cache=True)
def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=list(map(int,input().split()))
lr=[]
for i in range(Q):
    l,r=map(int1,input().split())
    lr.append((l,r,i))
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s
    
b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
for i in range(N):
    if lastap[a[i]]!=-1:
        b.add(lastap[a[i]],lastap[a[i]]+1,-1)
    b.add(i,i+1,1)
    lastap[a[i]]=i
    while lr and lr[-1][1]==i:
        l,r,j=lr.pop()
        ans[j]=b.sum(l,r+1)
for x in ans:
    print(x)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n,q = map(int,input().split())
c = list(map(int,input().split()))
xa = np.zeros(n)
x = np.zeros((n+1,n),dtype=np.uint32)
for i in range(1,n+1):
  xa[c[i-1]-1] += 1
  x[i] = xa
for _ in range(q):
  l,r = map(int,input().split())
  print(np.count_nonzero(x[l-1] < x[r]))

Submission status: Runtime Error

Solution code:
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):
        # [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: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    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
st = SegmentTree([0]*N)

lr = [[i] + list(map(int, input().split())) for i in range(Q)]
lr.sort(key=lambda x:x[2])

now = 0
for i, l, r in lr:
    l -= 1
    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')

Submission status: Runtime Error

Solution code:
"""
                            pppppppppppppppppppp
                         ppppp  ppppppppppppppppppp
                      ppppppp    ppppppppppppppppppppp
                      pppppppp  pppppppppppppppppppppp
                      pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
       ppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppp
      pppppppppppppppppppppppppppppppppppppppppppppppp  ppppppppppppppppppppp
     ppppppppppppppppppppppppppppppppppppppppppppppppp  pppppppppppppppppppppp
    ppppppppppppppppppppppppppppppppppppppppppppppp    pppppppppppppppppppppppp
   pppppppppppppppppppppppppppppppppppppppppppppp     pppppppppppppppppppppppppp
  ppppppppppppppppppppppppppppppppppppppppppppp      pppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppppppp               pppppppppppppppppppppppppppppppp
  pppppppppppppppppppppppppppp     pppppppppppppppppppppppppppppppppppppppppppppp
  ppppppppppppppppppppppppppp    pppppppppppppppppppppppppppppppppppppppppppppppp
    pppppppppppppppppppppppp  pppppppppppppppppppppppppppppppppppppppppppppppppp
     ppppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppppp
      pppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppppp
       ppppppppppppppppppppp  ppppppppppppppppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppppp
                              pppppppppppppppppppppppppppppppp
                              pppppppppppppppppppppp  pppppppp
                              ppppppppppppppppppppp    ppppppp
                                 ppppppppppppppppppp  ppppp
                                    pppppppppppppppppppp
"""


import sys
from functools import lru_cache, cmp_to_key
from collections import defaultdict as dd, deque, Counter as C
from bisect import bisect_left as bl, bisect_right as br, bisect
from heapq import heapify, heappop, heappush
# from math import sqrt
from math import ceil, log, floor
mod = pow(10, 9) + 7
mod2 = 998244353
def data(): return sys.stdin.readline().strip()
def out(var, end="\n"): sys.stdout.write(str(var)+end)
def outa(*var, end="\n"): sys.stdout.write(' '.join(map(str, var)) + end)
def L(): return list(sp())
def sl(): return list(ssp())
def sp(): return map(int, data().split())
def ssp(): return map(str, data().split())
def l1d(n, val=0): return [val for i in range(n)]
def l2d(n, m, val=0): return [l1d(n, val) for j in range(m)]

# Code is referenced from https://geeksforgeeks.org


segment = [[] for i in range(1000)]


def build(i, s, e, arr):
    if s == e:
        segment[i].append(arr[s])
        return
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left
    # node of the segment tree
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


def query(node, l, r, a, b):
    left, right, result = [], [], []
    if b < l or a > r:
        return result
    if a <= l and r <= b:
        return segment[node]
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


def init(n):
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


def getDistinct(l, r, n):
    ans = query(1, 0, n - 1, l, r)
    print(answer(str(ans)))


n, q = sp()
arr = L()
init(n)
build(1, 0, n - 1, arr)
for _ in range(q):
    l, r = sp()
    getDistinct(l-1, r-1, n)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

X = np.zeros((N+1,N), dtype=int)
for i in range(N):
  c = C[i]-1
  X[i+1] = X[i]
  X[i+1,c] += 1

for _ in range(Q):
  l,r = map(int, input().split())
  print(np.sum(X[r]>X[l-1]))

Submission status: Runtime Error

Solution code:
import sys
def Ii():return int(sys.stdin.readline())
def Mi():return map(int,sys.stdin.readline().split())
def Li():return list(map(int,sys.stdin.readline().split()))
n,q = Mi()
c = Li()
for i in range(n):
  l,r = Mi()
  print(len(set(c[l-1:r])))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

X = np.zeros((N+1,N), dtype=int)
for i in range(N):
  c = C[i]
  X[i+1] = X[i]
  X[i+1,c] += 1

for _ in range(Q):
  l,r = map(int, input().split())
  print(np.sum(X[r]>X[l-1]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from math import ceil,log,floor 
  
segment=[[] for i in range(10**6)] 
  
def build(i, s, e, arr): 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
    segment[i].append(segment[2 * i]) 
    segment[i].append(segment[2 * i + 1]) 

def query(node, l, r, a, b): 
    left, right, result=[],[],[] 
    if (b < l or a > r): 
        return result 
  
    if (a <= l and r <= b): 
        return segment[node] 
  
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
  
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d) 
  
def init(n): 
      
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
  
def getDistinct(l, r, n): 
    ans = query(1, 0, n - 1, l, r) 
    print(answer(ans)) 
  
import sys;input=sys.stdin.readline
N, M = map(int, input().split())
arr = list(map(int, input().split()))
n = N
  
init(n) 
  
build(1, 0, n - 1, arr) 
  
for _ in range(M):
    l, r = map(int, input().split())
    getDistinct(l-1, r-1, n)

Submission status: Runtime Error

Solution code:
from math import ceil,log,floor 
  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 
segment=[[] for i in range(1000)] 
  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr): 
  
    # If start is equal to end then 
    # append the array element 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
  
    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i]) 
  
    segment[i].append(segment[2 * i + 1]) 
  
# Query in an range a to b 
def query(node, l, r, a, b): 
    left, right, result=[],[],[] 
  
    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r): 
        return result 
  
    # If the range lies in this segment 
    if (a <= l and r <= b): 
        return segment[node] 
  
    # Else query for the right and left 
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
  
    # Return the result 
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d) 
  
# Initialize the segment tree 
def init(n): 
      
    # Get the height of the segment tree 
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n): 
      
    # Query for the range set 
    ans = query(1, 0, n - 1, l, r) 
  
    print(answer(str(ans))) 
  
# Driver code 
import sys;input=sys.stdin.readline
N, M = map(int, input().split())
arr = list(map(int, input().split()))
n = N
  
init(n) 
  
# Bulid the segment tree 
build(1, 0, n - 1, arr) 
  
# Query in range 0 to 4 
for _ in range(M):
    l, r = map(int, input().split())
    getDistinct(l-1, r-1, n)