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: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit#,i8


def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)

# Query取得-rightでソート
# dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=np.empty((Q,2),int)
# #rights=[[] for _ in range(N+1)]

for q in range(Q):
	l,r=map(int,input().split())
	#queries[q] = (q,l,r)
	queries[q][0] = l
	queries[q][1] = r
	#queries=np.sort(queries,order="end")

#queries=np.array(sys.stdin.buffer.read().split(),int).reshape(Q,2)

orderByR=np.argsort(queries[:,1])

# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N+1, int)
# bit indexed tree
bitArray=np.zeros(N+1,int)

#@njit(cache=True)
# @jit(返り値の型(引数1の型,引数2の型,．．．,引数nの型))
#@jit(i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:]))
def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	# 答え配列
	ans=np.zeros(Q, dtype=np.int64)
	#ans=[0]*Q
	# 左からBITと現在色の更新をしながら、クエリのrightに到達したときにBITにクエリ発行する
	qindex = 0

	for n in range(N):
		# 外側のループでは、全部の色をループ

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			# ループ中の場所の色のindexが既にある場合(=過去に、同じ色が登録されていた場合)
			# 今回で、同じ色の一番右側の要素はループ中の要素になる
			# 前登録したこの色の一番右のindexを一度BITから抜く(↓で再度登録される)
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		# この要素の色の一番右のindexを、BITに登録
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		# while qindex < Q and n+1 == queries[qindex][2]:
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			# print(tmpIndex,start,end,ans[tmpIndex])
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	cc.compile()
	exit(0)
from my_module import main

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)

Submission status: Runtime Error

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

# numpyを使ってcount_nonzero
for i in range(Q):
    m = np.zeros(N)
    for j in range(r[i]-l[i]+1):
        m[c[j+l[i]-1]] += 1
    print(np.count_nonzero(m))

Submission status: Runtime Error

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

for i in range(Q):
    m = np.zeros(N)
    for j in range(r[i]-l[i]+1):
        m[c[j+l[i]-1]] += 1
    print(np.count_nonzero(m))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

class BIT:
	'''NOTES: 1-origin-indexed
	'''
	def __init__(self, itemCount):
		self.itemCount = itemCount
		self.items = np.zeros(itemCount+1,int)

	def add(self, i, value):
		while i <= self.itemCount:
			self.items[i] += value
			i += (i & (-i))

	def sumFromStart(self, end):
		summary = 0
		i = end
		while i > 0:
			summary += self.items[i]
			i -= (i & (-i))
		return summary

	def sum(self, start,end):
		summary = self.sumFromStart(end) - self.sumFromStart(start-1)
		return summary


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

C=np.array(input().split(), int)

# Query取得-rightでソート
# dtypeQuery = [("index", int), ("start", int), ("end", int)]
# queries=np.empty((Q,2),int)
# #rights=[[] for _ in range(N+1)]

# for q in range(Q):
# 	l,r=map(int,input().split())
# 	#queries[q] = (q,l,r)
# 	queries[q][0] = l
# 	queries[q][1] = r
# 	#queries=np.sort(queries,order="end")

queries=np.array(sys.stdin.buffer.read().split(),int).reshape(Q,2)

sortByR=np.argsort(queries[:,1])

