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 #
#############

N,Q = IL()
sqrtN = math.ceil(math.sqrt(N))

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]
Qs = sorted(Qs,key = lambda x: (x[1]//sqrtN,x[2]))

ans = [None for i in range(Q)]

now = DD(int)
nl = nr = 0
cnt = 0
for i,l,r in Qs:
  while nr > r:
    if now[A[nr-1]] == 1:
      cnt -= 1
    now[A[nr-1]] -= 1
    nr -= 1
  while nr < r:
    if now[A[nr]] == 0:
      cnt += 1
    now[A[nr]] += 1
    nr += 1
  if nl < l:
    while nl < l:
      if now[A[nl]] == 1:
        cnt -= 1
      now[A[nl]] -= 1
      nl += 1
  else:
    while nl > l:
      if now[A[nl-1]] == 0:
        cnt += 1
      now[A[nl-1]] += 1
      nl -= 1

  ans[i] = cnt
  
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

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

slr = sorted(lr, key=lambda x:x[1])
last = [-1] * N
bit = [0] * N
pastr = 0
dic = dict()
for l, r in slr:
    for i in range(pastr, r):
        bit[last[C[i]-1]] = 0
        last[C[i]-1] = i
        bit[i] = 1
    dic[(l,r)] = sum(bit[l-1:r])
    pastr = r

for q in lr:
    print(dic[q])

Submission status: Time Limit Exceeded

Solution code:
from dataclasses import dataclass

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N

    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)

    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res

    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)


@dataclass
class Query:
    i: int
    l: int
    r: int


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

queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))

V = max(C)
bit = BIT(N)
last = [-1] * (max(C) + 1)

query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i

    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)

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

Submission status: Time Limit Exceeded

Solution code:
BIT=[]
siz=0
def BITinit(x):
  global BIT
  global siz
  siz=x
  BIT=[0]*(x+1)

def BITadd(x,a):
  global BIT
  global siz
  z=a
  while(z<=siz):
    BIT[z]+=x
    z+=(z&(-z))

def BITsum(a):
  r=0
  z=a
  while(z>0):
    r+=BIT[z]
    z-=(z&(-z))
  return r

def BITsecsum(a,b):
  return BITsum(max(a,b))-BITsum(min(a,b)-1)

N,Q=map(int,input().split())
BITinit(N+2)
C=list(map(int,input().split()))
q=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
  q[i]=[q[i][0],q[i][1],i]
q.sort(key=lambda x:x[1])
q.append([N+1,N+1])
X=[[] for i in range(N)]
Z=[0]*N
for i in range(N):
  X[C[i]-1].append(i+1)
QR=[[] for i in range(N)]
A=[0]*Q
for i in range(Q):
  QR[q[i][1]-1].append((q[i][0],q[i][2]))
for i in range(N):
  if Z[C[i]-1]:
    BITadd(-1,X[C[i]-1][Z[C[i]-1]-1])
  BITadd(1,X[C[i]-1][Z[C[i]-1]])
  Z[C[i]-1]+=1
  for j in range(len(QR[i])):
    A[QR[i][j][1]]=BITsecsum(QR[i][j][0],i+1)
print(*A,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*10**14+l*10**7+i)

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%10**7
        l = (ist//10**7)%10**7
        r = ist//10**14
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
for i in range(k):
    i, j  = [int(i) for i in input().split()]
    print(len(set(nums[i-1:j])))

Submission status: Time Limit Exceeded

Solution code:
from dataclasses import dataclass

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N

    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)

    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res

    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)


@dataclass
class Query:
    i: int
    l: int
    r: int
    ans: int = -1


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

queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append(Query(i, l - 1, r - 1))
queries.sort(key=lambda q: q.r)

V = max(C)
bit = BIT(N)
last = [-1] * (max(C) + 1)

query_idx = 0
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i

    while query_idx < Q and queries[query_idx].r <= i:
        q = queries[query_idx]
        q.ans = bit.sum_in(q.l, q.r)
        query_idx += 1

queries.sort(key=lambda q: q.i)
print('\n'.join(map(lambda q: str(q.ans), queries)))

Submission status: Time Limit Exceeded

Solution code:
from operator import add, mul, sub, or_


