Problem p02599 (python)

Fixed submission:
import sys
input = sys.stdin.readline

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

    def add(x, a):
        while x <= N:
            bit[x] += a
            x += x & -x

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    lr = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        lr[i] = (i, l, r)
    lr.sort(key=lambda x: x[2])
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for i, l, r in lr:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+2)
ans = [None] * Q
last_idx = [-1] * N
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')

Buggy submission (verdict: Runtime Error):
from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

    def add(self, x, a):
        while x <= self.N:
            self.bit[x] += a
            x += x & -x

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * N
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')