Buggy python submission (verdict: Runtime Error):
I = [int(_) for _ in open(0).read().split()]
N, Q=I[:2]
C = I[2:2 + N]
LR = I[2 + N:]
2 ** 40
2 ** 20
Query = []
for i, lr in enumerate(zip(LR[::2], LR[1::2])):
    l, r = lr
    Query += [r * 2 ** 40 + l * 2 ** 20 + i]
for i, c in enumerate(C):
    Query += [(i + 1) * 2 ** 40 + c]
Query.sort()
c_i = [-1] * (N + 1)

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
 

ans = [0] * N
st = SegmentTree([0] * (N + 5), lambda x,y:x+y, 0)
for q in Query:
    x, yz = divmod(q, 2 ** 40)
    y, z = divmod(yz, 2 ** 20)
    if y==0:
        if c_i[z] != -1:
            st.operate_right(c_i[z], -1)
        c_i[z] = x
        st.operate_right(x, 1)
    else:
        ans[z] = st.query(y, x + 1)
print(*ans, sep='\n')


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j, r):
        j += 1
        if arr[C[j]]:
            BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j, r):
        j += 1
        if arr[C[j]]:
            BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(Q)]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted([(lr[1], lr[0], i) for i, lr in enumerate(LR)])
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(Q)]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([0] * N, lambda x, y: x + y, 0)
arr = [0] * (5 * 10**5 + 1)
RLI = sorted([(lr[1], lr[0], i) for i, lr in enumerate(LR)])
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        st.operate_right(arr[C[j]], -1)
        arr[C[j]] = j + 1
        st.operate_right(j + 1, 1)
        j += 1
    ans[i] = st.query(l, r + 1)
print(*ans, sep='\n')


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Buggy python submission (verdict: Time Limit Exceeded):
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = I[2:2 + N]
L, R = I[2 + N::2], I[3 + N::2]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([set([c]) for c in C], lambda x, y: x | y, set())

for l, r in zip(L, R):
    print(len(st.query(l - 1, r)))


Fixed submission:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))