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:
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 = [0] + LI()
    lr = []
    for i in range(Q):
        l,r = MI()
        lr.append((i,l,r))

    from operator import itemgetter
    from collections import defaultdict

    lr = sorted(lr,key=itemgetter(2))  # 右端rでソート
    a = 0
    d = defaultdict(int)  # d[i] = 玉iが現れた最も右の位置
    ANS = []


    class BIT():
        def __init__(self, init_value):
            self.n = len(init_value)
            self.tree = [0] * (self.n + 1)
            for i in range(1, self.n + 1):
                x = init_value[i - 1]
                while i <= self.n:
                    self.tree[i] += x
                    i += i & (-i)

        def update(self, i, x):  # i(1-index)番目の値を+x
            while i <= self.n:
                self.tree[i] += x
                i += i & (-i)
            return

        def query(self, i):  # 1番目からi(1-index)番目までの和を返す
            res = 0
            while i > 0:
                res += self.tree[i]
                i -= i & (-i)
            return res


    bit = BIT([0]*N)  # 最も右に現れた玉の位置を管理
    for i in range(1,N+1):
        if d[c[i]] == 0:
            d[c[i]] = i
            bit.update(i,1)
        else:
            bit.update(d[c[i]],-1)
            d[c[i]] = i
            bit.update(i, 1)
        while a <= Q-1 and lr[a][2] == i:
            j,l,r = lr[a]
            ANS.append((j,bit.query(r)-bit.query(l-1)))
            a += 1

    ANS.sort()
    print(*[ANS[i][1] for i in range(Q)],sep='\n')


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    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]:
            if i&1:
                query_list[i].sort(key=lambda x: x[1], reverse=True)
            else:
                query_list[i].sort(key=lambda x: x[1])
    query = []
    for ql in query_list:
        query.extend(ql)

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

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

    def rem(i):
        nonlocal 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 sys
