Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in ans:
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = (l-1, r, p)
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in reversed(range(last_update_idx, r)):
                if not color[j] in st:
                    if color[j] in dic:
                        seg.update(dic[color[j]], 0)
                    dic[color[j]] = j
                    seg.update(j, 1)
                    st.add(color[j])
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    segupd = seg.update
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    segupd(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                segupd(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
        self.dic = {}
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        if (p, q) in self.dic:
            return self.dic[(p, q)]
        else:
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res, self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res, self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res, self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
            self.dic[(p, q)] = res
            return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
        self.dic = {}
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        if (p, q) in self.dic:
            return dic[(p, q)]
        else:
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res, self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res, self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res, self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
            self.dic[(p, q)] = res
            return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if color[j] in dic and not color[j] in st:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j, col in enumerate(color[last_update_idx: r]):
                if not col in st and col in dic:
                    seg.update(dic[col], 0)
                dic[col] = j+last_update_idx
                st.add(col)
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in [None]*q:
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        qry[i] = [l-1, r, i]
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    segupd = seg.update
    segqry = seg.query
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    segupd(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                segupd(dic[v], 1)
            last_update_idx = r
        ans[i] = segqry(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        qry[i] = [l-1, r, i]
    qry.sort(key=lambda x: x[1])
    dic = {}
    idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if idx < r:
            st = set()
            while idx < r:
                if not color[idx] in st and color[idx] in dic:
                    seg.update(dic[color[idx]], 0)
                dic[color[idx]] = idx
                st.add(color[idx])
                idx += 1
            for v in st:
                seg.update(dic[v], 1)
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        qry[i] = [l-1, r, i]
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        qry[i] = [l-1, r, i]
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    q_list = range(q)
    qry = [[None]*3 for _ in q_list]
    ans = [None]*q
    for i in q_list:
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l-1, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    q_list = range(q)
    qry = [[None]*3 for _ in q_list]
    ans = [None]*q
    for i in q_list:
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l-1, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*3 for _ in range(q)]
    ans = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l-1, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    q_list = list(range(q))
    qry = [[None]*3 for _ in range(q)]
    ans = [None]*q
    for i in q_list:
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in q_list:
        l, r = qry[i][0], qry[i][1]
        l -= 1
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[qry[i][2]] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    q_list = list(range(q))
    qry = [[None]*3 for _ in range(q)]
    ans = [None]*q
    for i in q_list:
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in q_list:
        l, r = qry[i][0], qry[i][1]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        ans[qry[i][2]] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    q_list = list(range(q))
    qry = [[None]*4 for _ in range(q)]
    for i in q_list:
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in q_list:
        l, r = qry[i][0], qry[i][1]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in q_list:
        print(qry[i][3])

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][0], qry[i][1]
        l -= 1
        if last_update_idx < r:
            j = last_update_idx
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()


Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            j = last_update_idx
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            j = last_update_idx
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            j = last_update_idx
            while j < r:
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
                j += 1
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            j = last_update_idx
            while j < r:
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
                j += 1
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    seg.update(dic[color[j]], 0)
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [[None]*4 for _ in range(q)]
    for i in range(q):
        l, r = map(int, input().split())
        qry[i][0], qry[i][1], qry[i][2] = l, r, i
    qry.sort(key=lambda x: x[1])
    col_var = [0]*n
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, col_var)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    col_var[dic[color[j]]] = 0
                    seg.update(dic[color[j]], 0)
                col_var[j] = 1
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i][3] = seg.query(l, r)
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    for i in range(q):
        qry[i].append(i)
    qry.sort(key=lambda x: x[1])
    col_var = [0]*n
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, col_var)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    col_var[dic[color[j]]] = 0
                    seg.update(dic[color[j]], 0)
                col_var[j] = 1
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i].append(seg.query(l, r))
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    for i in range(q):
        qry[i].append(i)
    qry.sort(key=lambda x: x[1])
    col_var = [0]*n
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, col_var)
    for i in range(q):
        l, r = qry[i][:2]
        l -= 1
        if last_update_idx < r:
            for j in range(last_update_idx, r):
                if color[j] in dic:
                    col_var[dic[color[j]]] = 0
                    seg.update(dic[color[j]], 0)
                col_var[j] = 1
                seg.update(j, 1)
                dic[color[j]] = j
            last_update_idx = r
        qry[i].append(seg.query(l, r))
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    dics = [{} for _ in range(n)]
    dics[0][color[0]] = 0
    for i in range(1, n):
        dics[i].update(dics[i-1])
        dics[i][color[i]] = i
    for i in range(q):
        qry[i].append(i)
        qry[i].append(0)
    qry.sort(key=lambda x: x[0])
    for i in range(q):
        l, r = qry[i][0]-1, qry[i][1]-1
        rmset = set()
        for v in dics[r].keys():
            if dics[r][v] < l:
                rmset.add(v)
        for v in rmset:
            dics[r].pop(v)
        qry[i][3] = len(dics[r])
    qry.sort(key=lambda x: x[2])
    for i in range(q):
        print(qry[i][3])

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)

Buggy python submission (verdict: Time Limit Exceeded):
class SegTree():
    def segfunc(self, x, y):
        return x | y

    def __init__(self, n, init_val):
        self.num = 2**(n-1).bit_length()
        self.seg = [set() for _ in range(2 * self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def query(self, p, q):#p <= x < q
        if q<=p:
            return set()
        p += self.num-1
        q += self.num-2
        res = set()
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    tmp = [set() for _ in range(n)]
    for i in range(n):
        tmp[i].add(color[i])
    seg = SegTree(n, tmp)
    for l, r in qry:
        print(len(seg.query(l-1, r)))

if __name__ == "__main__":
    main()

Fixed submission:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

n, q = map(int, input().split())
color = list(map(int, input().split()))
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 0
seg = SegTree(0, n, [0]*n)
for l, r, i in qry:
    if last_update_idx < r:
        st = set()
        for j in range(last_update_idx, r):
            if not color[j] in st and color[j] in dic:
                seg.update(dic[color[j]], 0)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            seg.update(dic[v], 1)
        last_update_idx = r
    ans[i] = seg.query(l, r)
for v in ans:
    print(v)