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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import add, itemgetter


class RMQ():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        while a < b:
            if a & 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if not b & 1:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k=1, l=0, r=-1):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query_bottomup(a, b)


def read():
    N, Q = map(int, input().strip().split())
    C = list(map(int, input().strip().split()))
    # クエリ [l, r) とその順序を持っておく
    LRI = []
    for i in range(Q):
        l, r = map(int, input().strip().split())
        LRI.append((l-1, r, i))
    return N, Q, C, LRI


def solve(N, Q, C, LRI, INF=10**7):
    prev = [0 for i in range(N+1)]
    A = [0 for i in range(N)]
    ans = [0 for i in range(Q)]
    
    rmq = RMQ.from_array(A, op=add, init_value=0)
    # Rの昇順にソート
    LRI.sort(key=itemgetter(1))
    r_prev = 0
    for l, r, i in LRI:
        for j in range(r_prev, r):
            c = C[j]
            # A[prev[c]] = 0
            rmq.update(prev[c], 0)
            prev[c] = j
            # A[j] = 1
            rmq.update(j, 1)
        r_prev = r
        ans[i] = rmq.query(l, r)

    for a in ans:
        print(a)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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][1], S[i][0], i] for i in range(Q)] #クエリ
  S.sort() #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(N)]
  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] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0] == j+1: #クエリへの返答
      ans[S[k][2]] = t - BIT_query(S[k][1]-1)
      k += 1
    if k == len(S):
      break
  return ans

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

Submission status: Wrong Answer

Solution code:
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)]
color = [[] for _ in range(N)]

for k in range(N):
  color[c[k]-1].append(k)

good = [0 for _ in range(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[j] = 1
    elif lastapp[c[j]-1] < j:
      good[lastapp[c[j]-1]] = 0
      good[j] = 1
      lastapp[c[j]-1] = j
  ans[a] = sum(good[l:r+1])
  end = r
  

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

Submission status: Wrong Answer

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: Wrong Answer

Solution code:


# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls.copy()
        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


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


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


N, Q = ints()
C = ints()

mo = Mo(C)

queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))
ans = mo.process(queries)
print('unko')
# print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:


# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls.copy()
        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


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


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


N, Q = ints()
C = ints()

mo = Mo(C)

queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))
print('unko')
# ans = mo.process(queries)
# print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:


# mo's algorithm
# offline queryをlについて平方分割、rについてしゃくとり法したもの
from collections import defaultdict
from operator import itemgetter


class Mo:
    def __init__(self, ls):
        # データは突っ込んで置きたい
        from math import sqrt, ceil
        self.ls = ls.copy()
        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


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


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


N, Q = ints()
C = ints()

mo = Mo(C)

queries = []
for _ in range(Q):
    l, r = ints()
    queries.append((l - 1, r))
print('unko')
# ans = mo.process(queries)
# print(*ans, sep='\n')

Submission status: Wrong Answer

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 reversed(range(last_update_idx, r)):
                if not color[j] in st:
                    if color[j] in dic:
                        seg.update(dic[color[j]], 0)
                    else:
                        dic[color[j]] = j
                    seg.update(j, 1)
                    st.add(color[j])
            last_update_idx = r
        ans[i] = seg.query(l, r)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

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

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


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

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

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

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


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

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

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

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

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

    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from bisect import bisect_right


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

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

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

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

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

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

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

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

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

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

lastAppeared = [0]*N
C = []
for i, c in enumerate(map(int, input().split())):
    c -= 1
    C.append(c)
    lastAppeared[c] = i
data = []
for i in range(Q):
    l, r = map(int, input().split())
    data.append((l-1,r-1,i))

data2 = data.copy()
data.sort(key=lambda x:x[1])

BIT = Bit(N)

for a in lastAppeared:
    if a != 0:
        BIT.add(a, 1)

res = [0]*Q
r0 = -1
for l, r, i in data:
    if r != r0:
        BIT.add(lastAppeared[C[r]], -1)
        lastAppeared[C[r]] = r
        BIT.add(lastAppeared[C[r]], 1)
    res[i] = BIT.get(l, r) + 1
    r0 = r

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

