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:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

import numpy as np

N,Q = IL()
A = IL()

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [np.zeros(K,int) for i in range((2 * self.size))]
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] |= val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
K = 10**5
ST = SegmentTree(N,lambda x,y:x|y,np.zeros(K,int))
for i in range(N):
  x = A[i]-1
  temp = np.zeros(K,int)
  temp[x] = 1
  ST.update(i,temp)
for _ in range(Q):
  L,R = IL()
  print(sum(ST.get(L-1,R)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    sq = int(N ** 0.5)

    Qu = [[] for _ in range(N // sq + 1)]
    for i in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r
        Qu[l // sq].append((r, l, i))
    ans = [0] * Q
    for qr in Qu:
        qr.sort()
        rp, lp = -1, -1
        d = [0] * (N + 1)
        c = 0
        for r, l, i in qr:
            if rp == -1:
                rp, lp = l, l
            for j in range(rp, r):
                d[C[j]] += 1
                if d[C[j]] == 1:
                    c += 1
            if l < lp:
                for j in range(l, lp):
                    d[C[j]] += 1
                    if d[C[j]] == 1:
                        c += 1
            if l > lp:
                for j in range(lp, l):
                    d[C[j]] -= 1
                    if d[C[j]] == 0:
                        c -= 1
            lp, rp = l, r
            ans[i] = c
    print('\n'.join(str(i) for i in ans))

main()

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

h = {}
for i in range(n):
	s = set()
	for j in range(i,n):
		s.add(cis[j])
		h[(i,j)] = len(s)
for _ in range(q):
	u,v = map(int, raw_input().split())
	print h[(u-1,v-1)]

Submission status: Time Limit Exceeded

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

N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [set()]*(4*N0)

def update(k, x):
    k += N0-1
    data[k] = set([x])
    while k >= 0:
        k = (k - 1) // 2
        data[k] = data[2*k+1]|data[2*k+2]


def query(l, r):
    L = l + N0; R = r + N0
    s = set()
    while L < R:
        if R & 1:
            R -= 1
            s|=data[R-1]

        if L & 1:
            s|=data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return len(s)

for i in range(N):
    update(i,c[i])

q = [list(map(int,input().split())) for _ in range(Q)]

for i in range(Q):
    l,r = q[i]
    ans = query(l-1,r)
    print(ans)

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
  ci = set()
  li, ri = map(int, readline().split())
  for j in range(li-1, ri):
    ci.add(C[j])
  print(len(ci))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
table=[[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-ans.count(0))

Submission status: Time Limit Exceeded

Solution code:
def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1] = 2**(init_val[i]-1)   
    #built
    for i in range(num-2,-1,-1):
        seg[i] = 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] = seg[k*2+1] | seg[k*2+2]


def query(p,q): # pからq-1までの最大値
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res = 0
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = res | seg[p] | seg[q]
    return bin(res).count('1')


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

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

init(a)
for i in range(q):
    l, r = map(int,input().split())
    print(query(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:
n,q=list(map(int,input().split()))
c=list(map(int,input().split()))
l=[]
r=[]
for i in range(q):
  o,p=list(map(int,input().split()))
  l.append(o)
  r.append(p)
from collections import Counter
for i in range(q):
  print(len(Counter(c[l[i]-1:r[i]])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

for _ in range(q):
    l,r  = map(int, input().split())
    print(np.unique(c[l-1:r]).size)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for x in range(q):
    l, r, z = query[x]
    for i in range(right, r):
        if appear[c[i]] != -1:
            bit.add(appear[c[i]]+1, -1)
        appear[c[i]] = i
        bit.add(appear[c[i]]+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def main():
    n,q=map(int,input().split())
    lst=[0]*n
    clst=tuple(map(int,input().split()))
    work=Counter([])
    for i in range(n):
        if clst[i] in work:
            work[clst[i]]+=1
        else :
            work[clst[i]]=1
        lst[i]=work.copy()
    
    for _ in range(q):
        l,r=map(int,input().split())
        rwork=lst[r-1]
        if l==1 :
            print(len(rwork))
            continue
        lwork=lst[l-2]
        print(len(rwork-lwork))

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = input().split()

# 回答
lr = [map(int, input().split()) for _ in range(q)]
l, r = [list(i) for i in zip(*lr)]
for i in range(q):
  print(len(set(balls[l[i]-1:r[i]])))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1

N,Q = map(int,input().split())
C=[None]
for c in list(map(int,input().split())):
    C.append(c)

pos=[(list(map(lambda x:int(x),input().split())),i) for i in range(Q)]

pos = sorted(pos,key=lambda x:x[0][1])

last_appeared=[0]*(N+1) #last_appeared[i]: iが最後に現れた場所(1-origin)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
for (l,r),i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r]]=cur_r #lastの更新
        cur_r+=1

    ans[i]=B.sum(r)-B.sum(l-1)


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

Submission status: Time Limit Exceeded

Solution code:
def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f

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 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
        if l==r:
            res = self.tree[l]
        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 popcount(res)
    
N,Q=map(int,input().split())
b = list(map(int,input().split()))
a = [0 for i in range(N)]
for i in range(N):
    a[i]|=(1<<b[i])
def segfunc_union(x, y):
    return x | y
ide_ele_set = 0
seg1 = SegTree(a, segfunc_union, ide_ele_set)
for i in range(Q):
    b,c=map(int,input().split())
    print(seg1.query(b-1,c))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
# d = {c[0]:1}
# cnt = 0
# l = [1]+[0]*(n-1)
# for i in range(1,n):
#     if c[i] not in d:
#         d[i] = 1
#         l[i]= 1
#     l[i] = l[i] + l[i-1]
# print(l)
for i in range(q):
    a,b = map(int,input().split())
    print(len(set(c[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
num=[]
def ap(n1,n2,n3):
    num.append([n1,n2,n3])
for i in range(q):
    l,r=map(int,input().split())
    ap(l,r,i)
num.sort(key=lambda x: x[1])
la=[-1]*max(c)
bit=[0]*n
ans=list(range(q))
num1=0
def cnt(n01,n02):
    return sum(bit[n01-1:n02])
for i in range(q):
    n0=num[i][0]
    n1=num[i][1]
    for j in range(num1,n1):
        num2=c[j]
        num3=la[num2-1]
        if num3==-1:
            la[num2-1]=j
            bit[j]=1
        else:
            bit[num3]=0
            la[num2-1]=j
            bit[j]=1
    ans[num[i][2]]=cnt(n0,n1)
    num1=n1-1
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
l, r = list(zip(*[list(map(int, input().split())) for _ in range(Q)]))

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

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
lr= [list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    print(len(set(c[lr[i][0]-1:lr[i][1]])))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    for _ in range(q):
        l, r = map(int, input().split())
        l -= 1
        print(len(set(c[l:r])))
        
        

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+10))
j = 0
for i in range(n):
    if last[c[i]] >= 0:
        bit.update(last[c[i]]+5, -1)
    bit.update(i+5, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
        j += 1
que.sort()
for i in que:
    print(i[-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

MAX_VAL = 5 * 10 ** 5 + 1


class FenwickTree(object):
 
    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]
 
    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s
 
    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)
 
    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def in_place_answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    queries.sort(key=lambda x: x[1])
    ans = [0] * q
    qc = 0
    for i in range(n):
        if last_visit[cs[i]] != -1:
            ft.add(last_visit[cs[i]], -1)
        last_visit[cs[i]] = i
        ft.add(i, 1)
        while qc < q and queries[qc][1] == i:
            ans[queries[qc][2]] = ft.sum_range(queries[qc][0],
                                                      queries[qc][1] + 1)
            qc += 1
    return ans


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = []
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries.append((le, ri, i))
    ans = in_place_answer_queries(n, q, cs, queries)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

    def get_sum(self,i):
        s = 0
        while i:
            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

n,q = map(int,readline().split())
c = list(map(int,readline().split()))
lr = list(map(int,read().split()))
it = iter(lr)
lr2 = []
for i,l,r in zip(range(q),it,it):
    lr2.append((r-1,l-1,i))

lr2.sort()
st = BIT(n+1)
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
for r,l,i in lr2:
    while(c_ind <= r):
        bef = before[c[c_ind]]
        if(bef!=-1):
            st.add(bef+1,-1)
        before[c[c_ind]] = c_ind
        c_ind += 1

    ans[i] = r-l+1 + st.get_sum(r+1) - st.get_sum(l)

print('\n'.join(map(str,ans)))

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())
    x=collections.Counter(c[l-1:r])
    print(len(x))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
num=[]
def ap(n1,n2,n3):
    num.append([n1,n2,n3])
for i in range(q):
    l,r=map(int,input().split())
    ap(l,r,i)
num.sort(key=lambda x: x[1])
la=[-1]*max(c)
bit=[0]*n
ans=list(range(q))
num1=0
def cnt(n01,n02):
    return bit[n01-1:n02].count(1)
for i in range(q):
    n0=num[i][0]
    n1=num[i][1]
    for j in range(num1,n1):
        num2=c[j]
        num3=la[num2-1]
        if num3==-1:
            la[num2-1]=j
            bit[j]=1
        else:
            bit[num3]=0
            la[num2-1]=j
            bit[j]=1
    ans[num[i][2]]=cnt(n0,n1)
    num1=n1-1
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
def main():
  n, q = map(int, input().split())
  c = list(map(int, input().split()))
  a = len(set(c))
  left = []
  s = set()
  for i in c:
    s.add(i)
    left.append(len(s))
  s =  set()
  right = [0]*n
  for i in range(n-1, -1, -1):
    s.add(c[i])
    right[i] = len(s)
  for i in range(q):
    l, r = map(int, input().split())
    print(max(-left[l-1] + left[r-1]+1, right[l-1]-right[r-1] + 1))
      

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
lr= [list(map(int,input().split())) for _ in range(q)]
for i in range(q):
    print(len(set(c[lr[i][0]-1:lr[i][1]])))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,q=(int(x) for x in input().split())
c=[x for x in input().split()]

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

Submission status: Time Limit Exceeded

Solution code:
from collections import *
from bisect import *

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

d = defaultdict(list)

for i,c in enumerate(C):
    d[c]+=[i]

for _ in range(Q):
    l, r = map(int,input().split())
    print(sum(bisect(L, r-1)-bisect_left(L, l-1) > 0 for L in d.values()))

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])
            
    def union(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            return self.tree[a]
        else:
            self.tree[a] = self.union(a*2) | self.union(a*2+1)
            return self.tree[a]
    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)
    st.union(1)
    for l,r in lr:
        print(st.query(l-1,r-1))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

l = list(input().split())

for _ in range(q):
    a, b = map(int, input().split())
    s = l[a - 1:b]
    c = set(s)
    print(len(c))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
lr = [tuple(map(int, input().split())) for _ in range(Q)]

for l, r in lr:
    #print(l-1, r, C[l-1:r])
    print(len(set(C[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
l=input().split() 
for _ in range(q):
    l1,r1=map(int,input().split())
    print(len(set(l[l1-1:r1])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
line = list(map(int, input().split()))
colors = {}
for cnt, val in enumerate(line):
    if val not in colors:
        colors[val] = [cnt]
    else:
        colors[val].append(cnt)

for idx in range(Q):
    cnt = 0
    start, end = map(int, input().split())
    start -= 1
    ran = set(range(start, end))
    for kind in colors.values():
        if set(kind) & ran != set():
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys, math, bisect



if(__name__ == "__main__"):

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



    Queries = [ [0, 0] for _ in range(Q) ]
    for i in range(Q):
        l, r = map(int, input().strip().split() )
        Queries[i] = [l, r]

    colors_pos = [ [-1]*N for _ in range(N) ]
    poses = [N-1] * N
    for i in range(N-1, -1, -1):
        color = colors[i]-1
        pos = poses[color]
        colors_pos[color][pos] = i
        poses[color] -= 1

    for q in range(Q):
        N_color_lr = 0
        query = Queries[q]
        left = query[0] -1
        right = query[1] - 1

        N_types = 0
        for i in range(N):
            if( bisect.bisect_right(colors_pos[i], right) - bisect.bisect_left(colors_pos[i], left) >0):
                N_types += 1
        """
        if(left==0):
            #rightで考える
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) >0):
                    N_types += 1
        else:
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) - bisect.bisect_left(colors_pos[i], left) >0):
                    N_types += 1
        """
        print(N_types)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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