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:
N,Q=map(int, input().split())
c=list(map(int, input().split()))
X=[list(map(int,list(input().split()))) for i in range(Q)]

for i in range(Q):
    a = c[(X[i][0]-1):(X[i][1])]
    b = list(set(a))
    print(len(b))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, Q = map(int,input().split())

L = [np.array([0] * N) for _ in range(N + 1)]

C = list(map(int,input().split()))

for i in range(N):
    L[i+1] += L[i]
    L[i+1][C[i] - 1] += 1

for _ in range(Q):
    l, r = map(int,input().split())
    tmp = L[r] - L[l-1]
    print(np.count_nonzero(tmp))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


from bisect import bisect_left, bisect_right, insort_left

from functools import reduce


class SqrtDecomposedList:
    def __init__(self, ls, segfunc, identity_element):
        from math import sqrt, ceil
        from copy import copy
        self.f = segfunc  # queryのfunction
        self.ide = identity_element
        self.n = len(ls)
        self.ls = copy(ls)
        self.b = ceil(sqrt(self.n))
        self.bucket = [self.ide] * (self.b + 1)
        self._build()

    def _build(self):
        for d in range(self.b):
            self.bucket[d] = reduce(
                self.f, self.ls[(d * self.b):((d + 1) * self.b)], self.ide)

    def __getitem__(self, idx):
        return self.ls[idx]

    def update(self, i, x):
        '''i番目の要素をxに更新する O(√n)'''
        self.ls[i] = x
        s = i // self.b * self.b
        t = s + self.b
        # print(i, self.b, i // self.b, s, t)
        self.bucket[i // self.b] = reduce(self.f,
                                          self.ls[s:t], self.ide)

    def query(self, l, r):
        '''半開区間[l,r)で指定すること O(√n)'''
        if r - l < 2 * self.b:
            return reduce(self.f, self.ls[l:r])
        l_bucket = (l - 1) // self.b + 1
        r_bucket = r // self.b  # 半開区間なのでこれでいい
        ret = reduce(self.f, self.bucket[l_bucket:r_bucket], self.ide)
        ret = self.f(
            reduce(self.f, self.ls[l:(l_bucket * self.b)], self.ide),
            ret)
        ret = self.f(
            reduce(self.f, self.ls[(r_bucket * self.b):r], self.ide),
            ret)
        return ret


def segfunc(x, y):  # セット
    return x | y


N, Q = ints()
C = []
for c in ints():
    C.append({c})

ls = SqrtDecomposedList(C, segfunc, set())
# セグ木か？面倒なので平方分割で
ans = []
for _ in range(Q):
    l, r = ints()
    ans.append(len(ls.query(l - 1, r)))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import collections

n,q=map(int,input().split())
c=list(map(int,input().split()))

for i in range(q):
    l,r=map(int,input().split())
    print(len(collections.Counter(c[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10**7)
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def LI2(): return list(map(int,sys.stdin.readline().rstrip()))  #空白なし
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())  #空白あり
def LS2(): return list(sys.stdin.readline().rstrip())  #空白なし


N,Q = MI()
c = LI()
n = len(set(c))
A = list(set(c))
d = {}
for i in range(n):
    d[A[i]] = i
for i in range(N):
    c[i] = {d[c[i]]}


def seg_func(x,y):
    return x|y


unit = set([])


class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
    def __init__(self,N,seg_func,unit):
        self.N = N
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)
    def build(self,init_value):  # 初期値を[N,2N)に格納
        for i in range(self.N):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def set_val(self,i,x):  # i番目(0-index)の値をxに変更
        i += self.N
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def fold(self,L,R):  # [L,R)の区間取得
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)


seg = SegTree(N,seg_func,unit)
seg.build(c)