# 答え配列
ans=np.zeros(Q, int)
# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N+1, int)
# bit indexed tree
bitree=BIT(N)
# 左からBITと現在色の更新をしながら、クエリのrightに到達したときにBITにクエリ発行する
qindex = 0
for n in range(N):
	# 外側のループでは、全部の色をループ

	if Q <= qindex:
		break

	if 0 < mostRightColorIndex[C[n]]:
		# ループ中の場所の色のindexが既にある場合(=過去に、同じ色が登録されていた場合)
		# 今回で、同じ色の一番右側の要素はループ中の要素になる
		# 前登録したこの色の一番右のindexを一度BITから抜く(↓で再度登録される)
		bitree.add(mostRightColorIndex[C[n]], -1 )

	# この要素の色の一番右のindexを、BITに登録
	mostRightColorIndex[C[n]] = n+1
	bitree.add(n+1, 1)

	# while qindex < Q and n+1 == queries[qindex][2]:
	while qindex < Q and n+1 == queries[sortByR[qindex]][1]:
		# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
		tmpIndex = sortByR[qindex]
		start = queries[tmpIndex][0]
		end = queries[tmpIndex][1]
		ans[tmpIndex]=bitree.sum(start,end)
		# print(tmpIndex,start,end,ans[tmpIndex])
		qindex += 1


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

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = max(N, Q).bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [0] * N
    for i in range(N):
        ci = next(it)-1
        Aa[i] = ci
    Aq, Ac = [None] * Q, [0] * Q
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r, i = arg >> X, arg & b1

        for j in range(offset, r+1):
            ci = Aa[j]

            lo = N1 + dp[ci]
            hi = N1 + j

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = j + 1
        else:
            offset = r+1
        l = Ac[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
class BIT:
	'''NOTES: 1-origin-indexed
	'''
	def __init__(self, itemCount):
		self.itemCount = itemCount
		self.items = [0 for i in range(itemCount+1)]

	def add(self, i,value):
		while i <= self.itemCount:
			self.items[i] += value
			i += (i & (-i))

	def sumFromStart(self, end):
		summary = 0
		i = end
		while i > 0:
			summary += self.items[i]
			i -= (i & (-i))
		return summary

	def sum(self, start,end):
		summary = self.sumFromStart(end) - self.sumFromStart(start-1)
		return summary

import numpy as np

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

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

# Query取得-rightでソート
dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=[]
for q in range(Q):
	l,r=map(int,input().split())
	queries.append( (q,l,r) )
queries=np.array(queries, dtype=dtypeQuery)
queries=np.sort(queries,order="end")

# 答え配列
ans=np.zeros(Q, dtype=np.int)
# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N, dtype=np.int)
# bit indexed tree
bitree=BIT(N)
# 左からBITと現在色の更新をしながら、クエリのrightに到達したときにBITにクエリ発行する
qindex = 0
for n in range(N):
	# 外側のループでは、全部の色をループ

	if 0 < mostRightColorIndex[C[n]]:
		# ループ中の場所の色のindexが既にある場合(=過去に、同じ色が登録されていた場合)
		# 今回で、同じ色の一番右側の要素はループ中の要素になる
		# 前登録したこの色の一番右のindexを一度BITから抜く(↓で再度登録される)
		bitree.add(mostRightColorIndex[C[n]], -1 )

	# この要素の色の一番右のindexを、BITに登録
	mostRightColorIndex[C[n]] = n+1
	bitree.add(n+1, 1)

	while qindex < Q and n+1 == queries[qindex][2]:
		# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
		index = queries[qindex][0]
		start = queries[qindex][1]
		end = queries[qindex][2]
		ans[index]=bitree.sum(start,end)
		# print(index,start,end,ans[index])
		qindex += 1


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

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    A = [None] * (N+Q)
    B = [0] * N
    C = [None] * Q
    for i in range(N):
        ci = next(it)-1
        A[i] = i << (X+1) | i
        B[i] = ci
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        A[N+i] = r<< (X+1) | bc | i
        C[i] = l

    A.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    for arg in A:
        r = arg >> (X+1)
        cmd = arg & bc
        i = arg & b1
        if cmd == 0:
            ci = B[i]

            lo = N1 + dp[ci]
            hi = N1 + r

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1

            dp[ci] = r + 1
            continue
        l = C[i]

        num = 0
        j = l + N1
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)

    if Q == 3:
        raise 1

    A = [None] * (N+Q)
    for i in range(N):
        ci = next(it)-1
        A[i] = (i, 0, ci)
    for i in range(Q):
        l, r = next(it)-1, next(it)-1
        A[N+i] = (r, 1, l, i)

    A.sort()
    dp = [0] * N

    N1 = (2*N+1)//2
    dp2 = [0] * (N1*2)

    ans = [0] * Q
    for r, cmd, *arg in A:
        if cmd == 0:
            ci, = arg

            lo = N1 + dp[ci]
            hi = N1 + r

            while lo < hi:
                if lo & 1:
                    dp2[lo] += 1
                    lo += 1
                if not hi & 1:
                    dp2[hi] += 1
                    hi -= 1
                lo >>= 1; hi >>= 1;

            if lo == hi: dp2[lo] += 1


            dp[ci] = r + 1
            continue

        l, i = arg
        num = 0
        j = l + N
        while j > 0:
            num += dp2[j]
            j >>= 1
        ans[i] = num

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)

    if Q == 3:
        raise 1
    A = [None] * (N+Q)
    for i in range(N):
        ci = next(it)-1
        A[i] = (i, 0, ci)
    for i in range(Q):
        l, r = next(it) - 1, next(it) - 1
        A[N+i] = (r, 1, l, i)

    A.sort()
    dp = [-1] * N
    dp2 = [0] * N

    ans = [0] * Q
    for r, cmd, *arg in A:
        if cmd == 0:
            ci, = arg
            for j in range(dp[ci], r):
                dp2[j+1] += 1
            dp[ci] = r
            continue

        l, i = arg
        ans[i] = dp2[l]

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
import math
import collections
from numba import*

