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:

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)
    Q = len(queries)
    bit = BinaryIndexedTree(N)

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

    queries = sorted((r-1,l-1,i) for i,(l,r) in enumerate(queries))
    qi = 0

    res = [None]*Q

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

        temp = None
        while qi < Q and queries[qi][0] == i:
            if temp is None:
                temp = bit._get_sum(i+1)
            res[queries[qi][2]] = temp - bit._get_sum(queries[qi][1])
            qi += 1

    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: Time Limit Exceeded

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))
    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

    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: Time Limit Exceeded

Solution code:
#F - Range Set Query
setColor = {}
Query = []

# 入力
N,Q     = map(int,input().split())
Color   = list(map(int,input().split()))
for i in range(Q):
    l,r   = map(int,input().split())
    setColor = set(Color[l-1:r])
    Query.append(len(setColor))
# 出力
for k in range(Q):
    print(Query[k])

Submission status: Time Limit Exceeded

Solution code:
#F - Range Set Query
left  = []
right = []
setColor = {}
Query = []

# 入力
N,Q     = map(int,input().split())
Color   = list(map(int,input().split()))
for i in range(Q):
    l,r   = map(int,input().split())
    left.append(l-1)
    right.append(r-1)
for j in range(Q):
    setColor = set(Color[int(left[j]):int(right[j])+1])
    Query.append(len(setColor))
# 出力
for k in range(Q):
    print(Query[k])

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 + 1, r + 1):
        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:
N, Q = list(map(int, input().split()))

c = input().split()
  
