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 collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

n, q = LI()
ans = [0] * q
C = LI()
Q = []
for i in range(q):
    l, r = LI()
    Q += [(l-1, 0, i)]
    Q += [(r-1, 1, i)]

Q.sort()
Q += [(INF, 0, 0)]
D = defaultdict(lambda:-1)
DD = {}
bit = BIT(q + 1)
now = 0
q_now = 0
for i in range(n):
    col = C[i]
    last_q_now = D[col]
    if last_q_now == -1:
        bit.add(0, 1)
    else:
        bit.add(last_q_now, 1)
# print(bisect_right(l_idx, last_idx), "a")
    while Q[now][0] <= i:
        idx, flg, qq = Q[now]
        if flg:
            ans[qq] = bit.sum(DD[qq])
        else:
            DD[qq] = q_now
            q_now += 1
        now += 1
    D[col] = q_now
    bit.add(q_now, -1)
#    print(q_now, "b")


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n, q = map(int, input().split())
C = list(map(int, input().split()))
for i in range(q):
  l, r = map(int, input().split())
  count = Counter(C[l-1:r])
  keys = list(count.keys())
  print(len(keys))

Submission status: Time Limit Exceeded

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

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]

from operator import itemgetter
QU.sort(key=itemgetter(0))

from collections import deque

NUM=[deque() for i in range(N+1)]
for i,c in enumerate(C):
    NUM[c].append(i+1)

# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

for x in NUM:
    if x:
        update(x[0],1)

ANS=[-1]*Q

ia=0
for x,y,ind in QU:

    while ia+1!=x:
        update(C[ia+1],-1)
        NUM[C[ia+1]].popleft()
        if NUM[C[ia+1]]:
            update(NUM[C[ia+1]][0],1)
        ia+=1
    ANS[ind]=getvalue(y+1)-1

print(*ANS)

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:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, Q = LI()
c = LI()
lr = []
for i in range(Q):
    l, r = LI()
    l -= 1
    r -= 1
    lr.append((l, r))



tmp_list = []
for q in range(Q):
    l,r = lr[q]

    print(len(set(c[l:r+1])))


# keys = set(c)

# dics = []
# dic = {}
# for key in keys:
#     dic[key] = 0

# for i in range(N):
#     dic[c[i]] += 1
#     dics.append(copy.deepcopy(dic))

# for i in range(Q):
#     l, r = lr[i]
#     ans = 0
#     if l > 0:
#         left_dic = dics[l - 1]
#         right_dic = dics[r]
#         for key in keys:
#             if right_dic[key] - left_dic[key] > 0:
#                 ans += 1
#         print(ans)
#     else:
#         left_dic = dics[l - 1]
#         right_dic = dics[r]
#         for key in keys:
#             if right_dic[key] > 0:
#                 ans += 1
#         print(ans)

Submission status: Time Limit Exceeded

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

po = [1]
for i in range(n):
    po.append(po[-1]*2)
li = [0]*n
for i in range(n):
    li[i] = po[c[i] - 1]

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

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
init(li)

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

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    query = []
    for q in range(Q):
        query.append(list(map(int, input().split())))
        query[-1].append(q)
    query.sort(key=lambda x: x[1])

    last = [0] * (N+1)
    for i, c in enumerate(C):
        if i > query[0][1]-1:
            break
        last[c] = i+1

    bit = Bit(N)
    for i in range(1, N+1):
        if last[i]:
            bit.add(last[i], 1)
    r_prev = query[0][1]
    ans = [0] * Q
    for l, r, q in query:
        if r > r_prev:
            for i in range(r_prev+1, r+1):
                j = last[C[i-1]]
                if j:
                    bit.add(j, -1)
                last[C[i-1]] = i
                bit.add(i, 1)
        ans[q] = bit.sum(r) - bit.sum(l-1)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
# 条件入力
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 sys
data = [int(v) for v in sys.stdin.read().split()[::-1]]

def inp():
    return data.pop()

n, q = inp(), inp()
*c, = [inp() for _ in range(n)]


n_intervals = int(n ** .5)
interval_length = (n + n_intervals - 1) // n_intervals

queries = []
ans = []
for i in range(q):
    l, r = inp(), inp()
    l -= 1
    r -= 1
    queries.append((l, r, i))

