Problem p02599 (python)

Fixed submission:
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-number-distinct-elements-subarray/
# 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])


# This code is contributed by
# sanjeev2552


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

    queries = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        queries[i] = Query(l - 1, r - 1, i)

    queries.sort(key=lambda x: x.r)
    answeringQueries(C, N, queries, Q)

    return


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
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(5 * 10 ** 5)]

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

Buggy submission (verdict: Runtime Error):
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()