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 FenwickTree():
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
    
    def sum(self, i):
        '''
        i: 1-indexed
        bit(i)のうち最後に現れる1をi -= i&(-i)で消している。
        '''
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        '''
        i: 1-indexed
        '''
        while i <= self.n:
            self.tree[i] += x
            i += i & -i
    
    def query(self, l, r):
        '''
        区間[l, r]でのsumを返す。
        l, r 1-indexed
        '''
        return self.sum(r)-self.sum(l-1)

def main():
    import sys
    from collections import defaultdict
    def input(): return sys.stdin.readline().rstrip()
    
    n, q = map(int, input().split())
    c = [0]+list(map(int, input().split()))
    que = defaultdict(lambda: [])
    cset = defaultdict(int)
    for i in range(q):
        l, r = map(int, input().split())
        que[r].append((l, i))
    # que.sort(key=lambda x: x[2])
    ans = [0]*q
    ft = FenwickTree(n)
    for i in range(1, n+1):
        if cset[c[i]] > 0:
            ft.add(cset[c[i]], -1)
        ft.add(i, 1)
        cset[c[i]] = i
        for l, k in que[i]:
            ans[k] = ft.query(l, i)
    for x in ans:
        print(x)



if __name__ == '__main__':
    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(list(map(int,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])

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(list(map(int,input().split())),dtype=np.int)

# Query取得-rightでソート
dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=np.empty(Q,dtype=dtypeQuery)
for q in range(Q):
	l,r=map(int,input().split())
	queries[q] = (q,l,r)
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)

	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: 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=list(map(int,input().split()))

# Query取得-rightでソート
dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=np.empty(Q,dtype=dtypeQuery)
for q in range(Q):
	l,r=map(int,input().split())
	queries[q] = (q,l,r)
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)

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

Solution code:
import sys
input = sys.stdin.buffer.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

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

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

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

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

Solution code:
class BIT:
	'''NOTES: 1-origin-indexed
	'''
	def __init__(self, itemCount):
		self.itemCount = itemCount
		self.items = [0 for _ 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+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)

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

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x:int(x)-1, input().split()))
query = []
for i in range(q):
    l, r = map(int, input().split())
    query.append((i, l-1, r-1))

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

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

Submission status: Time Limit Exceeded

Solution code:
# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls
        self.n = len(ls)
        self.b = ceil(sqrt(self.n))  # bukectのサイズ及び個数

    def _init_states(self):
        ########################################
        # self.states = None  # その時点における状態(自分で定義しろ) #2つでもいい
        self.n_unique = 0
        self.cnt = defaultdict(lambda: 0)
        ########################################

        # [l,r)の半開区間で考える
        self.l = 0
        self.r = 0

        # queryを格納する用
        self.bucket = [list() for _ in range((self.b + 1))]

    def _add(self, i):
        # i番目の要素を含めて考えるときへstatesを更新
        if self.cnt[self.ls[i]] == 0:
            self.n_unique += 1
        self.cnt[self.ls[i]] += 1

    def _delete(self, i):
        # i番目の要素を削除して考えるときへstatesを更新
        self.cnt[self.ls[i]] -= 1
        if self.cnt[self.ls[i]] == 0:
            self.n_unique -= 1

    def _one_process(self, l, r):
        # クエリ[l,r)に対してstatesを更新する
        for i in range(self.r, r):  # rまで伸長
            self._add(i)
        for i in range(self.r - 1, r - 1, -1):  # rまで短縮
            self._delete(i)
        for i in range(self.l, l):  # lまで短縮
            self._delete(i)
        for i in range(self.l - 1, l - 1, -1):  # lまで伸長
            self._add(i)

        self.l = l
        self.r = r

    def process(self, queries):
        self._init_states()

        # idx = defaultdict(lambda: [])  # queryの順番を記録しておく
        for i, (l, r) in enumerate(queries):  # queryをbucketに格納
            # idx[l, r].append(i)
            self.bucket[l // self.b].append((l, r, i))

        for i in range(len(self.bucket)):
            self.bucket[i].sort(key=itemgetter(1))

        ret = [-1] * len(queries)
        for b in self.bucket:
            for l, r, i in b:  # クエリに答えていく
                self._one_process(l, r)
                ########################################
                # クエリに答える作業をここで書く
                ret[i] = self.n_unique
                ########################################
        return ret


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


N, Q = ints()
C = ints()
queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))