# print(interval_length)
queries.sort(key=lambda q: (q[0] // interval_length, q[1]))

freq = [0] * (n + 2)

prev_l = 0
prev_r = -1

cnt = 0
for q_idx in range(len(queries)):
    l, r, i = queries[q_idx]
    while prev_l < l:
        freq[c[prev_l]] -= 1
        if freq[c[prev_l]] == 0:
            cnt -= 1
        prev_l += 1
    while prev_l > l:
        prev_l -= 1
        freq[c[prev_l]] += 1
        if freq[c[prev_l]] == 1:
            cnt += 1
    while prev_r < r:
        prev_r += 1
        freq[c[prev_r]] += 1
        if freq[c[prev_r]] == 1:
            cnt += 1
    while prev_r > r:
        freq[c[prev_r]] -= 1
        if freq[c[prev_r]] == 0:
            cnt -= 1
        prev_r -= 1

    # print(freq)
    ans.append((cnt, i))

ans.sort(key=lambda q: q[1])
ans = [v[0] for v in ans]
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N,K=map(int,input().split())
A=list(map(int,input().split()))
L=[[0]*(N+1)]
M=[0]*(N+1)
for i in range(N):
    M[A[i]]+=1
    H=list(M)
    L.append(H)
for i in range(K):
    l,r=map(int,input().split())
    ans=0
    for i in range(N+1):
        if((L[r][i]-L[l-1][i])!=0):
            ans+=1
    print(ans)
#print(L)

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))


que = []
for i in range(q):
    l, r = map(int, input().split())
    heapq.heappush(que, (r, l, i))

bit = [0 for _ in range(n+1)]
def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= (i & -i)
    return s
def add(i, x):
    while i <= n:
        bit[i] += x
        i += (i & -i)


lastAppeared = [-1 for _ in range(n+1)]
ans = [None for _ in range(q)]
for i in range(1, n+1):
    if lastAppeared[c[i-1]] != -1:
        add(lastAppeared[c[i-1]], -1)
    lastAppeared[c[i-1]] = i
    add(i, 1)

    while len(que) > 0 and que[0][0] == i:
        r, l, x = heapq.heappop(que)
        ans[x] = sum(r) - sum(l-1)

    if len(que) == 0:
        break

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    def MI():
        return map(int, sys.stdin.readline().rstrip().split())
    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, Q = MI()
    c = LI()

    seg = [set()]*(2*N)
    for i in range(N):
        seg[i+N] = {c[i]}
    for i in range(N-1,0,-1):
        seg[i] = seg[i << 1] | seg[i << 1 | 1]

    def fold(L, R):  # [L,R)の区間取得
        L += N
        R += N
        vL = set()
        vR = set()
        while L < R:
            if L & 1:
                vL = vL | seg[L]
                L += 1
            if R & 1:
                R -= 1
                vR = seg[R] | vR
            L >>= 1
            R >>= 1
        return len(vL | vR)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def ctoi(c):  # a～zを0～25に変換する(BITと各アルファベットを対応させる)
    return c-1


n, q = map(int, input().split())
s = list(map(int, input().split()))
bits = [[0]*(n+1) for _ in range(n)]  # BITを各アルファベットについて持つ


def query(pos):  # 各文字について1からpos番目までの文字数を数える
    ret = [0]*n
    for i in range(n):
        tmp = 0
        p = pos
        while p > 0:  # 1からpos番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p & (-p)
        ret[i] = tmp
    return ret


def update(pos, a, x):  # a番目のアルファベットについてpos番目の要素の値にxを加える
    while pos <= n:  # pos番目の要素を含むすべての要素についてxを加える
        bits[a][pos] += x
        pos += pos & (-pos)


for i in range(n):  # 各BITを与えられた文字列で初期化する
    update(i+1, ctoi(s[i]), 1)  # sのi番目の文字に対応するBITのi+1番目の要素を1として更新する

for _ in range(q):
    a, b = map(int, input().split())
    cnt1 = query(b)  # 1からrまでの各文字の文字数
    cnt2 = query(a-1)  # 1からl-1までの各文字の文字数
    ans = 0
    for i in range(n):
        if cnt1[i]-cnt2[i] > 0:  # lからrまでの各文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    
    def __init__(self, init_val, ide_ele):
        
        n = len(init_val)
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        self.tree = [ide_ele] * (2 * self.num)
        
        for i in range(n):
            self.tree[self.num + i ] = init_val[i]
            
        for i in range(self.num-1, 0, -1):
            self.tree[i] = self.tree[2*i] | self.tree[2*i+1]
    
    def query(self, l, r):
        
        res = self.ide_ele
        
        l += self.num
        r += self.num
        
        while l<r:
            if l&1:
                res = res|self.tree[l]
                l += 1
            if r&1:
                res = res|self.tree[r-1]
            l >>= 1
            r >>= 1
        
        return res
        

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

