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:
import sys


class BinaryIndexedTree(object):
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__e = 0
        self.__node = [self.__e] * (self.__n + 1)
        for i in range(1, self.__n + 1):
            self.update(i, A[i - 1])
    
    def update(self, i, v):
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        return self.sum(j) - self.sum(i - 1)


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
BIT = BinaryIndexedTree(right)

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
        # BIT.update(cur + 1, 0)
        p = P[c]
        if len(p):
            BIT.update(p.pop() + 1, 1)
        cur -= 1
    tmp = BIT.get(l + 1, r + 1)
    ans[i] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
import sys


class BinaryIndexedTree(object):
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__e = 0
        self.__node = [self.__e] * (self.__n + 1)
        for i in range(1, self.__n + 1):
            self.update(i, A[i - 1])
    
    def update(self, i, v):
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        return self.sum(j) - self.sum(i - 1)


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
BIT = BinaryIndexedTree(right)

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
        BIT.update(cur + 1, 0)
        p = P[c]
        if len(p):
            BIT.update(p.pop() + 1, 1)
        cur -= 1
    tmp = BIT.get(l + 1, r + 1)
    ans[i] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
from sys import exit, stdin
import copy

# import numpy as np
from collections import deque, Counter

N, Q = map(int, stdin.readline().split())
C = list(map(int, stdin.readline().split()))
R = [list(map(int, stdin.readline().split())) for _ in range(Q)]


tmp = Counter([])

q = [copy.deepcopy(tmp)]

for c in C:
    tmp[str(c)] += 1
    q.append(copy.deepcopy(tmp))

for r in R:
    d = q[r[1]] - q[r[0] - 1]
    print(len(d))

Submission status: Time Limit Exceeded

Solution code:
# import numpy as np
from sys import exit
import copy
from collections import deque, Counter