class SegmentTree:
    '''
    セグメント木(遅延ではない)
    1-indexd セグメント木
    values : 値の配列
    op : 区間に対する関数
    ie : 初期値
    '''

    def __init__(self, values, op, ie):
        self.values = values
        vlen = len(values)
        self.op = op
        self.size = 2 ** (vlen-1).bit_length()
        self.tree = [ie]*self.size + self.values + [ie]*(self.size-vlen)
        self.ie = ie

        for i in range(self.size-1, 0, -1):
            self.tree[i] = self.op(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, v):
        i += self.size
        self.tree[i] = v
        while i > 0:
            i //= 2
            self.tree[i] = self.op(self.tree[i*2], self.tree[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        ret = self.ie
        while l < r:
            if l & 1:
                ret = self.op(ret, self.tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.op(ret, self.tree[r])
            l //= 2
            r //= 2
        return ret


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

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

st = SegmentTree([0]*(N+1), add, 0)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        st.update(finds[c[i]], 0)

    finds[c[i]] = i
    st.update(finds[c[i]], 1)

    for j, x in q[i]:
        ans[j] = st.query(x, i+1)

for a in ans:
    print(a)

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 #
#############

N,Q = IL()
sqrtN = math.ceil(math.sqrt(N))

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]
Qs = sorted(Qs,key = lambda x: (x[1]//sqrtN,x[2]))

ans = [None for i in range(Q)]

now = DD(int)
nl = nr = 0
cnt = 0
block = 1
for i,l,r in Qs:
  if l >= sqrtN*block:
    while l >= sqrtN*block:
      block += 1
    while nr > r:
      if now[A[nr-1]] == 1:
        cnt -= 1
      now[A[nr-1]] -= 1
      nr -= 1
  while nr < r:
    if now[A[nr]] == 0:
      cnt += 1
    now[A[nr]] += 1
    nr += 1
  if nl < l:
    while nl < l:
      if now[A[nl]] == 1:
        cnt -= 1
      now[A[nl]] -= 1
      nl += 1
  else:
    while nl > l:
      if now[A[nl-1]] == 0:
        cnt += 1
      now[A[nl-1]] += 1
      nl -= 1

  ans[i] = cnt
  
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9
val = 0
Bsize = 700

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

    # ABC174-F

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

    query_list = [[] for _ in range(N // Bsize + 1)]
    for q in range(Q):
        l, r = map(int, input().split())
        query_list[(l-1) // Bsize].append((l - 1, r - 1, q))
    for i in range(N // Bsize + 1):
        if query_list[i]:
            query_list[i].sort(key=lambda x: x[1])
    query = []
    for ql in query_list:
        query.extend(ql)

    # [l, r)での求める値を管理するための変数たち
    # 問題によって変える
    cnt = [0] * (N + 1)

    # 区間の伸縮操作
    # 問題によって変える
    def add(i):
        global val
        cnt[A[i]] += 1
        if cnt[A[i]] == 1:
            val += 1

    def rem(i):
        global val
        cnt[A[i]] -= 1
        if cnt[A[i]] == 0:
            val -= 1

    # init
    l, r, _ = query[0]
    for i in range(l, r + 1):
        add(i)

    # process
    ans = [0] * Q
    for l_new, r_new, q in query:
        if r < r_new:
            for i in range(r + 1, r_new + 1):
                add(i)
        elif r > r_new:
            for i in range(r, r_new, -1):
                rem(i)
        if l < l_new:
            for i in range(l, l_new):
                rem(i)
        elif l > l_new:
            for i in range(l - 1, l_new - 1, -1):
                add(i)
        l = l_new
        r = r_new
        ans[q] = val

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

colors = list(input().split())

colur_last_indexs = [{} for _ in range(N)]

temp_colors = {}
for i, c in enumerate(colors):
    temp_colors[c] = i

    colur_last_indexs[i] = copy.deepcopy(temp_colors)

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

    if l == 0:
        result.append(len(colur_last_indexs[r]))
    else:
        all_nums = colur_last_indexs[r]

        rest_count = 0
        for c in all_nums.keys():
            if all_nums[c] >= l:
                rest_count += 1
        result.append(rest_count)

for r in result:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append((l, r, i))

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for l, r, i in query:
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

    # ABC174-F

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

    Bsize = int(N ** 0.5) + 1
    query = []
    for q in range(Q):
        l, r = map(int, input().split())
        query.append((l - 1, r - 1, q))
    query.sort(key=lambda x: x[1])
    query.sort(key=lambda x: x[0] // Bsize)

    # [l, r)での求める値を管理するための変数たち
    # 問題によって変える
    cnt = [0] * (N + 1)

    # 区間の伸縮操作
    # 問題によって変える
    def add(i):
        global val
        cnt[A[i]] += 1
        if cnt[A[i]] == 1:
            val += 1

    def rem(i):
        global val
        cnt[A[i]] -= 1
        if cnt[A[i]] == 0:
            val -= 1

    # init
    l, r, _ = query[0]
    for i in range(l, r + 1):
        add(i)

    # process
    ans = [0] * Q
    for l_new, r_new, q in query:
        if r < r_new:
            for i in range(r + 1, r_new + 1):
                add(i)
        elif r > r_new:
            for i in range(r, r_new, -1):
                rem(i)
        if l < l_new:
            for i in range(l, l_new):
                rem(i)
        elif l > l_new:
            for i in range(l - 1, l_new - 1, -1):
                add(i)
        l = l_new
        r = r_new
        ans[q] = val

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append((r,l,i))

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for r,l,i in qi:
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        if bq_al[r] == 0:
            bq_al[r] = BIT_query(r)

        ans[i] = bq_al[r]-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**15+l*10**8+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**15
    query %= 10**15
    l = query//10**8
    q = query % 10**8
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# ABC174-F

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

Bsize = int(N ** 0.5)+1
query = []
for q in range(Q):
    l, r = map(int, input().split())
    query.append((l-1, r-1, q, l // Bsize))
query.sort(key=lambda x: x[1])
query.sort(key=lambda x: x[3])

# [l, r)での求める値を管理するための変数たち
# 問題によって変える
cnt = [0] * (N+1)
val = 0

# 区間の伸縮操作
# 問題によって変える
def add(i):
    global val
    cnt[A[i]] += 1
    if cnt[A[i]] == 1:
        val += 1

def rem(i):
    global val
    cnt[A[i]] -= 1
    if cnt[A[i]] == 0:
        val -= 1

# init
l, r, _, _ = query[0]
for i in range(l, r+1):
    add(i)


# process
ans = [0] * Q
for l_new, r_new, q, _ in query:
    if r < r_new:
        for i in range(r+1, r_new+1):
            add(i)
    elif r > r_new:
        for i in range(r, r_new, -1):
            rem(i)
    if l < l_new:
        for i in range(l, l_new):
            rem(i)
    elif l > l_new:
        for i in range(l-1, l_new-1, -1):
            add(i)
    l = l_new
    r = r_new
    ans[q] = val

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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


N,Q = map(int,input().split())
C = list(map(int,input().split()))
#print(C)
LR = []
ans = [0 for _ in range(Q)]
for i in range(Q):
  temp= list(map(int,input().split()))
  LR.append([temp,i]) #クエリとID
LR.sort(key=lambda x : x[0][1])
#print(LR)
CMAX = max(C)
Tree = BIT(N)
last = [-1 for _ in range(CMAX)] #色を0index
left,right = LR[0][0]
for j in range(right):
  mae = last[C[j]-1]
  last[C[j]-1] = j
  if mae !=-1:
    Tree.add(mae+1,-1) #BITは1から
  Tree.add(last[C[j]-1]+1,1) #BITは1から
  #print(Tree.get(left,right))
#print(last)
D = []
#for i in range(1,N+1):
#  detemp = Tree.get(i,i)
#  D.append(detemp)
#print(D)

temp = Tree.get(left,right)
ID = LR[0][1]
ans[ID] = temp
lastright = right  
#print(Tree.get(left,right))
for i in range(1,Q):
  left,right = LR[i][0]
  #print(right,lastright)
  if lastright < right:
    for j in range(lastright,right):
      mae = last[C[j]-1]
      last[C[j]-1] = j
      #print(C[j],mae,j,last[C[j]-1] )
      if mae !=-1:
        #rint(C[j],"A")
        Tree.add(mae+1,-1) #BITは1index
      Tree.add(last[C[j]-1]+1,1) #BITは1index
  temp = Tree.get(left,right)
  ID = LR[i][1]
  ans[ID] = temp
  lastright = max(right,lastright)
  #print(last)


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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append((r,l,i))

    qi.sort()

    ans = [-1]*q
    ln = [-1]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for r,l,i in qi:
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


N,Q = map(int,input().split())
C = list(map(int,input().split()))
#print(C)
LR = []
ans = [0 for _ in range(Q)]
for i in range(Q):
  temp= list(map(int,input().split()))
  LR.append([temp,i]) #クエリとID
LR.sort(key=lambda x : x[0][1])
#print(LR)
CMAX = max(C)
Tree = BIT(N)
last = [-1 for _ in range(CMAX)] #色を0index
left,right = LR[0][0]
for j in range(right):
  mae = last[C[j]-1]
  last[C[j]-1] = j
  if mae !=-1:
    Tree.add(mae+1,-1) #BITは1から
  Tree.add(last[C[j]-1]+1,1) #BITは1から
  #print(Tree.get(left,right))
#print(last)
D = []
#for i in range(1,N+1):
#  detemp = Tree.get(i,i)
#  D.append(detemp)
#print(D)

temp = Tree.get(left,right)
ID = LR[0][1]
ans[ID] = temp
lastright = right  
#print(Tree.get(left,right))
for i in range(1,Q):
  left,right = LR[i][0]
  #print(right,lastright)
  for j in range(lastright,right):
    mae = last[C[j]-1]
    last[C[j]-1] = j
    #print(C[j],mae,j,last[C[j]-1] )
    if mae !=-1:
      #rint(C[j],"A")
      Tree.add(mae+1,-1) #BITは1index
    Tree.add(last[C[j]-1]+1,1) #BITは1index
  temp = Tree.get(left,right)
  ID = LR[i][1]
  ans[ID] = temp
  lastright = max(right,lastright)
  #print(last)


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

Submission status: Time Limit Exceeded

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

colors = list(input().split())

colur_nums = [{} for _ in range(N)]

temp_colors = {}
for i, c in enumerate(colors):
    
    if c not in temp_colors:
        temp_colors[c] = 0
    temp_colors[c] += 1

    colur_nums[i] = copy.deepcopy(temp_colors)

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

    if l == 0:
        result.append(len(colur_nums[r]))
    else:
        minus_nums = colur_nums[l-1]
        all_nums = colur_nums[r]

        rest_count = 0
        for c in all_nums.keys():
            if c not in minus_nums or all_nums[c] > minus_nums[c]:
                rest_count += 1
        result.append(rest_count)

for r in result:
    print(r)