seg = SegTree(c, set())

for i in range(q):
    l,r = map(int,input().split())
    l -= 1
    print(len(seg.query(l,r)))

Submission status: Time Limit Exceeded

Solution code:
#ceilevenoddformula
import math
from queue import PriorityQueue
import bisect
import copy
import time
from collections import Counter
#map(int,input().split())
#int(x) for x in input().split()
MAX = 1000001
  
# 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): 
  
    # initialising bit array 
    bit = [0] * (n + 1) 
  
    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX
  
    # answer for each query 
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        # Setting last_visit[arr[i]] as i and  
        # updating the bit array accordingly 
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        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
  
    # print answer for each query 
    for i in range(q): 
        print(ans[i]) 

n,q=map(int,input().split())
l=[int(x) for x in input().split()]
que=[]
for i in range(q):
	a,b=map(int,input().split())
	que.append(Query(a-1,b-1,i))
que.sort(key = lambda x: x.r)
answeringQueries(l,n,que,q)

Submission status: Time Limit Exceeded

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

X = [len(set(master[l[0]-1:l[1]])) for l in lists]

for x in X:
  print(x)

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)]
ruiseki = [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]
  ruiseki[0] = bit[0]
  for k in range(1, qr2[i]):
    ruiseki[k] = ruiseki[k - 1] + bit[k]
  
  if ql2[i] == 1:
    ans[ql2[i]- 1][qr2[i] - 1] = ruiseki[qr2[i] - 1]
  else:
    ans[ql2[i]- 1][qr2[i] - 1] = ruiseki[qr2[i] - 1] - ruiseki[ql2[i] - 2]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,q= map(int,input().split())
A = list(map(int,input().split()))
C = [list(map(int,input().split())) for i in range(q)]

for i in range(q):
    print(len(set(A[C[i][0]-1:C[i][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()))


#####segfunc######
def segfunc(x,y):
    return x|y

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

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

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

for i in range(n):
    update(i,1<<c[i])

for i in range(Q):
    l,r = map(int,input().split())
    l -= 1

    res = query(l,r)

    print(popcnt(res))

Submission status: Time Limit Exceeded

Solution code:
import collections
numbers = list(map(int, input().split()))
N = numbers[0]
Q = numbers[1]
ball = input().split()
for i in range(Q):
  new = []
  queri = list(map(int, input().split()))
  for j in range(queri[0]-1, queri[1]):
    new.append(ball[j])
  count = collections.Counter(new)
  print(len(count))

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
c = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(Q)]

class SegTree:
  def __init__(self, n) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.tree = [set() for _ in range((i << 1))]

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i].add(x)
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = set()
    while l < r :
      if r & 1 :
        r -= 1
        s |= self.tree[r - 1]
      if l & 1 :
        s |= self.tree[l - 1]
        l += 1
      l >>= 1
      r >>= 1
    return len(s)

ST = SegTree(N + 5)
for i in range(N) :
  ST.update(i, c[i])
 
for l, r in lr :
  print(ST.query(l - 1, r))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

n, q = LI()
ans = [0] * q
C = LI()
Q = []
for i in range(q):
    l, r = LI()
    Q += [(l-1, 0, i)]
    Q += [(r-1, 1, i)]

Q.sort()
Q += [(INF, 0, 0)]
D = defaultdict(lambda:-1)
DD = {}
bit = BIT(q + 1)
now = 0
q_now = 0
l_idx = [INF] * (q + 1)
for i in range(n):
    col = C[i]
    last_q_now = D[col]
    if last_q_now == -1:
        bit.add(0, 1)
    else:
        bit.add(last_q_now, 1)
# print(bisect_right(l_idx, last_idx), "a")
    while Q[now][0] <= i:
        idx, flg, qq = Q[now]
        if flg:
            ans[qq] = bit.sum(DD[qq])
        else:
            DD[qq] = q_now
            l_idx[q_now] = idx
            q_now += 1
        now += 1
    D[col] = q_now
    bit.add(q_now, -1)
#    print(q_now, "b")


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import operator
N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split())) for i in range(Q)]
'''
import random
N = 5*(10**5)
Q = 5*(10**5)
C = [random.randint(1,N) for i in range(N)]
LR = []
for i in range(Q):
    l,r = [random.randint(1,N) for i in range(2)]
    LR.append(sorted([l,r]))
    '''