for i in range(Q):
  l, r = list(map(int, input().split()))
  ans = c[l-1:r-1]
  ans.append(c[r-1])
  print(len(set(ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(Q):
  l, r = list(map(int, input().split()))
  ans = c[l-1:r-1]
  ans.append(c[r-1])
  print(len(set(ans)))

Submission status: Time Limit Exceeded

Solution code:
LI = lambda: list(map(int, input().split()))

N, Q = LI()
C = LI()
LR = [LI() for _ in range(Q)]


class BIT:

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

    def cost_recur(self, i):
        if i == 0:
            return 0
        return self.dat[i] + self.cost_recur(i - (i & -i))

    def sum_cost(self, r):
        return self.cost_recur(r)


def create_arrow_list():
    ret = []
    w = [-1] * (N + 1)
    for i, c in enumerate(C):
        if w[c] == -1:
            w[c] = i
        else:
            t = (w[c], i)
            ret.append(t)
            w[c] = i
    ret.sort(reverse=True)
    return ret


def main():
    arrow_list = create_arrow_list()
    query_list = [(t[0] - 1, t[1] - 1, i) for i, t in enumerate(LR)]
    query_list.sort(reverse=True)
    
    ans = [None] * Q
    bit = BIT(N)
    i, j = 0, 0
    while i != len(arrow_list) or j != Q:
        if i == len(arrow_list):
            x, y, v = query_list[j]
            ans[v] = y - x + 1 - bit.sum_cost(y + 1)
            j += 1
        elif j == N:
            bit.add(arrow_list[i][1], 1)
            i += 1
        else:
            if query_list[j][0] <= arrow_list[i][0]:
                bit.add(arrow_list[i][1], 1)
                i += 1
            else:
                x, y, v = query_list[j]
                ans[v] = y - x + 1 - bit.sum_cost(y + 1)
                j += 1
    
    for i in range(Q):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
LI = lambda: list(map(int, input().split()))

N, Q = LI()
C = LI()
LR = [LI() for _ in range(Q)]


class SegmentTree:

    def __init__(self):
        self.n = self.array_n(N)
        self.dat = [0] * (self.n * 2 - 1)
        self.l = [None] * (self.n * 2 - 1)
        self.r = [None] * (self.n * 2 - 1)
        self.set_range(0, 0, self.n)

    @staticmethod
    def array_n(n):
        ret = 1
        while ret < n:
            ret *= 2
        return ret

    def clear(self):
        self.dat = [0] * (self.n * 2 - 1)
    
    def set_range(self, i, left, right):
        self.l[i] = left
        self.r[i] = right
        if i < self.n - 1:
            self.set_range(2 * i + 1, left, (left + right) // 2)
            self.set_range(2 * i + 2, ((left + right) // 2), right)

    def add(self, i):
        i += self.n - 1
        self.dat[i] += 1
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] += 1

    def cost_recur(self, i, l, r):
        left, right = self.l[i], self.r[i]
        if left == l and right == r:
            return self.dat[i]
        center = (left + right) // 2
        ret = 0
        if l < center:
            ret = self.cost_recur(i * 2 + 1, l, min(center, r))
        if center < r:
            ret += self.cost_recur(i * 2 + 2, max(center, l), r)
        return ret

    def sum_cost(self, l, r):
        return self.cost_recur(0, l, r)


def create_arrow_list():
    ret = []
    w = [-1] * (N + 1)
    for i, c in enumerate(C):
        if w[c] == -1:
            w[c] = i
        else:
            t = (w[c], i)
            ret.append(t)
            w[c] = i
    ret.sort(reverse=True)
    return ret


def main():
    arrow_list = create_arrow_list()
    query_list = [(t[0] - 1, t[1] - 1, i) for i, t in enumerate(LR)]
    query_list.sort(reverse=True)
    
    ans = [None] * Q
    seg = SegmentTree()
    i, j = 0, 0
    while i != len(arrow_list) or j != Q:
        if i == len(arrow_list):
            x, y, v = query_list[j]
            ans[v] = y - x + 1 - seg.sum_cost(0, y + 1)
            j += 1
        elif j == N:
            seg.add(arrow_list[i][1])
            i += 1
        else:
            if query_list[j][0] <= arrow_list[i][0]:
                seg.add(arrow_list[i][1])
                i += 1
            else:
                x, y, v = query_list[j]
                ans[v] = y - x + 1 - seg.sum_cost(0, y + 1)
                j += 1
    
    for i in range(Q):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add, itemgetter


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

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

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


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

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

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

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

    query.sort(reverse=True, key=itemgetter(0))
    ans = [None] * Q

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add

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

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

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


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

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

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

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

spec = [
	("itemCount", i8),
	("items", i8[:])
]

@jitclass(spec)
class BIT:
	'''NOTES: 1-origin-indexed
	'''
	def __init__(self, itemCount,bitArray):
		self.itemCount = itemCount
		self.items = bitArray	#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

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)
bitree=BIT(N,bitArray)

@njit
def mainLoop(N,Q,C,queries,orderByR,mostRightColorIndex,bitree):

	# 答え配列
	#ans=np.zeros(Q, int)
	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から抜く(↓で再度登録される)
			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[orderByR[qindex]][1]:
			# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=bitree.sum(start,end)
			# print(tmpIndex,start,end,ans[tmpIndex])
			qindex += 1

	return ans

for a in mainLoop(N,Q,C,queries,orderByR,mostRightColorIndex,bitree):
	print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
import sys
input = sys.stdin.readline

N, Q = map(int, input().split())
C = np.array(list(map(int, input().split())), dtype='i4')
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((l-1, r-1, i))
LR = np.array(LR, dtype='i4')
ANS = np.zeros(Q, dtype='i4')

# @njit(cache=1)
@jit('void(i4[:],i4,i4)', nopython=True)
def ftadd(ary, i, a):
    i += 1
    n = len(ary)
    while i < n:
        ary[i] += a
        i += i & -i


# @njit(cache=1)
@jit('i4(i4[:],i4)', nopython=True)
def ftsum(ary, i):
    i += 1
    ret = 0
    n = len(ary)
    while i > 0:
        ret += ary[i]
        i -= i & -i
    return ret


# @njit(cache=1)
@jit('void(i4[:], i4[:,:],i4[:],i4,i4)')
def solve(ANS, LR, C, N, Q):
    memo = -np.ones(N, dtype='i4')
    ST = np.zeros((N,2), dtype='i4')
    nst = 0
    for i in range(N):
        c = C[N-1-i]
        if memo[c-1] >= 0:
            ST[nst] = (N-i-1, memo[c-1])
            nst += 1
        memo[c-1] = N-i-1
    ST = ST[:nst]
    # ST.sort(reverse=True)
    LR = LR[np.argsort(LR[:,0])[::-1]]
    # ans = np.array(Q, dtype='i4')
    ft = np.zeros(N+1, dtype='i4')
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j,0] >= l:
            ftadd(ft, ST[j,1], 1)
            j += 1
        ANS[i] = r - l + 1 - ftsum(ft, r)
    # return ans

if __name__ == "__main__":
    solve(ANS, LR, C, N, Q)
    print('\n'.join(map(str, ANS.tolist())))

Submission status: Time Limit Exceeded

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

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)

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: Time Limit Exceeded

Solution code:
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")
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: Time Limit Exceeded

Solution code:
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")
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 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: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
import sys
input = sys.stdin.readline

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


@jit('void(i4[:],i4,i4)')
def ftadd(ary, i, a):
    i += 1
    n = len(ary)
    while i < n:
        ary[i] += a
        i += i & -i


@jit('i4(i4[:],i4)')
def ftsum(ary, i):
    i += 1
    ret = 0
    n = len(ary)
    while i > 0:
        ret += ary[i]
        i -= i & -i
    return ret


def solve():
    memo = [-1] * N
    ST = []
    nst = 0
    for i, c in enumerate(C[::-1]):
        if memo[c-1] >= 0:
            ST.append((N-i-1, memo[c-1]))
            nst += 1
        memo[c-1] = N-i-1
    # ST.sort(reverse=True)
    LR.sort(reverse=True)
    ans =[0 for _ in range(Q)]
    ft = np.zeros((N+1), dtype='i4')
    j = 0
    for l, r, i in LR:
        while j < nst and ST[j][0] >= l:
            ftadd(ft, ST[j][1], 1)
            j += 1
        ans[i] = r - l + 1 - ftsum(ft, r)
    return ans

if __name__ == "__main__":
    print('\n'.join(map(str, solve())))

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
import sys
buf = sys.stdin.buffer
input = buf.readline

# Binary Indexed Tree (Fenwick Tree)
#   date : 2020.08.04
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = np.zeros(n+1, np.int)
        self.el = np.zeros(n+1, np.int)

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

    def add(self, i, x):
        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 solve(n, q, c, z):
    idx = np.argsort(z[:,1]).astype(np.int)
    z = z[idx]
    res = np.zeros(q, np.int)
    bit = BIT(n+2)
    b = np.ones(n+1, np.int)

    j = 1
    for ii in range(q):
        i, l, r = idx[ii], z[ii,0], z[ii,1]
        while j <= r:
            d = c[j-1]
            j += 1
            k = b[d]
            b[d] = j
            bit.add(k+1,1)
            bit.add(j+1,-1)
        res[i] = bit.sum(l+1)
    print('\n'.join(map(str,res)))

def main():
    n, q = map(int, input().split())
    c = np.array( input().split(), dtype=np.int )
    z = np.array( buf.read().split(), dtype=np.int ).reshape(-1,2)
    solve(n,q,c,z)

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

class BIT:
	'''NOTES: 1-origin-indexed
	'''
	def __init__(self, itemCount):
		self.itemCount = itemCount
		self.items = np.zeros(itemCount+1,dtype=np.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(),dtype=np.int)

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


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

# 答え配列
ans=np.zeros(Q, dtype=np.int)
# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N+1, 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)

	for qindex in rights[n+1]:
		# 今の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])


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