@jit(nopython=True)
def mainloop(c, q):
  for i in range(q):
    l, r = map(int, input().split())
    print(len(collections.Counter(c[l-1:r])))
    
n, q = map(int, input().split())
c = list(map(int, input().split()))

mainloop(c, q)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def LF(): return list(map(float, input().split()))
def LC(): return [c for c in input().split()]
def LLI(n): return [LI() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]

def array2d(N, M, initial=0):
    return [[initial]*M for _ in range(N)]

def copy2d(orig, N, M):
    ret = array2d(N, M)
    for i in range(N):
        for j in range(M):
            ret[i][j] = orig[i][j]
    return ret


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

class BIT:
    # 1-index
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


def main():
    N, Q = MAP()
    c = [None]+LI()
    lri = [(l, r, i) for i, (l, r) in enumerate(LLI(Q))]
    ans = [0]*Q

    # クエリは右端でソート
    lri.sort(key=lambda x: x[1])
    good_ball = [-1]*N
    acc = BIT(N)

    # 1-indexで統一したい
    curr = 1
    # 始めの一つの更新
    acc.add(curr, 1)
    good_ball[c[1]] = 1
    for l, r, i in lri:
        # currがrに到達するまで、良い玉の集合を更新する。
        while r > curr:
            curr += 1
            cc = c[curr]
            # 良い玉が既にあれば、bitから除く
            if good_ball[cc] != -1:
                acc.add(good_ball[cc], -1)
            acc.add(curr, 1)
            # 良い玉の位置を更新する
            good_ball[cc] = curr
        # print(l, r, curr, dict(good_ball))
        # print([acc.sum(i+1) for i in range(N)])

        # クエリに答える
        # [l, r]に対する答えはsum(r)-sum(l-1)
        ans[i] = acc.sum(r)-acc.sum(l-1)

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

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50

class segtree:
    def __init__(self, n, init_val=None, init=0):
        self.n = n
        self.init_val = init_val
        self.init = init
        self.k = math.ceil(math.log2(n))

        try:
            init_val[0]
        except:
            raise ValueError('init_val should be list')

        self.bins = [self.init] * (1 << (self.k + 1))
        for idx, i in enumerate(range(1 << self.k, 1 << (self.k + 1))):
            if len(self.init_val) > idx:
                self.bins[i] = init_val[idx]
            else:continue

        self.caliculate()

    def compare(self, l, r):
        return l + r

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]

