Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
from numba import jit
import numpy as np

@jit(nopython=True,cache=True)
def mainloop(c, q, l, r):
    for i in range(q):
        data = np.array(c[l[i]-1:r[i]])
        print(len(np.unique(data)))

n, q = map(int, input().split())
c = list(map(int, input().split()))
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

mainloop(c, q, l, r)

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
from numba import jit
import numpy as np

@jit(nopython=True)
def mainloop(c, q, l, r):
    for i in range(q):
        data = np.array(c[l[i]-1:r[i]])
        print(len(np.unique(data)))

n, q = map(int, input().split())
c = list(map(int, input().split()))
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

mainloop(c, q, l, r)

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
	n, q = map(int, sys.stdin.readline().split())
	c = list(map(int, sys.stdin.readline().split()))
	fenwick = [0] * n
	
	def add(i, v):
		while i < n:
			fenwick[i] += v
			i = (i | (i + 1))
	
	def get(r):
		res = 0
		while r >= 0:
			res += fenwick[r]
			r = (r & (r + 1)) - 1
		return res
	
	def get_seg(l, r):
		return get(r) - get(l - 1)
		
	by_r = [[] for i in range(n)]
	for t in range(q):
		l, r = map(int, sys.stdin.readline().split())
		l, r = l - 1, r - 1
		by_r[r].append((l, t))
	last_ent = [-1] * (n + 1)
	ans = [0] * q
	for r in range(n):
		p = last_ent[c[r]]
		if p != -1:
			add(p, -1)	
		last_ent[c[r]] = r
		add(r, 1)
		for quer in by_r[r]:
			l, num = quer
			ans[num] = get_seg(l, r)
	print('\n'.join([str(x) for x in ans]))
	
main()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
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()

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
from numba import jit

@jit(nopython=True)
def mainloop(c, q, l, r):
    for i in range(q):
        print(len(set(c[l[i]-1:r[i]])))

n, q = map(int, input().split())
c = list(map(int, input().split()))
l = [0]*q
r = [0]*q
for i in range(q):
    l[i], r[i] = map(int, input().split())

mainloop(c, q, l, r)