for i in range(Q):
    l,r = MI()
    print(len(seg.fold(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
mex = 1000001

class Query:
	def __init__(self, l, r, idx):
		self.l = l
		self.r = r
		self.idx = idx


def update(idx, val, bit, n):
	while idx <= n:
		bit[idx] += val
		idx += idx & -idx


def query(idx, bit, n):
	summ = 0
	while idx:
		summ += bit[idx]
		idx -= idx & -idx
	return summ


def ansQuery(arr, n, queries, q):
	bits = [0] * (n + 1)
	l_v = [-1] * mex
	ans = [0] * q
	q_cnt = 0
	for i in range(n):
		if l_v[arr[i]] != -1:
			update(l_v[arr[i]] + 1, -1, bits, n)

		l_v[arr[i]] = i
		update(i + 1, 1, bits, n)

		while q_cnt < q and queries[q_cnt].r == i:
		    ans[queries[q_cnt].idx] = query(queries[q_cnt].r + 1, bits, n) - query(queries[q_cnt].l, bits, n)
		    q_cnt += 1

	for i in range(q):
		print(ans[i])


n,q = list(map(int,input().split()))
arr = list(map(int,input().split()))
queries = []
for i in range(q):
    l,r = list(map(int,input().split()))
    l,r = l-1,r-1
    queries.append(Query(l,r,i))
    q = len(queries)
queries.sort(key=lambda x: x.r)
ansQuery(arr, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))

lr = []
for i in range(q):
    lr.append(list(map(int, input().split())))

for i in lr:
    print(len(set(c[i[0] - 1 : i[1]])))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
final = []
for _ in range(q):
    l, r = map(int, input().split())
    count = 0
    s = set()
    for i in range(l, r+1):
        if c[i-1] not in s:
            s.add(c[i-1])
            count += 1
    final.append(count)
print('\n'.join(map(str, final)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().rstrip().split())
c = list(map(int,input().rstrip().split()))
for _ in range(Q):
    l, r = map(int,input().rstrip().split())
    ans = 0
    ll = []
    for i in range(l-1,r):
        if not(c[i] in ll):
            ans += 1
            ll.append(c[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split()) 
A = [int(x) for x in input().split()]
for i in range(Q):
  a,b = map(int, input().split()) 
  print(len(set(A[(a-1):b])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
data = [int(i) for i in input().split()]
ren = []
for i in range(Q):
    a, b = map(int, input().split())
    ren.append([a, b])

result = []
for j in range(Q):
    count = 0
    seen = []
    n = ren[j][0] - 1
    while n < ren[j][1]:
        if (data[n] in seen):
            n += 1
            continue
        else:
            count += 1
            seen.append(data[n])
            n += 1
    result.append(count)

for s in result:
    print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class Segtree():
    def __init__(self, aa):
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [0] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = self.tree[u * 2 + 1]|self.tree[u * 2 + 2]

    def get(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.get(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.get(l, r, seg_i * 2 + 2, segM, segR)
        return ret0|ret1

n,q=MI()
cc=MI()
aa=[1<<c for c in cc]
st=Segtree(aa)
for _ in range(q):
    l,r=MI()
    print(bin(st.get(l-1,r)).count("1"))

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n >> 1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c >> 2) & 0x3333333333333333)
    c = (c & 0x0F0F0F0F0F0F0F0F) + ((c >> 4) & 0x0F0F0F0F0F0F0F0F)
    c = (c & 0x00FF00FF00FF00FF) + ((c >> 8) & 0x00FF00FF00FF00FF)
    c = (c & 0x0000FFFF0000FFFF) + ((c >> 16) & 0x0000FFFF0000FFFF)
    c = (c & 0x00000000FFFFFFFF) + ((c >> 32) & 0x00000000FFFFFFFF)
    return c


num = 2 ** ((n - 1).bit_length())
SEG = [0] * (2 * num)


def func(a, b):
    return a | b


for idx, val in enumerate(C):
    idx += num
    SEG[idx] = 1 << (val - 1)
    while idx > 0:
        idx //= 2
        SEG[idx] = func(SEG[2 * idx], SEG[2 * idx + 1])


def query(left, right):
    resleft = 0
    resright = 0
    left += num
    right += num
    while right - left > 0:
        if left % 2 == 1:
            resleft = func(resleft, SEG[left])
            left += 1
        if right % 2 == 1:
            right -= 1
            resright = func(resright, SEG[right])
        left //= 2
        right //= 2
    return func(resleft, resright)


for _ in range(q):
    l, r = map(int, input().split())
    temp = query(l - 1, r)
    print(popcnt(temp))

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase
# region fastio
 
BUFSIZE = 8192
class FastIO(IOBase):
    newlines = 0
 
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
 
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
 
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
 
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
from math import ceil,log,floor 
  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 
MAX = 500001
r =ceil(log(MAX,2))
S  = pow(2,r+2)-1
segment=[[] for i in range(S)]
  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr): 
  
    # If start is equal to end then 
    # append the array element 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
  
    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
  
    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i]) 
  
    segment[i].append(segment[2 * i + 1]) 
  
# Query in an range a to b 
def query(node, l, r, a, b): 
    left, right, result=[],[],[] 
  
    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r): 
        return result 
  
    # If the range lies in this segment 
    if (a <= l and r <= b): 
        return segment[node] 
  
    # Else query for the right and left 
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
  
    # Return the result 
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d) 
  
# Initialize the segment tree 
def init(n): 
      
    # Get the height of the segment tree 
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n): 
      
    # Query for the range set 
    ans = query(1, 0, n - 1, l, r) 
  
    print(answer(str(ans))) 