mo = Mo(C)
ans = mo.process(queries)
print(*ans, sep='\n')

# まあTLEなんですけどね

Submission status: Time Limit Exceeded

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

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

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [[S[i], i] for i in range(Q)] #クエリ
  S.sort(key = lambda a: a[0][1]) #区間の右端でソート

  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

  for a in ans:
    print(a)

main(N, Q, C, S)

Submission status: Time Limit Exceeded

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

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

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [[S[i], i] for i in range(Q)] #クエリ
  S.sort(key = lambda a: a[0][1]) #区間の右端でソート

  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)  
    
    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
    #print(BIT) 
    #print(loc)
  for a in ans:
    print(a)

main(N, Q, C, S)

Submission status: Time Limit Exceeded

Solution code:
# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls
        self.n = len(ls)
        self.b = ceil(sqrt(self.n))  # bukectのサイズ及び個数

    def _init_states(self):
        ########################################
        # self.states = None  # その時点における状態(自分で定義しろ) #2つでもいい
        self.n_unique = 0
        self.cnt = defaultdict(lambda: 0)
        ########################################

        # [l,r)の半開区間で考える
        self.l = 0
        self.r = 0

        # queryを格納する用
        self.bucket = [defaultdict(lambda:list()) for _ in range((self.b + 1))]

    def _add(self, i):
        # i番目の要素を含めて考えるときへstatesを更新
        if self.cnt[self.ls[i]] == 0:
            self.n_unique += 1
        self.cnt[self.ls[i]] += 1

    def _delete(self, i):
        # i番目の要素を削除して考えるときへstatesを更新
        self.cnt[self.ls[i]] -= 1
        if self.cnt[self.ls[i]] == 0:
            self.n_unique -= 1

    def _one_process(self, l, r):
        # クエリ[l,r)に対してstatesを更新する
        for i in range(self.r, r):  # rまで伸長
            self._add(i)
        for i in range(self.r - 1, r - 1, -1):  # rまで短縮
            self._delete(i)
        for i in range(self.l, l):  # lまで短縮
            self._delete(i)
        for i in range(self.l - 1, l - 1, -1):  # lまで伸長
            self._add(i)

        self.l = l
        self.r = r

    def process(self, queries):
        self._init_states()

        idx = defaultdict(lambda: [])  # queryの順番を記録しておく
        for i, (l, r) in enumerate(queries):  # queryをbucketに格納
            idx[l, r].append(i)
            self.bucket[l // self.b][r].append(l)  # keyがr,lが要素

        # for i in range(len(self.bucket)):
        #     self.bucket[i].sort(key=itemgetter(1))

        ret = [-1] * len(queries)
        for b in self.bucket:
            keys = sorted(b.keys())
            for r in keys:
                for l in b[r]:
                    self._one_process(l, r)
                    ########################################
                    # クエリに答える作業をここで書く
                    ret[idx[l, r].pop()] = self.n_unique
                    ########################################
        return ret


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


N, Q = ints()
C = ints()
queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))


mo = Mo(C)
ans = mo.process(queries)
print(*ans, sep='\n')

# まあTLEなんですけどね

Submission status: Time Limit Exceeded

Solution code:
"""
AtCoder :: Beginner Contest 174 :: Range Set Query
https://atcoder.jp/contests/abc174/tasks/abc174_f
"""
import sys