Submission status: Wrong Answer

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

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

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

    queries.sort(reverse=True)

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

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

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

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# Hey, there Stalker!!!
# This Code was written by:
# ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
# ▒▒╔╗╔═══╦═══╗▒▒▒╔╗▒▒▒
# ▒╔╝║║╔═╗║╔═╗╠╗▒▒║║▒▒▒
# ▒╚╗║║║║║║║║║╠╬══╣║╔╗▒
# ▒▒║║║║║║║║║║╠╣║═╣╚╝╝▒
# ▒╔╝╚╣╚═╝║╚═╝║║║═╣╔╗╗▒
# ▒╚══╩═══╩═══╣╠══╩╝╚╝▒
# ▒▒▒▒▒▒▒▒▒▒▒╔╝║▒▒▒▒▒▒▒
# ▒▒▒▒▒▒▒▒▒▒▒╚═╝▒▒▒▒▒▒▒
# ▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒
#from functools import reduce
from __future__ import division, print_function
mod1=int(1e9+7)
#import resource
#resource.setrlimit(resource.RLIMIT_STACK, [0x100000000, resource.RLIM_INFINITY])
#import threading
#threading.stack_size(2**26)
"""fact=[1]
#for i in range(1,100001):
#    fact.append((fact[-1]*i)%mod)
#ifact=[0]*100001
#ifact[100000]=pow(fact[100000],mod-2,mod)
#for i in range(100000,0,-1):
#    ifact[i-1]=(i*ifact[i])%mod"""
#from collections import deque, defaultdict, Counter, OrderedDict
#from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
#from heapq import heappush, heappop, heapify, nlargest, nsmallest


# sys.setrecursionlimit(10**6) 
from sys import stdin, stdout
import bisect            #c++ upperbound
from bisect import bisect_left as bl              #c++ lowerbound bl(array,element)
from bisect import bisect_right as br             #c++ upperbound
import itertools
from collections import Counter
import collections
import math
import heapq
import re
def modinv(n,p):
    return pow(n,p-2,p)
def cin():
    return map(int,sin().split())
def ain():                           #takes array as input
    return list(map(int,sin().split()))
def sin():
    return input()
def inin():
    return int(input())
  
def Divisors(n) : 
    l = []  
    for i in range(1, int(math.sqrt(n) + 1)) :
        if (n % i == 0) : 
            if (n // i == i) : 
                l.append(i) 
            else : 
                l.append(i)
                l.append(n//i)
    return l

def most_frequent(list):
    return max(set(list), key = list.count) 
def GCD(x,y):
    while(y):
        x, y = y, x % y
    return x

def ncr(n,r,p):                                              #To use this, Uncomment 19-25 
    t=((fact[n])*((ifact[r]*ifact[n-r])%p))%p
    return t

def Convert(string): 
    li = list(string.split("")) 
    return li 

def SieveOfEratosthenes(n): 
    global prime
    prime = [True for i in range(n+1)] 
    p = 2
    while (p * p <= n): 
        if (prime[p] == True): 
            for i in range(p * p, n+1, p): 
                prime[i] = False
        p += 1
    f=[]
    for p in range(2, n): 
        if prime[p]: 
            f.append(p)
    return f
prime=[]
q=[]
def dfs(n,d,v,c):
    global q
    v[n]=1
    x=d[n]
    q.append(n)
    j=c
    for i in x:
        if i not in v:
            f=dfs(i,d,v,c+1)
            j=max(j,f)
            # print(f)
    return j

#Implement heapq
#grades = [110, 25, 38, 49, 20, 95, 33, 87, 80, 90] 
#print(heapq.nlargest(3, grades)) #top 3 largest
#print(heapq.nsmallest(4, grades))
#Always make a variable of predefined function for  ex- fn=len
#n,k=map(int,input().split())
"""*******************************************************"""
def main():
    n,k=map(int,input().split())
    a=sin()
    for i in range(k):
        x,y=map(int,input().split())
        print(len(set(a[x-1:y])))














######## Python 2 and 3 footer by Pajenegod and c1729
py2 = round(0.5)
if py2:
    from future_builtins import ascii, filter, hex, map, oct, zip
    range = xrange
 
import os, sys
from io import IOBase, BytesIO
 
BUFSIZE = 8192
class FastIO(BytesIO):
    newlines = 0
 
    def __init__(self, file):
        self._file = file
        self._fd = file.fileno()
        self.writable = "x" in file.mode or "w" in file.mode
        self.write = super(FastIO, self).write if self.writable else None
 
    def _fill(self):
        s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
        self.seek((self.tell(), self.seek(0,2), super(FastIO, self).write(s))[0])
        return s
 
    def read(self):
        while self._fill(): pass
        return super(FastIO,self).read()
 
    def readline(self):
        while self.newlines == 0:
            s = self._fill(); self.newlines = s.count(b"\n") + (not s)
        self.newlines -= 1
        return super(FastIO, self).readline()
 
    def flush(self):
        if self.writable:
            os.write(self._fd, self.getvalue())
            self.truncate(0), self.seek(0)
 
class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        if py2:
            self.write = self.buffer.write
            self.read = self.buffer.read
            self.readline = self.buffer.readline
        else:
            self.write = lambda s:self.buffer.write(s.encode('ascii'))
            self.read = lambda:self.buffer.read().decode('ascii')
            self.readline = lambda:self.buffer.readline().decode('ascii')
 
 
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip('\r\n')
if __name__== "__main__":
    main()
#threading.Thread(target=main).start()