class BIT:
    def __init__(self, a=0):
        self.n = a
        self.d = [0] * (a + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.d[i] += x
            i += i & (-i)

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            tmp = i[0] + 1
            while tmp:
                x += self.d[tmp]
                tmp -= tmp & (-tmp)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


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

app = [-1] * (N + 1)
ps = [[] for _ in range(N)]
for i in range(N):
    tmp = app[C[i]]
    if tmp != -1:
        ps[tmp].append(i)
    app[C[i]] = i

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

ans = [0] * Q
d = BIT(N)
for x in range(N - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    for p in qs[x]:
        r = p[0]
        i = p[1]
        ans[i] = (r - x + 1) - d.sum(r)

for re in ans:
    print(re)

Submission status: Time Limit Exceeded

Solution code:
 
# from math import factorial as fac
from collections import defaultdict
# from copy import deepcopy
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
# print(f.readline())
# sys.setrecursionlimit(3*10**6)

	
def print_case_iterable(case_num, iterable):
	print("Case #{}: {}".format(case_num," ".join(map(str,iterable))))

def print_case_number(case_num, iterable):
	print("Case #{}: {}".format(case_num,iterable))

def print_iterable(A):
	print (' '.join(A))

def read_int():
	return int(f.readline().strip())
def read_int_array():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def read_string():
	return list(f.readline().strip())
def ri():
	return int(f.readline().strip())
def ria():
	return [int(x) for x in f.readline().strip().split(" ")]
def rns():
	a =  [x for x in f.readline().split(" ")]
	return int(a[0]), a[1].strip()
def rs():
	return list(f.readline().strip())
def bi(x):
	return bin(x)[2:]





from collections import deque
import math
NUMBER = 10**9 + 7
# NUMBER = 998244353
def factorial(n) : 
	M = NUMBER
	f = 1
  
	for i in range(1, n + 1):  
		f = (f * i) % M # Now f never can  
						# exceed 10^9+7  
	return f
def mult(a,b):
	return (a * b) % NUMBER

def minus(a , b):
	return (a - b) % NUMBER

def plus(a , b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		g, y, x = egcd(b % a, a)
		return (g, x - (b // a) * y, y)

def modinv(a):
	m = NUMBER
	g, x, y = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m
def choose(n,k):
	if n < k:
		assert false
	return  mult(factorial(n), modinv(mult(factorial(k),factorial(n-k)))) % NUMBER
from collections import deque, defaultdict 
import heapq


from types import GeneratorType
def bootstrap(f, stack=[]):
	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to

	return wrappedfunc


def dfs(g, timeIn, timeOut,depths,parents): 
	# assign In-time to node u 
	cnt = 0
	# node, neig_i, parent, depth
	stack = [[1,0,0,0]]
	while stack:
		v,neig_i,parent,depth = stack[-1]
		parents[v] = parent
		depths[v] = depth
		# print (v)
		if neig_i == 0:
			timeIn[v] = cnt    
			cnt+=1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i+=1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u,0,v,depth+1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
  
# def isAncestor(u: int, v: int, timeIn: list, timeOut: list) -> str: 
# 	return timeIn[u] <= timeIn[v] and timeOut[v] <= timeOut[u] 

cnt = 0
@bootstrap
def dfs(v,adj,timeIn, timeOut,depths,parents,parent=0,depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt+=1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u,adj,timeIn,timeOut,depths,parents,v,depth+1)
	timeOut[v] = cnt
	cnt+=1
	yield 

def gcd(a,b): 
	if a == 0: 
		return b 
	return gcd(b % a, a) 
  
# Function to return LCM of two numbers 
def lcm(a,b): 
	return (a*b) / gcd(a,b) 
def get_num_2_5(n):
	twos = 0
	fives = 0
	while n>0 and n%2 == 0:
		n//=2
		twos+=1
	while n>0 and n%5 == 0:
		n//=5
		fives+=1
	return (twos,fives)
def shift(a,i,num):
	for _ in range(num):
		a[i],a[i+1],a[i+2] = a[i+2],a[i],a[i+1]

def equal(x,y):
	return abs(x-y) <= 1e-9
# def leq(x,y):
# 	return x-y <= 1e-9
def getAngle(a, b, c):
	ang = math.degrees(math.atan2(c[1]-b[1], c[0]-b[0]) - math.atan2(a[1]-b[1], a[0]-b[0]))
	return ang + 360 if ang < 0 else ang
def getLength(a,b):
	return math.sqrt((a[0]-b[0])**2 + (a[1]-b[1])**2)


from heapq import heapify, heappush, heappop

def bfs(adj):
	s = set()
	d = defaultdict(set)
	# print('\n'.join(map(str,E.items())))
	q = deque([])
	s.add(0)
	d[0].add(0)
	q.append((0,0))
	while len(q) > 0:
		v,depth = q.popleft()
		for u in adj[v]:
			if u not in s:
				s.add(u)
				d[depth+1].add(u)
				q.append((u,depth+1))
		# print(q)
	return d



def isSubsetSum(arr, n, summ): 
	  
	# The value of subarr[i][j] will be  
	# true if there is a 
	# subarr of arr[0..j-1] with summ equal to i 
	subarr =([[False for i in range(summ + 1)]  
			for i in range(n + 1)]) 
	  
	# If summ is 0, then answer is true  
	for i in range(n + 1): 
		subarr[i][0] = True
		  
	# If summ is not 0 and arr is empty,  
	# then answer is false  
	for i in range(1, summ + 1): 
		 subarr[0][i]= False
			  
	# Fill the subarr table in botton up manner 
	for i in range(1, n + 1): 
		for j in range(1, summ + 1): 
			if j<arr[i-1]: 
				subarr[i][j] = subarr[i-1][j] 
			if j>= arr[i-1]: 
				subarr[i][j] = (subarr[i-1][j] or 
								subarr[i - 1][j-arr[i-1]]) 
	  
	# uncomment this code to print table  
	# for i in range(n + 1): 
	# for j in range(summ + 1): 
	# print (subset[i][j], end =" ") 
	# print() 
	return subarr[n][summ] 



def bfs(v,adj,onpath):
	# d is a dict for depth
	s = set()
	d = defaultdict(set)
	q = deque([])
	s.add(0)
	d[0].add(0)
	q.append((0,0))
	while len(q) > 0:
		v,depth = q.popleft()
		for u in adj[v]:
			if u not in s:
				s.add(u)
				d[depth+1].add(u)
				q.append((u,depth+1))
		# print(q)
	return d












def solution(a,n,q,m):
	s = 1
	while s < n:
		s*=2
	seg = [set() for i in range(2*s)]
	for i in range(n):
		# print(s+i)
		seg[s+i]
		seg[s+i].add(a[i])
	for i in range(s-1,0,-1):
		seg[i] = seg[2*i] | seg[2*i+1]
	# print(seg)

	res = []
	for l, r in q:
		l = s+l-1
		r = s+r-1
		cur = seg[l] | seg[r]
		while l//2 != r//2:
			if l % 2 == 0:
				cur |= seg[l+1]
			if r % 2 == 1:
				cur |= seg[r-1]
			l//=2
			r//=2
		# print(cur)
		res.append(len(cur))
	return '\n'.join(map(str,res))







def main():
	T = 1
	# T = ri()
	for i in range(T):
		# n = ri()
		n,m= ria()
		a = ria()
		q = []
		for i in range(m):
			q.append(ria())

		# a = ria()
		# s = rs()

		# adj = [list() for _ in range(n)]
		# for j in range(m):
		# 	a,b = ria()
		# 	a-=1;b-=1
		# 	adj[a].append(b)

		x = solution(a,n,q,m)

		# continue
		if 'xrange' not in dir(__builtins__):
			print(x) # print("Case #"+str(i+1)+':',x)
		else:
			print >>output,str(x)
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()

if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
#example usage:
#    for l in res:
#       print >>output, str(len(l)) + ' ' +  ' '.join(l)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.size = n
        self.array = [0] * (n + 1)
        self.e = [0] * n

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

    def add(self, i, x):
        self.e[i] += x
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


n, q = map(int, input().split())
*C, = map(lambda x: int(x) - 1, input().split())
P = [0] * n
N = [0] * n
for i in range(n)[::-1]:
    if P[C[i]]:
        N[i] = P[C[i]]
    P[C[i]] = i
F = [0] * n
B = BIT(n)
for i in range(n):
    if F[C[i]] == 0:
        B.add(i, 1)
        F[C[i]] = 1
XY = sorted([(tuple(map(int, input().split())), _) for _ in range(q)])
a = 0
lst = []
for (x, y), _ in XY:
    for i in range(a, x - 1):
        B.add(N[i], 1)
    a = x - 1
    lst.append((_, B.sum(y) - B.sum(x - 1)))
lst.sort()
for _, ans in lst:
    print(ans)

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(int, input().split())
    query.append((i, l-1, r-1))

class BinaryIndexedTree():
    def __init__(self, n):
        self.n = n
        self.bit = [0]*n
    
    def add(self, i, w):
        x = i+1
        while x<=self.n:
            self.bit[x-1] += w
            x += x & -x
    
    def sum(self, i):
        ret = 0
        x = i+1
        while x>0:
            ret += self.bit[x-1]
            x -= x & -x
        return ret

bit = BinaryIndexedTree(n+1)
query.sort(key=lambda x:x[2])
last = [None]*n
ans = [None]*q
nr = -1
for idx, l, r in query:
    for cr in range(nr+1, r+1):
        if last[c[cr]] is not None:
            bit.add(last[c[cr]]+1, -1)
        last[c[cr]] = cr
        bit.add(cr+1, 1)
    nr = r
    ans[idx] = bit.sum(r+1) - bit.sum(l)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
rli = sorted((r << 40) + (l << 20) + i for i, (l, r) in enumerate(zip(mp, mp)))
mask = (1 << 20) - 1

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for k in rli:
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
lr = list(map(int, sys.stdin.buffer.read().split()))
lll = lr[0::2]
rrr = lr[1::2]
idx = sorted(enumerate(rrr), key=itemgetter(1))

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for i, r in idx:
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, lll[i])

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

Submission status: Time Limit Exceeded

Solution code:
import sys


def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i


def bit_sum(arr, i):
    result = 0
    while i > 0:
        result += arr[i]
        i ^= i & -i
    return result


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
queries = sorted((r, l, i) for i, (l, r) in enumerate(zip(mp, mp)))

bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for r, l, i in queries:
    while p < r:
        c = ccc[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1

    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, Q = map(int, input().split())
C = list(map(int, input().split()))
Q_lst = []
for i in range(Q):
  l,r = map(int, input().split())
  Q_lst.append((l, r, i))
Q_lst = sorted(Q_lst, key=lambda x:x[1])
start, end, i = Q_lst.pop(0)
color_tmp = defaultdict(int)
dp = [0] * (N+1)
ans_lst = [0] * Q
for index, c in enumerate(C, 1):
  if not color_tmp[c]:
    color_tmp[c] = index
    dp[index] = 1
  else:
    dp[color_tmp[c]] = 0
    color_tmp[c] = index
    dp[index] = 1
  while True:
    if end == index:
      ans_lst[i] = sum(dp[start:end+1])
      if Q_lst:
        start, end, i = Q_lst.pop(0)
      else:
        break
    else:
      break
for ans in ans_lst:
  print(ans)

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LRST = []
for i in range(Q):
    l, r = map(int, input().split())
    LRST.append((l-1, 0, r-1, i))


class FenwickTree(object):
    def __init__(self, n):
        self._bit = [0] * (n+1)
        self.n = n+1
    
    def add(self, i, a):
        i += 1
        while i < self.n:
            self._bit[i] += a
            i += i & -i
    
    def sum(self, i):
        i += 1
        ret = 0
        while i > 0:
            ret += self._bit[i]
            i -= i & -i
        return ret


def solve():
    memo = [-1] * N
    for i, c in enumerate(C):
        if memo[c-1] >= 0:
            LRST.append((memo[c-1], 1, i, -1))
        memo[c-1] = i
    LRST.sort(reverse=True)
    ans =[0 for _ in range(Q)]
    ft = FenwickTree(N+1)
    for sl, typ, tr, q in LRST:
        if typ == 1:
            ft.add(tr, 1)
        else:
            ans[q] = tr - sl + 1 - ft.sum(tr)
    for a in ans:
        print(a)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

class BinaryIndexedTree:  # 0-index !!!
    """
    init(n):     要素数nを与えて0で初期化
    add(i, x):   i番目の値にxを追加 O(logN)
    sum(i):      区間[0,i)の和を返す O(logN)
    query(l, r): 区間[l,r)の和を返す O(logN)
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)  # 内部的には1-indexで扱う

    def add(self, i, x):  # 0-index
        i += 1  # 内部的には1-indexで扱う
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

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

    def query(self, l, r):  # 0-index  sum of [l,r)
        return self.sum(r) - self.sum(l)

# ---------------------- #

n, q = (int(x) for x in input().split())
C = list(int(x) - 1 for x in input().split())
LR = [tuple(int(x) for x in input().split()) for _ in range(q)]

bit = BinaryIndexedTree(n)
color_right_index = [-1] * n
queries = [(i, l - 1, r - 1) for i, (l, r) in enumerate(LR)]
queries.sort(key=itemgetter(2))
ANS = [0] * q
k = 0
for i, l, r in queries:
    while k <= r and k <= n:
        color = C[k]
        if color_right_index[color] != -1:
            bit.add(color_right_index[color], -1)
        color_right_index[C[k]] = k
        bit.add(k, 1)
        k += 1
    ANS[i] = bit.query(l, r + 1)

for ans in ANS:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = []
    for i, c in enumerate(C):
        if last[c] != -1:
            P.append((last[c], i+1))
        last[c] = i+1

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

    P.sort()
    queries.sort(reverse=True)

    class BIT():
        def __init__(self, n, x=1):
            self.n = n
            self.T = [0]*(n+1)

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

        def sum(self, i):
            ret = 0
            while i:
                ret += self.T[i]
                i -= i & -i
            return ret

    bit = BIT(N)
    ans = [0]*Q
    for l, r, i in queries:
        while P and P[-1][0] >= l:
            cl, cr = P.pop()
            bit.add(cr, 1)
        ans[i] = r-l+1-bit.sum(r)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

I = [[] for _ in range(N)] #各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [0 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c+1 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [[list(map(int, input().split())), i] for i in range(Q)] #クエリ
S.sort(key = lambda a: a[0][1]) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  t = BIT_query(j+1)
  while S and S[-1][0][1] == j+1:#クエリへの返答
    s = S.pop()
    ans[s[1]] = t - BIT_query(s[0][0]-1)
  
  if not S:
    break
    
  if loc[j] > 0: #最右端の玉である場合
    c = loc[j]-1
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c+1
       
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

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

I = [[] for _ in range(N)] #各種類の玉がどこにあるか
for i in range(N):
  I[C[i]-1].append(i)
  
BIT = [0 for _ in range(N+1)]
# Binary Indexed Tree 
# https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum

#Ai += x O(logN)
def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

loc = [0 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    i = I[c][-1]
    BIT_update(i+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[i] = c+1 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [[list(map(lambda a: int(a)-1, input().split())), i] for i in range(Q)] #クエリ
S.sort(key = lambda a: a[0][1]) #区間の右端でソート
#print(S)
#print(I)

ans = [0 for _ in range(Q)]
for j in range(N-1,-1,-1):
  while S and S[-1][0][1] == j:#クエリへの返答
    s = S.pop()
    ans[s[1]] = BIT_query(s[0][1]+1) - BIT_query(s[0][0])
  
  if not S:
    break
    
  if loc[j] > 0: #最右端の玉である場合
    c = loc[j]-1
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c+1
       
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

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


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


last = [-1] * (n + 1)
DD = {}
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for flg, qi in Q[i]:
        if flg:
            ans[qi] = bit.sum(i) - bit.sum(DD[qi] - 1)
        else:
            DD[qi] = i


#    print(q_now, "b")

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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

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


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


last = [-1] * (n + 1)
DD = {}
bit = BIT(n + 1)
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for flg, qi in Q[i]:
        if flg:
            ans[qi] = bit.sum(i) - bit.sum(DD[qi] - 1)
        else:
            DD[qi] = i


#    print(q_now, "b")

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

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, n):
        self.num = n
        self.dat = [0] * (self.num + 1)
        self.depth = n.bit_length()

    def add(self, i, x):
        i += 1
        while i <= self.num:
            self.dat[i] += x
            i += i & -i

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


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


last = [-1] * (n + 1)
DD = {}
bit = BIT(n + 1)
now = 0
for i, c in enumerate(C):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    for flg, qi in Q[i]:
        if flg:
            ans[qi] = bit.sum(i) - bit.sum(DD[qi] - 1)
        else:
            DD[qi] = i
        now += 1


#    print(q_now, "b")

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