class SegmentTree:
    def __init__(self, arr):
        self.tree = [set() for _ in range(2 * len(arr))]
        self.N = len(arr)
        for idx, val in enumerate(arr):
            self.tree[idx + len(arr)].add(arr[idx])
        for idx in range(len(arr) - 1, 0, -1):
            self.tree[idx] = self.tree[idx<<1] | self.tree[idx<<1|1]

    def query(self, left, right):
        """Return number of elements from [left, right)."""
        soln = set()
        left += self.N
        right += self.N
        while left < right:
            if left & 1:
                soln = soln | self.tree[left]
                left += 1
            if right & 1:
                right -= 1
                soln = soln | self.tree[right]
            left >>= 1
            right >>= 1
        return len(soln)


def main():
    """Main program."""
    ball_count, query_count = (int(i) for i in sys.stdin.readline().split())
    balls = [0] + [int(i) for i in sys.stdin.readline().split()]
    st = SegmentTree(balls)
    for _ in range(query_count):
        left, right = (int(i) for i in sys.stdin.readline().split())
        print(st.query(left, right+1))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls
        self.n = len(ls)
        self.b = ceil(sqrt(self.n))  # bukectのサイズ及び個数

    def _init_states(self):
        ########################################
        # self.states = None  # その時点における状態(自分で定義しろ) #2つでもいい
        self.n_unique = 0
        self.cnt = defaultdict(lambda: 0)
        ########################################

        # [l,r)の半開区間で考える
        self.l = 0
        self.r = 0

        # queryを格納する用
        self.bucket = [list() for _ in range((self.b + 1))]

    def _add(self, i):
        # i番目の要素を含めて考えるときへstatesを更新
        if self.cnt[self.ls[i]] == 0:
            self.n_unique += 1
        self.cnt[self.ls[i]] += 1

    def _delete(self, i):
        # i番目の要素を削除して考えるときへstatesを更新
        self.cnt[self.ls[i]] -= 1
        if self.cnt[self.ls[i]] == 0:
            self.n_unique -= 1

    def _one_process(self, l, r):
        # クエリ[l,r)に対してstatesを更新する
        for i in range(self.r, r):  # rまで伸長
            self._add(i)
        for i in range(self.r - 1, r - 1, -1):  # rまで短縮
            self._delete(i)
        for i in range(self.l, l):  # lまで短縮
            self._delete(i)
        for i in range(self.l - 1, l - 1, -1):  # lまで伸長
            self._add(i)

        self.l = l
        self.r = r

    def process(self, queries):
        self._init_states()

        idx = defaultdict(lambda: [])  # queryの順番を記録しておく
        for i, (l, r) in enumerate(queries):  # queryをbucketに格納
            idx[l, r].append(i)
            self.bucket[l // self.b].append((l, r))

        for i in range(len(self.bucket)):
            self.bucket[i].sort(key=itemgetter(1))

        ret = [-1] * len(queries)
        for b in self.bucket:
            for l, r in b:  # クエリに答えていく
                self._one_process(l, r)
                ########################################
                # クエリに答える作業をここで書く
                ret[idx[l, r].pop()] = self.n_unique
                ########################################
        return ret


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


N, Q = ints()
C = ints()
queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))


mo = Mo(C)
ans = mo.process(queries)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in ans:
        l, r = map(int, input().split())
        qry[p] = [l-1, r, p]
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
input = stdin.readline
class SegTree():
    def segfunc(self, x, y):
        return x+y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):#p <= x < q
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n, q = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [None]*q
    ans = [None]*q
    p = 0
    for _ in range(q):
        l, r = map(int, input().split())
        qry[p] = (l-1, r, p)
        p += 1
    qry.sort(key=lambda x: x[1])
    dic = {}
    last_update_idx = 0
    seg = SegTree(0, n, [0]*n)
    for l, r, i in qry:
        if last_update_idx < r:
            st = set()
            for j in range(last_update_idx, r):
                if not color[j] in st and color[j] in dic:
                    seg.update(dic[color[j]], 0)
                dic[color[j]] = j
                st.add(color[j])
            for v in st:
                seg.update(dic[v], 1)
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()