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:
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 100001


# 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 = [int(k) for k in input().split()]
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        queries.append(Query(l-1, r-1, i))
    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

# This code is contributed by
# sanjeev2552

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*n
Ans=[0]*q

n_max=5*10**5+1
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

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

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    if l==1:
        Ans[i]=bitsum(BIT,r+1)
    else:
        Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

N,Q = LI()
_c = LI()
_lr = [LI() for _ in range(Q)]
#A,B = zip(*AB)
lr = np.array(_lr)
c = np.zeros(N + 1)
c[1:] = _c

# setしてlength
# c.insert(0, 0)

@njit
def calc():
    for pair in lr:
        print(len(set(c[pair[0]:pair[1]+1])))

calc()

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

# Reference: https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/
# python3 implementation of above approach
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

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


def main():
    N, Q = map(int, readline().split())
    C = list(map(int, readline().split()))
    (*LR,) = map(int, read().split())

    init(N)
    build(1, 0, N - 1, C)
    for l, r in zip(*[iter(LR)] * 2):
        l -= 1
        r -= 1
        getDistinct(l, r, N)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*n
Ans=[0]*q

n_max=5*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

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

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    if l==1:
        Ans[i]=bitsum(BIT,r+1)
    else:
        Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class Abel> struct BIT {
    vector<Abel> dat[2];
    Abel UNITY_SUM = 0;                     // to be set

    /* [1, n] */
    BIT(int n) { init(n); }
    void init(int n) { for (int iter = 0; iter < 2; ++iter) dat[iter].assign(n + 1, UNITY_SUM); }

    /* a, b are 1-indexed, [a, b) */
    inline void sub_add(int p, int a, Abel x) {
        for (int i = a; i < (int)dat[p].size(); i += i & -i)
            dat[p][i] = dat[p][i] + x;
    }
    inline void add(int a, int b, Abel x) {
        sub_add(0, a, x * -(a - 1)); sub_add(1, a, x); sub_add(0, b, x * (b - 1)); sub_add(1, b, x * (-1));
    }

    /* a is 1-indexed, [a, b) */
    inline Abel sub_sum(int p, int a) {
        Abel res = UNITY_SUM;
        for (int i = a; i > 0; i -= i & -i) res = res + dat[p][i];
        return res;
    }
    inline Abel sum(int a, int b) {
        return sub_sum(0, b - 1) + sub_sum(1, b - 1) * (b - 1) - sub_sum(0, a - 1) - sub_sum(1, a - 1) * (a - 1);
    }

    /* debug */
    void print() {
        for (int i = 1; i < (int)dat[0].size(); ++i) cout << sum(i, i + 1) << ",";
        cout << endl;
    }
};

int main() {
    int N; cin >> N;
    int Q; cin >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];    
    vector<int> lefts(Q), rights(Q), ids(Q);
    for (int i = 0; i < Q; ++i) {
        cin >> lefts[i] >> rights[i];
        --lefts[i];
        ids[i] = i;
    }
    sort(ids.begin(), ids.end(), [&](int i, int j) {
            return rights[i] < rights[j];});

    BIT<int> bit(N+5);
    vector<int> prev(1100000, -1);
    vector<int> res(Q, 0);
    int r = 0;
    for (auto i : ids) {
        for (; r < rights[i]; ++r) {
            bit.add(prev[a[r]]+2, r+2, 1);
            prev[a[r]] = r;
        }
        int tmp = bit.sum(lefts[i]+1, lefts[i]+2);
        res[i] = max(res[i], tmp);
    }
    for (int i = 0; i < Q; ++i) cout << res[i] << endl;
}

Submission status: Runtime Error

Solution code:
import numpy as np
n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
mat =  np.zeros((n+1, n))
tmp_array = np.array([0]*n)
for i, ci in enumerate(c):
    tmp_array[ci] += 1
    mat[i+1] = tmp_array
for _ in range(q):
    l, r = list(map(int, input().split()))
    print(sum((mat[r] - mat[l-1]) > 0))

Submission status: Runtime Error

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*n
Ans=[0]*q

n_max=5*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

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

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)

Submission status: Runtime Error

Solution code:
# python3 implementation of above approach
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

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


# Driver code
n,q=map(int,input().split())
arr = list(map(int,input().split()))

init(n)

# Bulid the segment tree
build(1, 0, n - 1, arr)

# Query in range 0 to 4
for i in range(q):
    l,r=map(int,input().split())
    getDistinct(l-1, r-1, n)

# This code is contributed by mohit kumar 29

Submission status: Runtime Error

Solution code:
import numpy as np 
N,Q = map(int,input().split())
dp = np.zeros((N+1,N))
c_list = list(map(int,input().split()))
c0 = c_list[0] - 1
dp[1,c0] = 1 
for i,c in enumerate(c_list):
    dp[i+1,:] = dp[i,:]
    dp[i+1,c-1] = dp[i+1,c-1] + 1

for i in range(Q):
    l,r = map(int,input().split())
    print(sum(dp[r,:]-dp[l-1,:] >0))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = list(map(int, input().split()))

# 回答
for i in range(n):
  l, r = map(int, input().split())
  print(len(set(balls[l-1:r])))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n, q = map(int, input().split())
C = [int(c) for c in input().split()]
zero = np.zeros((max(C)+1, n), dtype = int)
i = 0
for c in C:
    zero[c][i] = 1
    i +=1

for i in range(q):
    l, r = map(int, input().split())
    zerosum = np.sum(zero[:,l-1:r], axis=1)
    print(len(zerosum[np.nonzero(zerosum)]))

Submission status: Runtime Error

Solution code:
n, q = tuple(map(int, input().split()))
c = list(map(int, input().split()))