N,Q=list(map(int,input().split()))
c=list(map(int,input().split()))
build(1,0,N-1,c)
for i in range(Q):
    l,r=list(map(int,input().split()))
    getDistinct(l-1,r-1,N)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [set()] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = [set([i]) for i in a]
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s

def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    S = SegTree(C, lambda x, y: x | y)

    for _ in range(Q):
        l, r = map(int, input().split())
        print(len(S.query(l - 1, r)))

main()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())

query = list(map(int, input().split()))

for _ in range(q):
  l, r = map(int, input().split())
  new_query = query[l - 1:r]
  set_query = list(set(new_query))
  print(len(set_query))

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, a):
        self.padding = 0
        self.n = len(a)
        self.N = 2 ** (self.n-1).bit_length()
        self.seg_data = [self.padding]*(self.N-1) + a + [self.padding]*(self.N-self.n)
        for i in range(2*self.N-2, 0, -2):
            self.seg_data[(i-1)//2] = self.seg_data[i] + self.seg_data[i-1]
    
    def __len__(self):
        return self.n
    
    def update(self, i, x):
        idx = self.N - 1 + i
        self.seg_data[idx] = x
        while idx:
            idx = (idx-1) // 2
            self.seg_data[idx] = self.seg_data[2*idx+1] + self.seg_data[2*idx+2]
    
    def query(self, i, j):
        # [i, j)
        if i == j:
            return self.seg_data[self.N - 1 + i]
        else:
            idx1 = self.N - 1 + i
            idx2 = self.N - 2 + j # 閉区間にする
            result = self.padding
            while idx1 < idx2 + 1:
                if idx1&1 == 0: # idx1が偶数
                    result = result + self.seg_data[idx1]
                if idx2&1 == 1: # idx2が奇数
                    result = result + self.seg_data[idx2]
                    idx2 -= 1
                idx1 //= 2
                idx2 = (idx2 - 1)//2
            return result
    
    @property
    def data(self):
        return self.seg_data[self.N-1:self.N-1+self.n]


N, Q = map(int, input().split())
C = list(map(int, input().split()))
ans = [0] * Q
last_appeared = [-1] * (N + 1)
st = SegmentTree([0]*N)

lr = [[i] + list(map(int, input().split())) for i in range(Q)]
lr.sort(key=lambda x:x[2])

now = 0
for i, l, r in lr:
    l -= 1
    while now < r:
        c = C[now]
        pre_idx, last_appeared[c] = last_appeared[c], now
        if pre_idx >= 0:
            st.update(pre_idx, 0)
        st.update(now, 1)
        now += 1
    ans[i] = st.query(l, r)


print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import math
import time
from collections import defaultdict, deque
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left, bisect_right
class seg_tree:
    def merge(self,a,b):
        return a.union(b)

    def __init__(self,n):
        size=1
        while(size<n):
            size*=2
        self.size=size
        self.segments=[0]*(2*size)

    def build_Until(self,a,x,lx,rx):
        if(rx-lx==1):
            self.segments[x]=set([a[lx]])
        else:
            mid=(lx+rx)//2
            self.build_Until(a,2*x +1,lx,mid)
            self.build_Until(a,2*x +2,mid,rx)
            self.segments[x]=self.merge(self.segments[2*x +1],self.segments[2*x +2])

    def build(self,a,n):
        self.build_Until(a,0,0,n)

    def sum_Until(self,x,lx,rx,l,r):
        # print(lx,rx)
        if(rx<=l or lx>=r):
            return set()
        elif(lx>=l and rx<=r):
            return self.segments[x]
        else:
            mid=(lx+rx)//2
            return self.merge(self.sum_Until(2*x +1,lx,mid,l,r),self.sum_Until(2*x +2,mid,rx,l,r))
    def sum(self,l,r):
        return self.sum_Until(0,0,n,l,r)
    
    def find_Until(self,x,lx,rx,val):
        # print(lx,rx,)
        if(rx-lx==1):
            return lx
        else:
            mid=(lx+rx)//2
            if(self.segments[x+x+2]>val):
                return self.find_Until(2*x+2,mid,rx,val)
            else:
                return self.find_Until(2*x+1,lx,mid,val-self.segments[x+x+2])


    def find(self,val):
        return self.find_Until(0,0,n,val)
n,q=map(int,stdin.readline().split())
a=list(map(int,stdin.readline().split()))
s=seg_tree(n)
s.build(a,n)
for _ in range(q):
    l,r=map(int,stdin.readline().split())
    print(len(s.sum(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map( int, input().split() )
c = list( map( int, input().split()))

for i in range(Q):
  l, r = map( int, input().split() )
  print( len( set( c[ l - 1: r ] )))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class SegmentTree:
    def __init__(self, S):
        N = len(S)
        d = N.bit_length()
        T = [set() for _ in range(2 ** (d + 1) - 1)]
        for i, s in enumerate(S):
            T[i + 2 ** d - 1].add(s)
        for i in range(2 ** d - 2, -1, -1):
            T[i] = T[2 * i + 1].union(T[2 * i + 2])
        self.d = d
        self.T = T

    def update(self, i, a):
            i = i + 2 ** self.d - 1
            while i > 0:
                i = (i - 1) // 2
                self.T[i] = self.T[2 * i + 1].union(self.T[2 * i + 2])
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, 2 ** self.d)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()

        if a <= l and r <= b:
            return self.T[k]
        else:
            s1 = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            s2 = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return s1.union(s2)


def main():
    N, Q = read_values()
    C = read_list()

    ST = SegmentTree(C)
    for _ in range(Q):
        a, b = read_index()
        print(len(ST.query(a, b + 1)))




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[1]:


N, Q = map(int,input().split())
c = list( map(int,input().split()) )
RNG_list = []
for i in range(Q):
    RNG_list.append( list( map(int,input().split()) ) )


# In[2]:


def color_val_ith(c,l,r):
    check = c[l-1:r]
    return len( list(set(check)) )


# In[5]:


color_val_list = [  color_val_ith(c,lr[0],lr[1]) for lr in RNG_list ]
for i in range(Q):  print( color_val_list[i] )

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
balls = input().split()
for _ in range(Q):
    l, r = map(int, input().split())
    print(len(set(balls[l - 1:r])))

Submission status: Time Limit Exceeded

Solution code:

import collections
from functools import lru_cache


# NOTE:
# This segment is of 1-based indexing, so provided array should be 1-indexed
class SegmentTree:
    def __init__(self, arr):
        self.N = len(arr)
        self.arr = arr
        segTreeSize = 2*self.N

        self.segTree = [set() for _ in range(segTreeSize)]

        for i in range(self.N):
            self.segTree[self.N + i] = set([self.arr[i]])

        self.buildTree()

    def buildTree(self):
        for i in range(self.N-1, 0, -1):
            self.segTree[i] = self.segTree[i << 1].union(
                self.segTree[(i << 1) | 1])

    # Range query [l, r)
    def query(self, l, r):
        ans = set()
        l += self.N
        r += self.N

        while l < r:
            if l & 1:
                ans = ans.union(self.segTree[l])
                l += 1

            if r & 1:
                r -= 1
                ans = ans.union(self.segTree[r])

            l >>= 1
            r >>= 1

        return len(ans)


def read():
    return input().strip()


def readInt():
    return int(input().strip())


def readList():
    return list(map(int, input().strip().split()))


def solve():
    [N, Q] = readList()
    arr = readList()
    queries = []

    segTree = SegmentTree([0] + arr)
    ans = []

    for _ in range(Q):
        l, r = readList()
        ans.append(segTree.query(l, r+1))

    return "\n".join(map(str, ans))


print(solve())

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
final = []
for _ in range(q):
    l, r = map(int, input().split())
    count = 0
    s = set()
    for i in range(l, r+1):
        if c[i-1] not in s:
            s.add(c[i-1])
            count += 1
    final.append(count)
for z in final:
    print(z)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun Aug  2 18:11:15 2020

@author: Paras
"""

n,queries = map(int, input().split())
c = list(map(int, input().split()))

for q in range(queries):
    l,r = map(int, input().split())
    l-=1
    print(len(set(c[l:r])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
if __name__ == "__main__":
    NQ=input().split(" ")
    N,Q=int(NQ[0]),int(NQ[1]);
    colors=input().split(" ")
    colors=np.array([int(i) for i in colors])
    for i in range(Q):
        lr=input().split(" ")
        l,r=int(lr[0]),int(lr[1])
        print(len(np.unique(colors[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n, q = input().split()
c = list(map(int, input().split()))

for i in range(int(q)):
    count = 0
    lst = []
    l, r = input().split()
    for j in c[int(l) - 1:int(r)]:
        if j not in lst:
            count += 1
            lst.append(j)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():

    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            add(i+1,1)
            p[ci] = i+1
            i += 1
        ans[ind] = sum_(r)-sum_(l-1)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()