class SegmentTree:
    def __init__(self,data,op,default):
        N = len(data)
        self.N = N
        self.op = op
        self.default = default
        self.l = 2**((N-1).bit_length())
        self.data = [default]*self.l + data + [default]*(self.l-N)
        for i in range(self.l-1,0,-1):
            #self.data[i] = op(self.data[2*i], self.data[2*i+1])
            self.data[i] = (self.data[2*i] | self.data[2*i+1])

    def get_data(self, i=None):
        if i is None:
            return self.data[self.l:self.l + self.N]
        else:
            return self.data[self.l+i]

    def set(self,i,val):
        i += self.l
        self.data[i] = val
        i = i//2
        while i > 0:
            self.data[i] = (self.data[2*i] | self.data[2*i+1])
            i = i//2

    def get(self,i,j):
        i += self.l
        j += self.l
        s = self.default 
        while j-i > 0:
            if i & 1:
                s =  s |self.data[i]
                i += 1
            if j & 1:
                s = s | self.data[j-1]
                j -= 1
            i, j = i//2, j//2
        return s


f = lambda x,y : x|y
bc = [set([c]) for c in C]
seg = SegmentTree(bc, f, set([]))
#bc = [set([c]) for c in C]
#seg = BIT(bc, f, set([]))
#print(seg.data)

for l,r in LR:
    print(len(seg.get(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

Submission status: Time Limit Exceeded

Solution code:
#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

def main():
    import sys

    lst=[]
    N,Q=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))
    colors=[-1]*(N+1)
    for i,col in enumerate(C):
        if colors[col]+1:
            lst.append((colors[col],i,0,0))
        colors[col]=i  

    seg=SegTree([0]*(N+Q+1),segfunc, ide_ele)
    
    for i in range(Q):
        l,r=list(map(int,sys.stdin.readline().split()))
        lst.append((l-1,r-1,1,i))

    lst.sort(key=lambda x:x[1]+0.1*x[2])

    output=[0]*Q
    for l,r,q,idx in lst:
        if q:
            output[idx]=r-l+1-seg.query(l,r+1)
        else:
            seg.update(l,1)

    for o in output:
        print(o)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())

#####segfunc######
def segfunc(x,y):
    return x.union(y)

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

num =2**(N-1).bit_length()
ide_ele = set()
seg=[ide_ele]*2*num
init([set([c]) for c in Cs])
for _ in range(Q):
    l, r = mapint()
    print(len(query(l-1, r)))

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))


que = []
for i in range(q):
    l, r = map(int, input().split())
    heapq.heappush(que, (r, l, i))

bit = [0 for _ in range(n+1)]
def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= (i & -i)
    return s
def add(i, x):
    while i <= n:
        bit[i] += x
        i += (i & -i)


lastAppeared = [-1 for _ in range(n+1)]
ans = [None for _ in range(q)]
for i in range(1, n+1):
    if lastAppeared[c[i-1]] != -1:
        add(lastAppeared[c[i-1]], -1)
    lastAppeared[c[i-1]] = i
    add(i, 1)

    while len(que) > 0 and que[0][0] == i:
        r, l, x = heapq.heappop(que)
        ans[x] = sum(r) - sum(l-1)

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

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    Qu = []

    for i in range(Q):
        l, r = map(int, input().split())
        Qu.append((r, l, i))
    Qu.sort()
    ans = [0] * Q
    rp = 0
    la = [-1] * (N + 1)
    B = BIT(N)
    for r, l, i in Qu:
        for j in range(rp, r):
            k = C[j]
            if la[k] >= 0:
                B.add(la[k], -1)
            la[k] = j + 1
            B.add(la[k], 1)
        ans[i] = B.sum(r) - B.sum(l - 1)
        rp = r
    print('\n'.join(str(i) for i in ans))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import numpy as np
N,Q=map(int, input().split())
C=np.array(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(np.unique(C[l-1:r]))
    #print(C[l-1:r])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

lr = []
sliceList = []
for i in range(q):
    l, r = map(int, input().split())
    sliceList.append(c[l - 1 : r])

for i in [np.unique(row).size for row in sliceList]:
    print(i)