for _ in range(n):
    l, r = tuple(map(int, input().split()))
    print(len(set(c[l-1:r])))

Submission status: Runtime Error

Solution code:
def main():
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    cnt = 0
    while cnt < Q:
        ans = 0
        mem = [0]*N
        l, r = list(map(int, input().split()))
        for val in c[(l-1):r]:
            if mem[val] == 0:
                mem[val] = 1
                ans += 1
        print(ans)
        cnt += 1

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = map(int, input().split())

# 回答
for i in range(n):
  l, r = map(int, input().split())
  print(len(set(balls[l-1:r])))

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            
    def union(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            return self.tree[a]
        else:
            self.tree[a] = self.union(a*2) | self.union(a*2+1)
            return self.tree[a]
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        while y - x > 1:
            if x % 2 == 1:
                tl = tl | self.tree[x]
                x += 1
            if y % 2 == 0:
                tr = self.tree[y] | tr
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            print(len(tl|tr|self.tree[x]))
        else:
            print(len(tl|tr|self.tree[x]|self.tree[y]))
            
N,Q,*f = map(int, open(0).read().split())
c = f[:N]
lr = [f[N+i*2:N+i*2+2] for i in range(Q)]
st = SegmentTree(c)
st.union(1)
for l,r in lr:
    st.query(l-1,r-1)

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
for i in range (q):
    A = [0 for i in range (n)]
    cnt = 0
    l,r = map(int,input().split())
    for i in range (l,r+1):
        num = c[i-1]
        if A[num] == 0:
            A[num] = 1
            cnt += 1
    print (cnt)

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())
list_number = []
a = list(input().split())
for _ in range(q):
  l, r = map(int, input().split())
  for h in range(l, r):
    list_number.append(a[i])
  print(len(set(list_number)))
  list_number = []

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = map(int, input().split())

# 回答
for i in range(n):
  l, r = map(int, input().split())
  print(len(balls[l-1:r]))

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
for i in range (q):
    A = [0 for i in range (n)]
    cnt = 0
    l,r = map(int,input().split())
    for i in range (r-l+1):
        num = c[l+i]
        if A[num] = 0:
            cnt += 1
    print (cnt)

Submission status: Runtime Error

Solution code:
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

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

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

import sys
input = sys.stdin.buffer.readline

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

query = []

for i in range(Q):
    l, r, = map(int, input().split())
    query.append((l - 1, r, i))

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

lt, rt = 0, 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = BinaryIndexedTree(N)

for l, r, idx in query:
    while rt < r:
        if L[C[rt]] is not None:
            bit.add(L[C[rt]] + 1, -1)
        L[C[rt]] = rt
        bit.add(rt + 1, 1)
        rt += 1
    res[idx] = bit.sum(r) - bit.sum(l)

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

Submission status: Runtime Error

Solution code:

from math import ceil,log,floor 

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

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(str(ans))) 



n,q=map(int,input().split())
arr=[int(x) for x in input().split()]
build(1, 0, n - 1, arr) 
init(n)
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  getDistinct(l,r,n)

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
c =list(map(int,input().split()))

for i in range(n):
    l,r = map(int,input().split())
    print(len(set(c[l-1:r])))

Submission status: Runtime Error

Solution code:

from math import ceil,log,floor 

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) 

  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 (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=map(int,input().split())
arr=[int(x) for x in input().split()]
print(arr)
build(1, 0, n - 1, arr) 
init(n)
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  getDistinct(l,r,n)

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split())
l=list(map(int,input().split()))
for _ in range(n):
    l1,r1=map(int,input().split())
    print(len(set(l[l1-1:r1])))

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((len(C)+1,5*10**5), dtype=np.int64)
for i in range(len(C)):
  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:
# -*- coding: utf-8 -*-
import numpy as np

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

X = np.zeros((N+1,5*10**5), dtype=np.int64)
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:
# Fast IO (only use in integer input)

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

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

colors = {}
colorCount = []
cnt = 0
for elem in c:
    if elem not in colors:
        colors[elem] = 1
        cnt += 1
    colorCount.append(cnt)

for _ in range(Q):
    l,r = map(int,input().split())
    if l == 1:
        lColor = 0
    else:
        lColor = colorCount[l - 2]
    print(colorCount[r - 1] - lColor)

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=np.int64)
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:
def main():
    # 一点更新・一点取得の加法BIT
    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)
            self.allsum = 0

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x = i+1
                self.allsum += j
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)

        # 位置iに値vを足す
        def add(self, i, v):
            x, n, bit = i+1, self.n, self.bit
            self.allsum += v
            while x < n+1:
                bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k, n, bit = 0, self.maxbit, self.n, self.bit
            while k:
                if x+k <= n and bit[x+k] < w:
                    w -= bit[x+k]
                    x += k
                k //= 2
            return x

    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    lastappend = [-1]*n
    lr = [list(map(int, input().split())) for _ in [0]*q]
    ilr = [(i, l-1, r-1) for i, (l, r) in enumerate(lr)]
    ilr.sort(key=lambda x: (x[2], x[1], x[0]))
    bit = BIT(n)
    ans = [-1]*q
    r_now = -1
    for i, l, r in ilr:
        if r > r_now:
            for j in range(r_now+1, r+1):
                last = lastappend[c[j]]
                if last != -1:
                    bit.add(last, -1)
                lastappend[c[j]] = j
                bit.add(j, 1)
            r_now = r
        ans[i] = bit.sum_range(l, r+1)
    for i in ans:
        print(i)


main()

Submission status: Runtime Error

Solution code:
import os
import sys
from io import BytesIO, IOBase
# region fastio
 
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")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
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((10**6))] 
  
# 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()))
init(N)
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)