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 operator import add
import sys
input = sys.stdin.buffer.readline

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

#クエリを終了位置rでソート。
ilrs = sorted(((i, l-1, r-1) for i, (l, r) in enumerate(lrs), key = lambda t: t[2]))

#重複を区間としてし、終了位置でソートされた状態で列挙。
duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i

#あとは平面走査と呼ばれる探査
ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

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

Submission status: Runtime Error

Solution code:
from operator import add
import sys
input = sys.stdin.buffer.readline

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

#クエリを終了位置rでソート。
ilrs = sorted((i, l-1, r-1) for i, (l, r) in enumerate(lrs), key = lambda t: t[2])

#重複を区間としてし、終了位置でソートされた状態で列挙。
duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i

#あとは平面走査と呼ばれる探査
ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


class SegmentTreeSUM(object):  # 1-indexed [l,r)
    def __init__(self, size):
        self.len = 1 << (size-1).bit_length()
        # print(self.len)
        self.array = [0 for _ in range(2 * self.len)]

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i] = self.array[i] + x
            i >>= 1
        # print(self.array)

    def get(self, i):  # 0-indexed
        return self.array[i + self.len]

    def get_sum(self, l, r):  # 0-indexed
        L = l+self.len
        R = r+self.len
        ANS = 0

        while L < R:
            if L & 1:
                ANS = ANS + self.array[L]
                L += 1

            if R & 1:
                R -= 1
                ANS = ANS + self.array[R]
            L >>= 1
            R >>= 1

        return ANS


N, Q = na()
c_array = na()

tree = SegmentTreeSUM(N)


q_array = []
for i in range(Q):
    l, r = na()
    q_array.append([i, l-1, r])

q_array = sorted(q_array, key=lambda x: x[2])
ans = [0] * Q
last_idx = [-1] * N
q_idx = 0
for i, c in enumerate(c_array):
    tree.update(i, 1)
    if last_idx[c] != -1:
        tree.update(last_idx[c], -1)
    last_idx[c] = i
    while(q_idx < Q and q_array[q_idx][2] == (i+1)):
        idx, l, r = q_array[q_idx]
        ans[idx] = tree.get_sum(l, r)
        q_idx += 1


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

Submission status: Runtime Error

Solution code:
#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
cdef int i,j,l,r,ll,rr
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# Mo's algorithm
# 言ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size)]
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))

# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
preb = -1
for i in range(n // bucket_size):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # print(nl, nr, l, r)
        # 区間を広げる時
        while nl > l:
            nl -= 1
            add_num(nl)
        while nr < r:
            add_num(nr)
            nr += 1
        # 区間を狭める時
        while nl < l:
            del_num(nl)
            nl += 1
        while nr > r:
            nr -= 1
            del_num(nr)
        # print("a", num, "idx", idx, "LR", (l, r))
        # print("c", count)
        ans[idx] = num


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

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*N

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

Submission status: Runtime Error

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

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

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        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):
        """
        [l, r)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(0-index)
        """
        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

#def function():
N, Q = map(int, input().split())
c = list(map(int, input().split()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i] = str(10**12*lrs[i][1] + 10**6* lrs[i][0] + i).zfill(18)

right_edge = [-1]*(N+1)
seg = SegTree([0]*(N+1), segfunc, ide_ele)

lrs = lrs.sort()
order_num = 0
answer = [0]*(Q)
for i, c_o in enumerate(c):
    if right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
    right_edge[c_o] = i
    seg.update(i, 1)
    
    for j in range(N):
        if order_num >= Q:
            break
        query_now = int(lrs[order_num][:6])
        left_edge = int(lrs[order_num][6:12])
        original_posi = int(lrs[order_num][12:])
        if query_now == i:
            answer[original_posi] = [order_num,seg.query(left_edge,query_now+1)]
            order_num += 1
        else:
            break

for i in range(len(answer)):
    print(answer[i][1])
        
#if __name__ == '__main__':
#    function()

Submission status: Runtime Error

Solution code:
# python3 implementation of above approach
import sys
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(10000)]

sys.setrecursionlimit(10 ** 8)


# 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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

Submission status: Runtime Error

Solution code:
# python3 implementation of above approach
import sys
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(1000000)]

sys.setrecursionlimit(10 ** 8)


# 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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

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


# 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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

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


# 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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

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


# 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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

Submission status: Runtime Error

Solution code:
import sys
from operator import add, itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(int, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    query = sorted([(left - 1, right, idx) for idx, (left, right) in enumerate(lr)], key=itemgetter(1))
    seg_tree = SegmentTree([0] * N, add, 0)
    c_to_idx = [-1] * N
    
    p_right = 0
    ans = [0] * Q
    for left, right, idx in query:
        for i in range(p_right, right):
            if c_to_idx[c[i]] != -1:
                seg_tree.update(c_to_idx[c[i]], 0)
            seg_tree.update(i, 1)
            c_to_idx[c[i]] = i
        p_right = right
        ans[idx] = seg_tree.query(left, right)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]

n = N

init(n)

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

# Query in range 0 to 4
for _ in range(Q):
    l, r = [int(x) for x in input().split()]
    getDistinct(l - 1, r - 1, n)

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 = [int(x) for x in input().split()]
C = [int(x) for x in input().split()]
LR = [[int(x) for x in input().split()] for _ in range(Q)]

n = N

init(n)

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

# Query in range 0 to 4
for l, r in LR:
    getDistinct(l - 1, r - 1, n)