def run():
    N, Q = map(int, sysread().split())
    right_arr = [-1] * N
    C = list(map(int, sysread().split()))

    L,R = [],[]
    for i in range(Q):
        l,r = map(int, sysread().split())
        L.append((l, i))
        R.append((r, i))
    perms = [i for r,i in sorted(R)]
    ans = [-1] * Q

    seg = segtree(N, init_val = [0]*N, init=0)
    checked = -1
    for perm in perms:
        r, i = R[perm]
        l, _ = L[perm]
        r -= 1
        l -= 1
        #print(l, r)
        for idx, c in enumerate(C[checked+1:r+1], checked+1):
            if right_arr[c] < idx:
                pre_idx = right_arr[c]
                right_arr[c] = idx
                if pre_idx != -1:
                    seg.update(pre_idx, 0)
                seg.update(idx, 1)
                #print(pre_idx, idx, c, seg.bins)
        sub = seg.eval(0, l-1) if l > 0 else 0
        val = seg.eval(0, r) - sub
        ans[i] = val
        checked = r
        #print(val)

    for a in ans:
        print(a)




if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
n,q = map(int,input().split())
c = tuple(map(int,input().split()))
qs = [[] for _ in range(n)]
for i in range(q):
  l,r = map(int,input().split())
  l -= 1
  r -= 1
  qs[l].append((r,i))

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
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n)]
for i in range(n):
  l = pi[c[i]]
  if l != -1:
    ps[l] = i
  pi[c[i]] = i
    
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n-1,-1,-1):
  if ps[x] != -1:
    d.add(ps[x],1)
  for r,i in qs[x]:
    ans[i] = (r-x+1)-d.sum(r)

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

Submission status: Runtime Error

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

