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: Accepted

Solution code:
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    sorted_qi = sorted(range(Q), key=lambda i:queries[i][1])

    res = [None]*Q
    pr = 0
    temp = 0
    for qi in sorted_qi:
        l,r = queries[qi]
        for j,c in enumerate(C[pr:r],start=pr):
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            else:
                temp += 1
            last_ind[c] = j
            bit._add(j, 1)

        pr = r
        res[qi] = temp - bit._get_sum(l-1)

    return res

# from random import randrange, seed
# from time import perf_counter

# def test():
#     seed(1234)
#     N = 5*10**5
#     C = [randrange(N) for _ in range(N)]
#     queries = [tuple(sorted((randrange(1,N+1),randrange(1,N+1)))) for _ in range(N)]
#     start = perf_counter()
#     solve(C,queries)
#     stop = perf_counter()
#     print(stop-start)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')
    # test()

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    sorted_qi = sorted(range(Q), key=lambda i:queries[i][1])

    res = [None]*Q
    pr = 0
    temp = 0
    for qi in sorted_qi:
        l,r = queries[qi]
        for j,c in enumerate(C[pr:r],start=pr):
            c = C[j]
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            else:
                temp += 1
            last_ind[c] = j
            bit._add(j, 1)

        pr = r
        res[qi] = temp - bit._get_sum(l-1)

    return res

# from random import randrange, seed
# from time import perf_counter

# def test():
#     seed(1234)
#     N = 5*10**5
#     C = [randrange(N) for _ in range(N)]
#     queries = [tuple(sorted((randrange(1,N+1),randrange(1,N+1)))) for _ in range(N)]
#     start = perf_counter()
#     solve(C,queries)
#     stop = perf_counter()
#     print(stop-start)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')
    # test()

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
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

N, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  q.append([l, r, k])


q.sort(key = lambda x: x[1])
ans = [0 for k in range(Q)]


good = BIT(N)
lastapp = [-1 for _ in range(N)]
end = -1
for k in range(Q):
  l = q[k][0]
  r = q[k][1]
  a = q[k][2]
  for j in range(r, end, -1):
    if lastapp[c[j]-1] == -1:
      lastapp[c[j]-1] = j
      good.add(j+1, 1)
    elif lastapp[c[j]-1] < j:
      good.add(lastapp[c[j]-1]+1, -1)
      good.add(j+1, 1)
      lastapp[c[j]-1] = j
  ans[a] = good.sum(r+1) - good.sum(l)
  end = r
  
for k in range(Q):
  print(ans[k])

Submission status: Accepted

Solution code:
from sys import stdin
#import numpy as np
 
readline = stdin.readline
 
N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # 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
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return
 
  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans
 
ans = main(N, Q, C, S)
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < len(self.data):
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(5*10**5 + 1)

    queries = sorted(((r,l-1,i) for i,(l,r) in enumerate(queries)), key=lambda x:x[0])
    qi = 0

    res = [None]*len(queries)

    for i,c in enumerate(C):
        li = last_ind[c]
        if li is not None:
            bit[li] -= 1
        last_ind[c] = i
        bit[i] += 1

        while qi < len(queries) and queries[qi][0] == i+1:
            res[queries[qi][2]] = bit[queries[qi][1]:i+1]
            qi += 1
        if qi == len(queries):
            break

    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')

Submission status: Accepted

Solution code:
from sys import stdin
#import numpy as np

readline = stdin.readline

N, Q = map(int, readline().split()) 
C = list(map(int, readline().split())) 
S = [list(map(int, readline().split())) for _ in range(Q)] 
#print(S)
def main(N, Q, C, S):    
  # 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
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [(S[i], i) for i in range(Q)] #クエリ
  S.sort(key = lambda s: s[0][1]) #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(Q)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0][1] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0][1] == j+1: #クエリへの返答
      ans[S[k][1]] = t - BIT_query(S[k][0][0]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:

class BinaryIndexedTree:
    def __init__(self, size):
        self.data = [0] * (size+1)
        self.size = size+1
        self.msb = 1 << (size.bit_length()-1)
    
    def _add(self, i, w):
        i += 1
        while i < self.size:
            self.data[i] += w
            i += i & -i
    
    def _get_sum(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    def __getitem__(self, i):
        """
        [0,i)
        """
        if isinstance(i, slice):
            if i.start is None:
                return self._get_sum(i.stop)
            else:
                return self._get_sum(i.stop) - self._get_sum(i.start)
        else:
            return 0 # fake value
    
    __setitem__ = _add
    
    def bisect_left(self, v):
        """
        return smallest i s.t v <= sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] < v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    def bisect_right(self, v):
        """
        return smallest i s.t v < sum[:i]
        """
        i = 0
        k = self.msb
        while k > 0:
            i += k
            if i < len(self.data) and self.data[i] <= v:
                v -= self.data[i]
            else:
                i -= k
            k >>= 1
        return i
    
    bisect = bisect_right



def solve(C, queries):
    N = len(C)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

    last_ind = [None]*(N + 1)
    queries = sorted(((r,l-1,i) for i,(l,r) in enumerate(queries)), key=lambda x:x[0])

    res = [None]*Q
    pr = 0
    for r,l,i in queries:
        for j in range(pr,r):
            c = C[j]
            if last_ind[c] is not None:
                bit._add(last_ind[c], -1)
            last_ind[c] = j
            bit._add(j, 1)
        res[i] = bit._get_sum(r)-bit._get_sum(l)
        pr = r

    return res

# from random import randrange, seed
# from time import perf_counter

# def test():
#     seed(1234)
#     N = 5*10**5
#     C = [randrange(N) for _ in range(N)]
#     queries = [tuple(sorted((randrange(1,N+1),randrange(1,N+1)))) for _ in range(N)]
#     solve(C,queries)

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

if __name__ == '__main__':
    N,Q = map(int,readline().split())
    C = list(map(int,readline().split()))

    m = map(int,read().split())
    queries = list(zip(m,m))

    print(*solve(C,queries), sep='\n')
    # test()

Submission status: Accepted

Solution code:

class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
class Query:
    def __init__(self, i, l, r):
        self.i = i
        self.l = l
        self.r = r
    
    
N, Q = map(int, input().split())
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print('\n'.join(map(str, ans)))

Submission status: Accepted

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

def addBIT(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 sumBIT(items, start,end):
	summary = sumFromStart(items, end) - sumFromStart(items, start-1)
	return summary

#@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):

	# 答え配列
	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から抜く(↓で再度登録される)
			addBIT(N,bitArray,mostRightColorIndex[C[n]], -1 )

		# この要素の色の一番右のindexを、BITに登録
		mostRightColorIndex[C[n]] = n+1
		addBIT(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]=sumBIT(bitArray,start,end)
			# print(tmpIndex,start,end,ans[tmpIndex])
			qindex += 1

	return ans

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



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)

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

Submission status: Accepted

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

#@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 import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	main=njit(main, cache=True)
	cc.compile()
	exit(0)
from my_module import main
#from numba import njit
#main=njit('i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])', cache=True)(main)



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)

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

Submission status: Accepted

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

#@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
#from numba import njit
#main=njit('i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])', cache=True)(main)



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)

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

Submission status: Accepted

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

#@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
from numba import njit
main=njit('i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])', cache=True)(main)



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)

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

Submission status: Accepted

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

#@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 import njit
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	main=njit(main)
	cc.compile()
	exit(0)
from my_module import main



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)

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