input = sys.stdin.buffer.readline

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 = [0]+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**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    for R in range(curR+1,r+1):
        color = c[R]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[color] = R
        BIT_update(R,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:
# -*- 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))
base = 10**6
A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = i + (l-1)*base + r*base**2 + ((l-1)//sqrtN)*base**3
Qs.sort()

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

now = DD(int)
nl = nr = 0
cnt = 0
for qi in Qs:
  i = qi%base
  l = (qi//base)%base
  r = (qi//base**2)%base
  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
  while nl < l:
    if now[A[nl]] == 1:
      cnt -= 1
    now[A[nl]] -= 1
    nl += 1
  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 = 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:
N,Q = map(int,input().split())
c = list(map(int,input().split()))
q = list(list(map(int,input().split()))+[i] for i in range(Q))

BIT = [0]*N

def add(ind,value):
    while ind <= N:
        BIT[ind-1] += value
        ind += ind & -ind
def sum(x):
    out = 0
    while x > 0:
        out += BIT[x-1]
        x -= x & -x
    return out

rbi= {}
ans = [0]*Q
q.sort(key= lambda x:x[1])
R = 0
for l,r,ind in q:
    for i in range(R,r):
        if c[i] in rbi:
            add(rbi[c[i]],-1)
        rbi[c[i]] = i+1
        add(rbi[c[i]],1)
    ans[ind] = sum(r)-sum(l-1)
    R = r

for i in ans:
    print(i)

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(j+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:
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
  ans[LR[i][1]] = Tree.get(left,right)
  lastright = max(right,lastright)
  #print(last)


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)
 
    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:
# -*- 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 #
#############
class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.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 bisect(self, x):
    w = i = 0
    k = self.n
    while k:
      if i+k <= self.n and w + self.data[i+k] < x:
        w += self.data[i+k]
        i += k
      k >>= 1
    return i+1
  
N,Q = IL()

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l,r+1]

Qs = sorted(Qs,key = lambda x:x[2])

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

GB = DD(lambda :-1)
B = BIT(int_log(N+1,2)+1)

nr = 1
for i,l,r in Qs:
  while nr < r:
    x = A[nr-1]
    if GB[x] == -1:
      GB[x] = nr
      B.add(nr,1)
    else:
      B.add(GB[x],-1)
      B.add(nr,1)
      GB[x] = nr
    nr += 1
  ans[i] = B.get(l-1,r)
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add

class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


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

P = [[] for _ in range(N)]
for i, c in enumerate(C):
    P[c - 1].append(i)

right = [0] * N
for p in P:
    if len(p):
        right[p.pop()] = 1
seg = SegmentTree(right, add, 0)

query = []
for i in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    query.append((r - 1, l - 1, i))

query.sort(reverse=True)
ans = [None] * Q

cur = N - 1
for r, l, i in query:
    while r < cur:
        c = C[cur] - 1
        # seg.update(cur, 0)
        p = P[c]
        if len(p):
            seg.update(p.pop(), 1)
        cur -= 1
    tmp = seg.get(l, r + 1)
    ans[i] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add

class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = A[i]
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


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

P = [[] for _ in range(N)]
for i, c in enumerate(C):
    P[c - 1].append(i)

right = [0] * N
for p in P:
    if len(p):
        right[p.pop()] = 1
seg = SegmentTree(right, add, 0)

query = []
for i in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    query.append((r - 1, l - 1, i))

query.sort(reverse=True)
ans = [None] * Q

cur = N - 1
for r, l, i in query:
    while r < cur:
        c = C[cur] - 1
        seg.update(cur, 0)
        p = P[c]
        if len(p):
            seg.update(p.pop(), 1)
        cur -= 1
    tmp = seg.get(l, r + 1)
    ans[i] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
        R = r
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

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

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

    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]:
            if i&1:
                query_list[i].sort(key=lambda x: x[1], reverse=True)
            else:
                query_list[i].sort(key=lambda x: x[1])
    query = []
    for ql in query_list:
        query.extend(ql)

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

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

    def rem(i):
        nonlocal 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:
class Segment_Tree():
    def __init__(self,N,calc,unit,L=[]):
        """calcを演算とするN項のSegment Treeを作成

        N:要素数
        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        X=[[unit]]
        k=1
        m=0

        N=max(N,len(L))
        while k<N:
            k*=2
            m+=1
            X.append([unit]*k)
        
        self.data=X
        self.num=k
        self.depth=m

        for k in range(len(L)):
            self.data[-1][k]=L[k]

        h=self.num
        for d in range(m-1,-1,-1):
            h//=2
            for i in range(h):
                self.data[d][i]=self.calc(self.data[d+1][2*i],self.data[d+1][2*i+1])
        
    def value(self,k):
        return self.data[-1][k]
    
    def update(self,k,x):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """
        
        self.data[-1][k]=x

        for d in range(self.depth-1,-1,-1):
            k=k//2
            self.data[d][k]=self.calc(self.data[d+1][2*k],self.data[d+1][2*k+1])

    def add(self,k,x):
        """第k要素にxを加え,更新する.

        k:数列の要素
        x:更新後の値
        """
        y=self.value(k)
        self.update(k,x+y)

    def sub_array(self,From,To):
        def g(k,m,l,r):
            if r<From or To<l:
                return self.unit
            elif From<=l and r<=To:
                return self.data[k][m]
            else:
                v=g(k+1,2*m,l,(l+r)//2)
                w=g(k+1,2*m+1,(l+r)//2+1,r)
                return self.calc(v,w)
        
        return g(0,0,0,self.num-1)
#-------------------------------------------------
N,Q=map(int,input().split())
C=["*"]+list(map(int,input().split()))

F=[0]*Q
for i in range(Q):
    L,R=map(int,input().split())
    F[i]=(i,L,R)
F.sort(key=lambda x:x[2])

T=Segment_Tree(N+1,lambda x,y:x+y,0)
G=[-1]*(N+1)
Y=1

X=[0]*Q
for (k,L,R) in F:
    while Y<=R:
        c=C[Y]

        if G[c]!=-1:
            T.add(G[c],-1)

        G[c]=Y
        T.add(Y,1)
        Y+=1

    X[k]=T.sub_array(L,R)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()


# Python3 code to find number of
# distinct numbers in a subarray
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])

# Driver Code

# This code is contributed by
# sanjeev2552


def main():
    # Driver Code
    n, q = list(map(int, input().split()))
    a = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        queries.append(Query(l-1, r-1, i))
    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)


if __name__ == '__main__':
    main()