class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.elem = [0] * (n + 1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.elem[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.elem[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.elem[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.elem[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [0]*self.n
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != 0:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(self.lastAppeared[self.array[R]], 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res

##############################################################################################

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

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

Submission status: Runtime Error

Solution code:
import numpy as np
import queue

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
mp = np.zeros((n + 1, n + 1))
wkMp = np.zeros((n + 1, n + 1))
wk = np.full(max(c) + 1, -1)
x = np.full(n + q + 1, -1)
y = np.full(n + q + 1, -1)
cnt = np.full(q + 1, -1)
queryX = np.full(q + 1, -1)
queryY = np.full(q + 1, -1)
cntQuery = 1
queue = queue.Queue()

for i in range(q):
    a, b = map(int, input().split())
    queryX[i] = a
    queryY[i] = b
    mp[-b - 1][a] = 2
    wkMp[-b - 1][a] = i + 1

for i in range(c.size):
    if wk[c[i]] == -1:
        wk[c[i]] = i + 1
    else:
        mp[-(i + 1) - 1][wk[c[i]]] += 1
        wk[c[i]] = i + 1

for i in range(n):
    searchX = n - i
    for j in range(n):
        if mp[j][searchX] == 0:
            continue
        elif mp[j][searchX] == 1:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
        elif mp[j][searchX] == 2:
            queue.put([searchX, n - j])
        elif mp[j][searchX] == 3:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
            queue.put([searchX, n - j])
    while not queue.empty():
        wkX, wkY = queue.get()
        cnt[int(wkMp[-wkY - 1][wkX])] = np.count_nonzero(y <= wkY) - np.count_nonzero(y == -1)

for i in range(1,q + 1):
    print(queryY[i - 1] - queryX[i -1] + 1 - cnt[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import queue

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
mp = np.zeros((n + 1, n + 1))
wkMp = np.zeros((n + 1, n + 1))
wk = np.full(n + 1, -1)
x = np.full(n + 1, -1)
y = np.full(n + 1, -1)
cnt = np.full(n + 1, -1)
queryX = np.full(n + 1, -1)
queryY = np.full(n + 1, -1)
cntQuery = 1
queue = queue.Queue()

for i in range(q):
    a, b = map(int, input().split())
    queryX[i] = a
    queryY[i] = b
    mp[-b - 1][a] = 2
    wkMp[-b - 1][a] = i + 1

for i in range(c.size):
    if wk[c[i]] == -1:
        wk[c[i]] = i + 1
    else:
        mp[-(i + 1) - 1][wk[c[i]]] += 1
        wk[c[i]] = i + 1

for i in range(n):
    searchX = n - i
    for j in range(n):
        if mp[j][searchX] == 0:
            continue
        elif mp[j][searchX] == 1:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
        elif mp[j][searchX] == 2:
            queue.put([searchX, n - j])
        elif mp[j][searchX] == 3:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
            queue.put([searchX, n - j])
    while not queue.empty():
        wkX, wkY = queue.get()
        cnt[int(wkMp[-wkY - 1][wkX])] = np.count_nonzero(y <= wkY) - np.count_nonzero(y == -1)

for i in range(1,q + 1):
    print(queryY[i - 1] - queryX[i -1] + 1 - cnt[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import queue

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
mp = np.zeros((n + 1, n + 1))
wkMp = np.zeros((n + 1, n + 1))
wk = np.full(n + 1, -1)
x = np.full(n + 1, -1)
y = np.full(n + 1, -1)
cnt = np.full(n + 1, -1)
queryX = np.full(n + 1, -1)
queryY = np.full(n + 1, -1)
cntQuery = 1
queue = queue.Queue()

for i in range(q):
    a, b = map(int, input().split())
    queryX[i] = a
    queryY[i] = b
    mp[-b - 1][a] = 2
    wkMp[-b - 1][a] = i + 1

for i in range(c.size):
    if wk[c[i]] == -1:
        wk[c[i]] = i + 1
    else:
        mp[-(i + 1) - 1][wk[c[i]]] += 1
        wk[c[i]] = i + 1

for i in range(n):
    searchX = n - i
    for j in range(n):
        if mp[j][searchX] == 0:
            continue
        elif mp[j][searchX] == 1:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
        elif mp[j][searchX] == 2:
            queue.put([searchX, n - j])
        elif mp[j][searchX] == 3:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
            queue.put([searchX, n - j])
    while not queue.empty():
        wkX, wkY = queue.get()
        cnt[int(wkMp[-wkY - 1][wkX])] = np.count_nonzero(y <= wkY) - np.count_nonzero(y == -1)

for i in range(1,cnt.size):
    print(queryY[i - 1] - queryX[i -1] + 1 - cnt[i])

Submission status: Runtime Error

Solution code:
import numpy as np
import queue

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
mp = np.zeros((n + 1, n + 1))
wkMp = np.zeros((n + 1, n + 1))
wk = np.full(n + 1, -1)
x = np.full(n + 1, -1)
y = np.full(n + 1, -1)
cnt = np.full(q + 1, -1)
queryX = np.full(q + 1, -1)
queryY = np.full(q + 1, -1)
cntQuery = 1
queue = queue.Queue()

for i in range(q):
    a, b = map(int, input().split())
    queryX[i] = a
    queryY[i] = b
    mp[-b - 1][a] = 2
    wkMp[-b - 1][a] = i + 1

for i in range(c.size):
    if wk[c[i]] == -1:
        wk[c[i]] = i + 1
    else:
        mp[-(i + 1) - 1][wk[c[i]]] += 1
        wk[c[i]] = i + 1

for i in range(n):
    searchX = n - i
    for j in range(n):
        if mp[j][searchX] == 0:
            continue
        elif mp[j][searchX] == 1:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
        elif mp[j][searchX] == 2:
            queue.put([searchX, n - j])
        elif mp[j][searchX] == 3:
            x[cntQuery] = searchX
            y[cntQuery] = n - j
            cntQuery += 1
            queue.put([searchX, n - j])
    while not queue.empty():
        wkX, wkY = queue.get()
        cnt[int(wkMp[-wkY - 1][wkX])] = np.count_nonzero(y <= wkY) - np.count_nonzero(y == -1)

for i in range(1,cnt.size):
    print(queryY[i - 1] - queryX[i -1] + 1 - cnt[i])

Submission status: Runtime Error

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 _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

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

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for i, r in zip(queries[i], queries[l]):
            ans[i] = r-l+1-sum(A, r)

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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

last = [-1]*N
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)))