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:
from math import log2,ceil

num_factor,num_query = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split())) for _ in range(num_query)]

length = 2*2**ceil(log2(num_factor)) - 1
tree = [set([])]*length
Ans = []

def update(index,value):#0-indexed
    index += length // 2
    tree[index] = value
    while index > 0:
        index = (index - 1) // 2
        tree[index] = tree[index*2 + 1] | tree[index*2 + 2]
    return

def query(left: int, right: int , node : int, node_left :int, node_right :int)->int:#[left, right]
    if node_right < left or right < node_left:
        return set([])
    elif left <= node_left and node_right <= right:
        return tree[node]
    tmp1 = query(left , right , node*2 + 1, node_left, (node_right + node_left) // 2)
    tmp2 = query(left , right , node*2 + 2, (node_right + node_left) // 2 + 1, node_right )
    return tmp1 | tmp2


# def main():
#     for _ in range(num_query):
#         com,x,y = map(int,input().split())
#         if com:
#             Ans.append(query(x,y,0,0,length // 2))
#         else:
#             update(x,y)
#     print(*Ans, sep ="\n")
#     return



def main():
    for i in range(num_factor):
        c = C[i]
        update(i,{c})
    Ans = []
    for l,r in LR:
        Ans.append(len(query(l - 1 ,r - 1,0,0,length // 2)))
    print(*Ans ,sep="\n")
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, raw_input().split())
cis = map(int, raw_input().split())
for iq in range(q):
	lo,hi = map(int, raw_input().split())
	lo-=1
	hi-=1
	print len(set([cis[j] for j in range(lo, hi+1)]))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    for i in range(q):
        l, r = lr[i]
        lr[i] = [l, r, i]
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        x = defaultdict(lambda:None)
        while t < q and lr[t][1] <= i:
            l, r, j = lr[t]
            if x[r] is None:
                x[r] = sum(r)
            if x[l - 1] is None:
                x[l - 1] = sum(l-1)
            tmp = x[r] - x[l - 1]
            ans[j] = tmp
            t += 1
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
import math 

def buildSparseTable(arr, n):
    j = 0
    v = 1 << j
    while v <= n:
        cur = set()
        for i in range(v-1):
            cur.add(arr[i])
        for i in range(v-1, n):
            cur.add(arr[i])
            lookup[i-(v-1)][j] = cur.copy()
            if arr[i-(v-1)] in cur :
                cur.remove(arr[i-(v-1)])
    
        j += 1
        v =  1 << j
    
def query(L, R):
    to_union = list()
    while L <= R :
        j = int(math.log2(R - L + 1))
        if L > R :
            print('something wrong')
        to_union.append(lookup[L][j])
        L += (1<<j)
    x = set()
    for i in range(len(to_union))[::-1] :
        x = x.union(to_union[i])
    return len(x) 

N, Q = map(int,input().split(" "))
arr = list(map(int, input().split(" ")))

v = int(math.log2(N+1))+1
lookup = [[None]*(v) for _ in range(N)]
buildSparseTable(arr, N)

# print('done')
for _ in range(Q) :
    l, r = map(int, input().split(" "))
    print(query(l-1, r-1))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
lists = [list(map(int, input().split())) for i in range(Q+1)]
master = lists.pop(0)

X = [master[l[0]-1:l[1]] for l in lists]

for x in X:
  print(len(set(x)))

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

N,Q = LI()
_c = LI()
_lr = [LI() for _ in range(Q)]
#A,B = zip(*AB)
lr = np.array(_lr)
c = np.zeros(N + 1)
c[1:] = _c
a = np.zeros(Q)

# setしてlength
# c.insert(0, 0)

# @njit(nopython=True)
a = []
def calc():
    for pair in lr:
        a.append(len(collections.Counter(c[pair[0]:pair[1]+1])))
        # a.append(len(set(c[pair[0]:pair[1]+1])))
    print(*a, sep="\n")

calc()

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
input = sys.stdin.readline

class Segment_tree():
    def __init__(self, n, arrange):
        self.inf = pow(2, 32)
        self.n = n
        self.arrange = arrange
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [set()]*(self.N) + self.arrange + [set()]*(self.size-self.N-self.n)
        #この次の処理は、求められる動作に応じて変化させる。ここでは区間最小値問題のコードを書く。
        for i in range(self.N-1, -1, -1):
            self.segment[i] = self.segment[2*i+1]|self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l|find_r
    
    def count(self, l, r):
        return self.find(l, r, 0, 0, self.size-self.N)



def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    key = [None]*n
    
    judge = dict()
    for i in range(n-1, -1, -1):
        if c[i] in judge:
            key[i] = {judge[c[i]]}
        else:
            key[i] = set()
        judge[c[i]] = i
    """
    key2 = [None]*n
    
    judge2 = dict()
    for i in range(n):
        if c[i] in judge2:
            key2[i] = {judge2[c[i]]}
        else:
            key2[i] = set()
        judge2[c[i]] = i
     """   
    segment = Segment_tree(n, key)
    for i in range(q):
        l, r = map(int, input().split())
        judgement = sorted(list(segment.count(l-1, r-1)))
        print(r-l+1-bisect.bisect_left(judgement, r))
    
    
    
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

c = tuple(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
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, target, no_effect=set()):
        target_size = len(target)
        leaves_size = 1
        while leaves_size < target_size:
            leaves_size *= 2
        self.tree_size = leaves_size * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.no_effect = no_effect
        self.initialize_tree(target, no_effect)

    @classmethod
    def initialize_func(cls, value):
        return {value}

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree(self, target: list, no_effect=0):
        initial_leaf = self.tree_size // 2
        leaves = range(initial_leaf, initial_leaf+len(target))
        for value, leaf in zip(target, leaves):
            self.tree[leaf] = self.initialize_func(value)

        for parent in range(initial_leaf-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_value, index):
        leaf = self.tree_size//2 + index
        new_data = self.initialize_func(new_value)
        if self.tree[leaf] == new_data:
            return
        self.tree[leaf] = new_data

        parent = (leaf-1) // 2
        while parent >= 0:
            new_data = self.merge_child_data(parent)
            if self.tree[parent] == new_data:
                break
            self.tree[parent] = new_data
            parent = (parent-1) // 2

    def resolve_query(self, from_, to):
        result = self.no_effect
        left, right = from_ + self.tree_size // 2, to + self.tree_size // 2
        while left <= right:
            result = result | self.tree[left] | self.tree[right]
            left //= 2
            right = right//2 - 1

        return len(result)


def main():
    n, q = map(int, input().split())
    C = list(map(int, input().split()))

    seg_tree = SegmentTree(C)
    lrs = [list(map(int, input().split())) for _ in range(q)]
    for l, r in lrs:
        res = seg_tree.resolve_query(l-1, r-1)
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = map(int,input().split())
c = np.array([int(i) for i in input().split()])
for i in range(Q):
  l,r = map(int,input().split())
  print(len(np.unique(c[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
import sys
#import string
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def solve():
    #n = int(stdin.readline().rstrip())
    n,q= map(int, stdin.readline().rstrip().split())
    c = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]
    for i in range(q):
        l,r= map(int, stdin.readline().rstrip().split())
        print(len(set(c[l-1:r])))

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

A = []
S = defaultdict(int)
A.append(S.copy())
for c in C:
    S[c] += 1
    A.append(S.copy())

for j in range(Q):
    count = 0
    l, r = map(int, input().split())
    for key, val in A[r].items():
        if key not in A[l-1].keys() or val - A[l-1][key] > 0:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,Q = (int(x) for x in input().split())
c = [int(x) for x in input().split()]
table = [[int(i) for i in input().split()] for Q in range(Q)]

for i in range(Q):
    print(len(set(c[table[i][0]-1:table[i][1]])))

Submission status: Time Limit Exceeded

Solution code:
n,q = list(map(int,input().split(" ")))
c = list(map(int, input().split(' ')))
ans = [None]*q
for i in range(q):
    l,r = list(map(int,input().split(' ')))
    choose = set(c[l-1:r])
    ans[i] = len(choose)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,q= map(int,input().split(" "))
c= list(map(int,input().split(" ")))
d=[[0 for j in range(n)] for i in range(n)]
for i in range(n):
    d[i][i]=1<<(c[i]-1)
    for j in range(i+1,n):
        if not(d[i][j-1] & 1<<(c[j]-1)):
            d[i][j]=d[i][j-1] + (1<<(c[j]-1))
        else:
            d[i][j]=d[i][j-1]

for _ in range(q):
    l,r = map(int, input().split(" "))
    print(bin(d[l-1][r-1]).count('1'))

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
n,q=map(int,input().split())
table=np.array([[0 for _ in range(n)] for _ in range(n+1)])
C=list(map(int,input().split()))
for i in range(1,n+1):
    c=C[i-1]-1
    table[i]=table[i-1][:]
    table[i][c]+=1


for _ in range(q):
    l,r=map(int,input().split())
    ans=list(map(lambda x,y: x==y,table[r],table[l-1]))
    print(n-sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split(" "))
c=tuple(map(int,input().split(" ")))
for i in range(q):
    a,b = [int(i) for i in input().split()]
    arr=[]
    ans=0
    for i in range(a-1,b):
        if c[i] not in arr:
            arr.append(c[i])
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            a = i + self.end_leaves
            for j in range(25):
                if a >= 0:
                    a = (a - 1) // 2
                    self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
                else:
                    break
            
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        for i in range(25):
            if y - x > 1:
                if x % 2 == 1:
                    tl = tl | self.tree[x]
                    x += 1
                if y % 2 == 0:
                    tr = self.tree[y] | tr
                    y -= 1
                x >>= 1
                y >>= 1
            elif y - x == 0:
                return len(tl|tr|self.tree[x])
            else:
                return len(tl|tr|self.tree[x]|self.tree[y])
            
N,Q,*f = map(int, open(0).read().split())
c = f[:N]
lr = [f[N+i*2:N+i*2+2] for i in range(Q)]
if N == 1:
    for i in range(Q):
        print(1)
else:
    st = SegmentTree(c)
    for l,r in lr:
        print(st.query(l-1,r-1))

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())
  s = set(c[l-1:r])
  print(len(s))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
LI = lambda: list(map(int, input().split()))

N, Q = LI()
C = LI()
LR = [LI() for _ in range(Q)]


def main():
    n = int(N ** 0.5)
    if n ** 2 < N:
        n += 1
    w = [set() for _ in range(n)]
    for i in range(n):
        for j in range(n):
            k = i * n + j
            if k < N:
                w[i].add(C[k])

    for l, r in LR:
        l, r = l - 1, r - 1
        s = set()
        while l % n != 0 and l < r:
            s.add(C[l])
            l += 1
        while r % n != 0 and l < r:
            s.add(C[r])
            r -= 1
        s.add(C[r])
        while l < r:
            i = l // n
            s |= w[i]
            l += n
        ans = len(s)
        print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instr = lambda: sys.stdin.readline()
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, q = inintm()
C = inintl()

for i in range(q):
    l,r = inintm()
    print(len(Counter(C[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 collections

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

Submission status: Time Limit Exceeded

Solution code:
inpl = lambda: list(map(int,input().split()))
class SegAccumCalc:
    def __init__(self, value, N=0, calc=lambda x,y: x+y):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [None] * (2*N-1)
        for i, v in enumerate(value):
            self.node[i+N-1] = v
        self.calc = lambda x, y: x if y is None else y if x is None else calc(x,y)
        for i in range(N-2,-1,-1):
            left, right = self.node[2*i+1], self.node[2*i+2]
            self.node[i] = self.calc(left, right)

    def update(self, n, v):
        i = (self.N-1) + n
        self.node[i] = v
        while i > 0:
            i = (i-1)//2
            left, right = self.node[2*i+1], self.node[2*i+2]
            new = self.calc(left,right)
            if self.node[i] == new:
                break
            else:
                self.node[i] = new
    
    def at(self, n):
        return self.node[(self.N-1)+n]

    def query(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                s = self.calc(self.node[R-1], s)
            if L & 1:
                s = self.calc(self.node[L-1], s)
                L += 1
            L >>= 1; R >>= 1
        return s

N, Q = inpl()
c = inpl()
sac = SegAccumCalc([{x} for x in c], calc=lambda x, y: x|y)
for q in range(Q):
    l, r = inpl()
    l -= 1
    r -= 1
    print(len(sac.query(l,r+1)))

Submission status: Time Limit Exceeded

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

ql = []
qr = []

for i in range(q):
  _l, _r = map(int, input().split())
  ql.append(_l)
  qr.append(_r)

query = zip(ql, qr)
query2 = sorted(query, key=lambda x:x[1])

ql2, qr2 = zip(*query2)

idx = 0
ans = [[0 for j in range(n + 1)] for i in range(n + 1)]
last = [-1 for i in range(n)]
bit = [0 for i in range(n)]
before = 0

for i in range(q):
  for j in range(before, qr2[i]):
    if last[c[j] - 1] >= 0:
      bit[last[c[j] - 1]] = 0
    last[c[j] - 1] = j
    bit[j] = 1
    before = qr2[i]
  ans[ql2[i]- 1][qr2[i] - 1] = sum(bit[(ql2[i] - 1):(qr2[i])])

for i in range(q):
  print(ans[ql[i] - 1][qr[i] - 1])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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())))

sliceList = []
for i in lr:
    sliceList.append(c[i[0] - 1 : i[1]])

answer = [np.unique(row).size for row in sliceList]

for i in answer:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    for i in range(q):
        l, r = lr[i]
        lr[i] = [l, r, i]
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1] <= i:
            l, r, j = lr[t]
            tmp = sum(r) - sum(l - 1)
            ans[j] = tmp
            t += 1
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import or_

class SegmentTree():

    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e
        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )
        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

sets = SegmentTree(map(lambda e: {e}, cs), or_, set())
for l, r in lrs:
    print(len(sets.folded(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
# input = sys.stdin.readline

def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))


n,q = mp()
c = lmp()
d = [dict()]
import copy
for i in range(n):
    tar = copy.deepcopy(d[i])
    if c[i] not in tar:
        tar[c[i]] = 1
    else:
        tar[c[i]] += 1
    d.append(tar)
for i in range(q):
    l,r = mp()
    cnt = 0
    l -= 1
    tar = list(d[r].items())
    for j in range(len(tar)):
        if tar[j][0] not in d[l]:
            cnt += 1
        elif d[l][tar[j][0]] != tar[j][1]:
            cnt += 1
    print(cnt)


# n,q = mp()
# c = lmp()
# cums = [0]
# c_set = set()
# j_set = [set()]
# for i in range(n):
#     if c[i] not in c_set:
#         c_set.add(c[i])
#         cums.append(cums[i]+1)
#     else:
#         cums.append(cums[i])
# import copy
# for i in range(n):
#     tar = copy.deepcopy(j_set[i])
#     if c[i] not in tar:
#         tar.add(c[i])
#         j_set.append(tar)
#     else:
#         j_set.append(tar)
# print(j_set)
# for i in range(q):
#     l,r = mp()
#     ans = cums[r]-cums[l-1]
#
#

Submission status: Time Limit Exceeded

Solution code:
# Coding is about expressing your feeling and there is always a better way to express your feeling _feelme
import sys,math,numpy as np
#sys.stdin,sys.stdout=open('input.txt','r'),open('output.txt','w')
from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()
# print('{:.3f}'.format(1),round(1.123456789,4))
# np.set_printoptions(sign=' ',legacy='1.13') # legacy add space at sign position
# sys.setrecursionlimit(500000)
def lcm(a,b): return (a*b)//gcd(a,b)
def setbits(n):return bin(n).count('1')
def resetbits(n):return bin(n).count('0')
def modinv(n,p):return pow(n,p-2,p)
def ncr(n,r):
    num,den=1,1;r=min(n,n-r)
    for i in range(r):num*=(n-i);den*=(i+1)
    return num//den
def ncr_p(n, r, p):
    num,den=1,1;r=min(r,n-r)
    for i in range(r):num = (num * (n - i)) % p ;den = (den * (i + 1)) % p
    return (num * modinv(den,p)) % p
def isPrime(num) :
    if num<=1:return False
    if num==2 or n==3:return True
    if (num % 2 == 0 or num % 3 == 0) :return False
    m = int(num**0.5)+1
    for i in range(5,m,6):
        if (num % i == 0 or num % (i + 2) == 0) :return False
    return True
def bin_search(arr, low, high, val):
    while low <= high:
        mid = low + (high - low) // 2;
        if arr[mid] == val:return mid
        elif arr[mid] < val:low = mid + 1
        else:high = mid - 1
    return -1
def sumofdigit(num):
    count=0;
    while num : count+=num % 10;num //= 10;
    return count;
def inputmatrix():
    r,c=iia();mat=[0]*r;
    for i in range(r):mat[i]=iia();
    return r,c,mat;
def prefix_sum(n,arr):
    for i in range(1,n):arr[i]+=arr[i-1]
    return arr;
def binomial(n, k):
    if 0 <= k <= n:
        ntok = 1;ktok = 1
        for t in range(1, min(k, n - k) + 1):ntok *= n;ktok *= t;n -= 1
        return ntok // ktok
    else:return 0
def divisors(n):
    res = [];
    for i in range(1,ceil(sqrt(n))+1):
        if n%i == 0:
            if i==n//i:res.append(i)
            else:res.append(i);res.append(n//i)
    return res;

# code here ----->
MAX = 500001

# structure to store queries
class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

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

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

def answeringQueries(arr, n, queries, q):

    bit = [0] * (n + 1)

    last_visit = [-1] * MAX

    ans = [0] * q

    query_counter = 0
    for i in range(n):
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] =  query(queries[query_counter].r + 1, bit, n) -  query(queries[query_counter].l, bit, n)
            query_counter += 1
    for i in range(q):
        print(ans[i])

if __name__ == "__main__":
    n,q=iia()
    a=iia()
    queries=[]
    for i in range(q):
        aa,bb=iia()
        aa-=1
        bb-=1
        queries.append(Query(aa,bb,i))
    queries.sort(key = lambda x: x.r)
    answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
n,q = [int(x) for x in input().split(" ")]
num_lis = [int(x) for x in input().split(" ")]

for i in range(q):
    a,b = [int(x) for x in input().split(" ")]
    #print(a,b)#デバッグ
    count = 0
    kind = []
    for i in range(a-1, b):
        #print(num_lis[i])#デバッグ
        if num_lis[i] not in kind:
            kind.append(num_lis[i])
            count += 1
    print(count)

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(np.unique(c[L-1:R])))
    print(len(set(c[L-1:R])))