Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Time Limit Exceeded

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

sys.setrecursionlimit(2147483647)
INF = 10 ** 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] += [[0, i]]
    Q[r - 1] += [[1, 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")

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 = [(tuple(map(lambda a: int(a)-1, input().split())), i) for i in range(Q)] #クエリ
S.sort(key = lambda a: (a[0][1], a[0][0])) #区間の右端でソート
#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:
N, Q = map(int, input().split())
C = [int(i) for i in input().split()]
for i in range(Q):
    l, r = map(int, input().split())
    print(len(set(C[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = 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 = [-1 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 #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [(tuple(map(lambda a: int(a)-1, input().split())), i) for i in range(Q)] #クエリ
S.sort(key = lambda a: (a[0][1], a[0][0])) #区間の右端でソート
#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 loc[j] >= 0: #最右端の玉である場合
    c = loc[j]
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c
       
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 = [-1 for _ in range(N)]#各種類の玉のうちの最右端の所在地
for c in range(N):
  if I[c]:
    BIT_update(I[c][-1]+1, 1) #各種類の玉について、最右端の所在地に1記入
    loc[I[c][-1]] = c #各種類の玉について、最右端の所在地に玉の種類を記入
    
S = [(tuple(map(lambda a: int(a)-1, input().split())), i) for i in range(Q)] #クエリ
S.sort(key = lambda a: (a[0][1], a[0][0])) #区間の右端でソート
#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:#クエリへの返答
    ans[S[-1][1]] = BIT_query(S[-1][0][1]+1) - BIT_query(S[-1][0][0])
    S.pop()
    
  if loc[j] >= 0: #最右端の玉である場合
    c = loc[j]
    I[c].pop()
    if I[c]:
      BIT_update(I[c][-1]+1, 1)
      loc[I[c][-1]] = c
       
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 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


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

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

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

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

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


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j, r):
        j += 1
        if arr[C[j]]:
            BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j, r):
        j += 1
        if arr[C[j]]:
            BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


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


def main():
	n,q=MI()
	C=[0]+LI()

	lr=[]

	for i in range(q):
		l,r=MI()
		lr.append([l,r,i])
	lr.sort(key=lambda x:x[1])
	#print(lr)
	R=[-1]*(n+1)

	B=BIT(n)
	now=1
	ans=[-1]*(q)
	for l,r,i in lr:
		while now<=r:
			if R[C[now]]!=-1:
				B.add(R[C[now]],-1)
			R[C[now]]=now
			B.add(R[C[now]],1)
			now+=1
		#print(R)
		#print(B.el)
		ans[i]=B.get(l-1,r)
	print(*ans,sep="\n")



if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted([(lr[1], lr[0], i) for i, lr in enumerate(LR)])
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j + 1
        BIT.add(j + 1, 1)
        j += 1
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([0] * N, lambda x, y: x + y, 0)
arr = [0] * (5 * 10**5 + 1)
RLI = sorted([(lr[1], lr[0], i) for i, lr in enumerate(LR)])
ans = [None] * Q
j = 0
for r, l, i in RLI:
    while j < r:
        st.operate_right(arr[C[j]], -1)
        arr[C[j]] = j + 1
        st.operate_right(j + 1, 1)
        j += 1
    ans[i] = st.query(l, r + 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
header = input()
n = header.split(" ")[0]
q = header.split(" ")[1]
marbles = input().split(" ")
for i in range(int(q)):
  query = input().split(" ")
  query = [int(index) for index in query]
  print(len(set(marbles[query[0] - 1:query[1]])))

Submission status: Time Limit Exceeded

Solution code:
header = input()
n = header.split(" ")[0]
q = header.split(" ")[1]
marbles = input().split(" ")
for i in range(int(q)):
  query = [int(index) for index in input().split(" ")]
  print(len(set(marbles[query[0] - 1:query[1]])))

Submission status: Time Limit Exceeded

Solution code:
from operator import add

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

#クエリを終了位置rでソート。
ilrs = [(i, l-1, r-1) for i, (l, r) in enumerate(lrs)]
ilrs.sort(key = lambda t: t[2])

#重複を区間としてし、終了位置でソートされた状態で列挙。
duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i

#あとは平面走査と呼ばれる探査
ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

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

Submission status: Time Limit Exceeded

Solution code:
class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,input().split())     #対象となるリストの項数, クエリの数
    C = list(map(int,input().split()))  #対象のリスト
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,input().split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()

Submission status: Time Limit Exceeded

Solution code:
# 解説の解法はAtCoder expressみたいな二次元累積和っぽい考え方を平面走査とBIT(セグ木)で高速化
# ここではとりあえず遅延セグ木を用いてけんちょんさんの解法を投げてみる https://drken1215.hatenablog.com/entry/2019/01/01/234400
# 遅延セグ木がTLEしたので,BITで...


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)  # bitは(1based indexっぽい感じなので)

    def init(self, ls):
        assert len(ls) <= self.n
        # lsをbitの配列に入れる
        for i, x in enumerate(ls):  # O(n log n 掛かりそう)
            self.add(i, x)

    def add(self, i, x):
        '''i番目の要素にxを足し込む'''
        i += 1  # 1 based idxに直す
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        '''[i,j)の区間の合計を取得'''
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        '''[,i)の合計を取得'''
        # 半開区間なので i+=1しなくていい
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret


class RangeAddBIT:  # range add query
    # [l,r)にxを加算する
    # [0,[l,r), i)のとき→bit.sum(i)+(rx-lx) (iによらない)
    # [0,[l,i),r)のとき→bit.sum(i)+(ix-lx)
    # [0,i),[l,r)のとき→bit.sum(i) (iによらない)
    # を加算できれば良い。bit.sum(i)が0だと見立てるとわかりやすいかも？
    # 場合分け2つ目における1項目をbit1,2項目をbit2とする
    def __init__(self, n: int):
        self.n = n
        self.bit1 = BIT(n)  # bit1.sum(i)*iで xiを達成したい部分 imos方的に使う
        self.bit2 = BIT(n)  # bit2.sum(i)で -xlを達成したい部分が手に入る。 r<iで区間加算後の和に相当する

    def add(self, l: int, r: int, x):
        '''[l,r)の要素にxを足し込む'''
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        '''[l,r)の区間の合計を取得'''
        return self._sum(r) - self._sum(l)

    def _sum(self, i: int):
        '''[,i)の合計を取得'''
        return self.bit1._sum(i) * i + self.bit2._sum(i)


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd
N, Q = ints()
C = ints()
L, R = read_col(Q)
LRI = [(l - 1, r, i) for i, (l, r) in enu(zip(L, R))]
LRI.sort(key=itemgetter(1))  # 右端でソートしておく
segtree = RangeAddBIT(N + 10)  # l-rまでの種類数を格納(rを広げながら更新していく)
idxprev = defaultdict(lambda: -1)  # 各色の前に出現したidx [prevの位置+1,再出現の位置+1)に区間加算する

ans = [-1] * Q
r_now = 0  # 現在の考慮する位置
for l, r, i in LRI:
    for j in range(r_now, r):
        prev = idxprev[C[j]]
        segtree.add(prev + 1, j + 1, 1)
        idxprev[C[j]] = j
        r_now = j
    ans[i] = segtree.sum(l, l + 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = I[2:2 + N]
L, R = I[2 + N::2], I[3 + N::2]


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


st = SegmentTree([set([c]) for c in C], lambda x, y: x | y, set())

for l, r in zip(L, R):
    print(len(st.query(l - 1, r)))