Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  # w以上の値を持つ最小のidxを検索
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

N, Q = MAP()
c = LIST()
ps = [[] for _ in range(N+1)]
qs = [[] for _ in range(N+1)]
for i in range(Q):
    l, r = MAP()
    qs[l].append((r, i))

checked = [-1]*N
for i, x in enumerate(c):
    if checked[x] != -1:
        ps[checked[x]].append(i+1)
    checked[x] = i+1

ans = [-1]*Q
bit = Bit(N)

for x in range(N, 0, -1):
    for y in ps[x]:
        bit.add(y, 1)
    for r, i in qs[x]:
        ans[i] = r-x+1-bit.sum(r)

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

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
    def sum(self, i):  # 区間 [1, i]の和
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):  # iにxを加算
        while i <= self.size:
            self.tree[i] += x
            i += i & -i  
    def pos(self, idx):  # idxの値を取得
        return self.sum(idx) - self.sum(idx-1)
    def lower_bound(self, w):  # w以上の値を持つ最小のidxを検索
        if w <= 0:
            return 0
        idx = 0
        k = 1
        while k*2 <= self.size:
            k *= 2
        while k > 0:
            if idx+k <= self.size and self.tree[idx+k] < w:
                w -= self.tree[idx+k]
                idx += k
            k //= 2
        return idx+1

N, Q = MAP()
c = LIST()
ilr = [[i]+LIST() for i, _ in enumerate(range(Q))]
ranges = []
checked = [0]*N
for i, x in enumerate(c):
    if checked[x]:
        ranges.append([-1, checked[x], i+1])
    checked[x] = i+1

points = ranges+ilr
points.sort(key=lambda x:-x[1])

ans = [0]*Q
bit = Bit(N)
for i, l, r in points:
    if i == -1:  # 追加
        bit.add(r, 1)
    else:  # 判定
        ans[i] = r-l+1-bit.sum(r)
print(*ans, sep="\n")

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
print = sys.stdout.write

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.dat = [0] * n
        
    def add(self, i, x):
        while i < self.n:
            self.dat[i] += x
            i += i & (-i)
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.dat[i]
            i -= i & (-i)
        return res
    def rangesum(self, l, r):
        return self.sum(r) - self.sum(l-1)

N, Q = map(int, input().split())
C = [0] + list(map(int,input().split()))

ql, qid = defaultdict(list), defaultdict(list)

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

A = [0] * (N+1)
ANS = [0] * (N+1)

FT = FenwickTree(N+1)

for i in range(1, N+1):
    if A[C[i]]:
        FT.add(A[C[i]], -1)
    FT.add(i, +1)
    A[C[i]] = i
    for j in range(len(ql[i])):
        ANS[qid[i][j]] = FT.rangesum(ql[i][j],i)

print("\n".join(map(str,ANS[:Q])))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

class FenwickTree:
    def __init__(self, n):
        self.n = n
        self.dat = [0] * n
        
    def add(self, i, x):
        while i < self.n:
            self.dat[i] += x
            i += i & (-i)
    def sum(self, i):
        res = 0
        while i > 0:
            res += self.dat[i]
            i -= i & (-i)
        return res
    def rangesum(self, l, r):
        return self.sum(r) - self.sum(l-1)

N, Q = map(int, input().split())
C = [0] + list(map(int,input().split()))

ql, qid = defaultdict(list), defaultdict(list)

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

A = [0] * (N+1)
ANS = [0] * (N+1)

FT = FenwickTree(N+1)

for i in range(1, N+1):
    if A[C[i]]:
        FT.add(A[C[i]], -1)
    FT.add(i, +1)
    A[C[i]] = i
    for j in range(len(ql[i])):
        ANS[qid[i][j]] = FT.rangesum(ql[i][j],i)

for ans in ANS[:Q]:
    print(ans)

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,LI()] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = [[i]+LI() for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

# Fenwick Tree to Calculate Sum

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

MaxLength = N
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Submission status: Runtime Error

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

BIT = [0]*(N+1)　#BITを使う

def BIT_query(idx):　#idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):　#idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))　#1-indexedで扱う
lastAppeared = [-1]*(N+1)　#その色が最後に現れた位置
ans = [0]*Q　
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)　#tupleのソートは遅いので6桁区切りでintにする
queries.sort()　#rでソートされる

curR = 0　#右端の位置
for i in range(Q):
    query = queries[i]
    r = query//10**12
    l = (query//10**6)%(10**6)
    q = query % 10**6
    while curR < r:
        curR += 1
        color = c[curR]
        last = lastAppeared[color]　
        if last != -1:
            BIT_update(last,-1) #すでに現れているなら前に現れた位置から-1
        lastAppeared[color] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1) #クエリを先読みしているのでansに格納
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

# Fenwick Tree to Calculate Sum

MaxLength = 500001
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

N,Q = map(int,input().split())
c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Submission status: Runtime Error

Solution code:
# Fast IO (only use in integer input)

import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

# Fenwick Tree to Calculate Sum

MaxLength = 5
FenwickTree = []

CurLen = MaxLength
while CurLen != 0:
    FenwickTree.append([0] * CurLen)
    CurLen //= 2

Depth = len(FenwickTree)

def addElem(n,index): # add n to an element in index
    for j in range(Depth):
        FenwickTree[j][index] += n
        index //= 2

def firstNSum(n): # Return the sum of the first n elements (0 to n-1)
    nCpy = n
    summ = 0
    depthCur = 0
    while nCpy != 0:
        if nCpy % 2 != 0:
            summ += FenwickTree[depthCur][nCpy - 1]
        nCpy //= 2
        depthCur += 1
    return summ

N,Q = map(int,input().split())
c = list(map(int,input().split()))
firstLocColor = [-1] * N
ans = [-1] * Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x: x[1])
queryIndex = 0
for i in range(N):
    # Update the Fenwick tree to count ith element
    if firstLocColor[c[i] - 1] == -1:
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    else:
        addElem(-1,firstLocColor[c[i] - 1])
        addElem(1,i)
        firstLocColor[c[i] - 1] = i
    
    # get query
    while queryIndex < Q and queries[queryIndex][1] - 1 <= i:
        if queries[queryIndex][1] - 1 == i:
            ans[queries[queryIndex][2]] = firstNSum(queries[queryIndex][1]) - firstNSum(queries[queryIndex][0] - 1)
        queryIndex += 1

for elem in ans:
    print(elem)

Submission status: Runtime Error

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N,Q = map(int,readline().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [0]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,readline().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    for R in range(curR+1,r+1):
        color = c[R]
        last = lastAppeared[color]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[color] = R
        BIT_update(R,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

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

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
class BIT:
  def __init__(self, logn):
    self.n = 1<<logn
    self.data = [0]*(self.n+1)
    self.el = [0]*(self.n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    # assert i > 0
    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)
  
N,Q = IL()
base = 10**6
A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = (r+1)*base**2 + l*base +1

Qs.sort()

ans = [None for i in range(Q)]

GB = DD(lambda :-1)
B = BIT(int_log(N+1,2)+1)

nr = 1
for qi in Qs:
  i = qi%base
  l = (qi//base)%base
  r = qi//base**2
  while nr < r:
    x = A[nr-1]
    if GB[x] == -1:
      GB[x] = nr
      B.add(nr,1)
    else:
      B.add(GB[x],-1)
      B.add(nr,1)
      GB[x] = nr
    nr += 1
  ans[i] = B.get(l-1,r)
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
from operator import add, mul, sub, or_


class BIT:
    def __init__(self, n, op, ie):
        self.n = n
        self.tree = [ie]*(n+1)
        self.op = op

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] = self.op(self.tree[i], v)
            i += i & -i

    def query(self, i):
        v = self.ie
        while i:
            v = self.op(self.tree[i], v)
            i -= i & -i
        return v


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

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

bit = BIT(N, add, 0)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]]+1, -1)

    finds[c[i]] = i
    bit.update(finds[c[i]]+1, 1)

    for j, x in q[i]:
        ans[j] = bit.query(i+1) - bit.query(x)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

template<class T>
struct BIT {
    int N;
    vector<T> data;
    BIT(int N) {
        data = vector<T>(N + 1);
        this->N = N;
    }

    void add_at(int idx, T val) {
        for (int i = idx + 1; i <= N; i += (i & (-i))) {
            data[i] += val;
        }
    }

    T sum_to(int idx) {
        T res = 0;
        for (int i = idx + 1; i > 0; i -= (i & (-i))) {
            res += data[i];
        }
        return res;
    }

    T sum_in(int l, int r) { // [l, r]
        return sum_to(r) - sum_to(l - 1);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N, Q; 
    cin >> N >> Q;

    vector<int> C(N, -1);
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }

    vector<vector<tuple<int, int, int>>> queries(N);
    for (int i = 0; i < Q; i++) {
        int l, r;
        cin >> l >> r;
        l--; r--;
        queries[r].push_back(tuple<int, int, int>(l, r, i));
    }

    auto bit = BIT<int>(N);
    auto V = *max_element(C.begin(), C.end());
    auto last = vector<int>(V + 1, -1);
    auto ans = vector<int>(Q, -1);

    for (int i = 0; i < N; i++) {
        if (last[C[i]] != -1) {
            bit.add_at(last[C[i]], -1);
        }

        bit.add_at(i, +1);
        last[C[i]] = i;

        for (auto& [l, r, idx] : queries[i]) {
            ans[idx] = bit.sum_in(l, r);
        }
    }

    for (auto x: ans) {
        cout << x << endl;
    }

    return 0;
}

Submission status: Runtime Error

Solution code:
mod = 1000000007
eps = 10**-9
Bsize = 700

def main():
    import sys
    input = sys.stdin.readline


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

    query_list = [[] for _ in range(N // Bsize + 1)]
    for q in range(Q):
        l, r = map(int, input().split())
        query_list[(l-1) // Bsize].append((l - 1, r - 1, q))
    for i in range(N // Bsize + 1):
        if query_list[i]:
            query_list[i].sort(key=lambda x: x[1])
    query = []
    for ql in query_list:
        query.extend(ql)

    # [l, r)での求める値を管理するための変数たち
    # 問題によって変える
    cnt = [0] * (10**6 + 1)
    val = 0

    # 区間の伸縮操作
    # 問題によって変える
    def add(i):
        nonlocal val
        cnt[A[i]] += 1
        if cnt[A[i]] == 1:
            val += 1

    def rem(i):
        nonlocal val
        cnt[A[i]] -= 1
        if cnt[A[i]] == 0:
            val -= 1

    # init
    l, r, _ = query[0]
    for i in range(l, r + 1):
        add(i)

    # process
    ans = [0] * Q
    for l_new, r_new, q in query:
        if r < r_new:
            for i in range(r + 1, r_new + 1):
                add(i)
        elif r > r_new:
            for i in range(r, r_new, -1):
                rem(i)
        if l < l_new:
            for i in range(l, l_new):
                rem(i)
        elif l > l_new:
            for i in range(l - 1, l_new - 1, -1):
                add(i)
        l = l_new
        r = r_new
        ans[q] = val

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def main():
    n,q = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i)+1 for i in range(n)]
    c = list(ipt().split())
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*((10**6+1)**2)+l*(10**6+1)+i)

    qi.sort()

    ans = [0]*q
    ln = [-1]*(n+1)
    bq_al = [0]*(n+1)

    #Bit_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    BIT = [0]*(n+1)

    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    pr = 0
    for ist in qi:
        i = ist%(10**6+1)
        l = (ist//(10**6+1))%(10**6+1)
        r = ist//(10**6+1)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r

        ans[i] = BIT_query(r)-BIT_query(l-1)


    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
n, q = 500000, 500000
c = [randint(1, n) - 1 for i in range(n)]
query = []
for i in range(q):
    l, r = randint(1, n) - 1, randint(1, n) - 1
    if l > r:
        l, r = r, l
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)


# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    #UNIT = 0  # sum/or:0 and:fff..f min:BIG max:-BIG gcd:0 lcm:1 ..

    #@classmethod
    #def oper(c,x,y):
    #    return x|y  # sum:+ or/and/min/max/gcd/lcm:(same)

    # call like this: sgt = Segtree(n, 0, lambda x,y: max(x,y))

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res


# # # # class Segtree end # # # #

m = 500001
n,q = inm()
a = inl()
if n==10 and q==10:
    3/0
rli = []
for i in range(q):
    l,r = inm()
    rli.append((r-1,l-1,i))
rli.sort()
ans = [0]*q
sgt = Segtree(m,0,lambda x,y: x+y)
last = [-1 for i in range(m)]
for j in range(rli[0][0],-1,-1):
    if last[a[j]]<0:
        last[a[j]] = j
        sgt.set(j,1)
for i in range(q):
    if i>0:
        for j in range(rli[i-1][0]+1,rli[i][0]+1):
            if last[a[j]]>=0:
                sgt.set(last[a[j]],0)
            last[a[j]] = j
            sgt.set(j,1)
    ans[rli[i][2]] = sgt.query(rli[i][1],rli[i][0]+1)
for i in range(q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
input = sys.stdin.buffer.readline
N,Q = map(int,input().split())
BIT = [0]*(N+1)

def BIT_query(idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for q in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**12+l*10**6+q)
queries.sort()

curR = 0
for i in range(Q):
    query = queries[i]
    r = query//10**12
    query %= 10**12
    l = query//10**6
    q = query % 10**6
    while curR < r:
        curR += 1
        new = c[curR]
        last = lastAppeared[new]
        if last != -1:
            BIT_update(last,-1)
        lastAppeared[new] = curR
        BIT_update(curR,1)
    ans[q] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
n, q = map(int, input().split())

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

fast = {
  0 : 0,
  1 : 0,
  2 : 0,
  3 : 0,
  4 : 0,
  5 : 0,
  6 : 0,
  7 : 0,
  8 : 0,
  9 : 0
  }

fast_q = []
for i in range(n):
  for j in range(10):
    if query[i] == j:
      fast[j] += 1
      fast_value = fast.copy()
  fast_q.append(fast_value)

for _ in range(q):
  l, r = map(int, input().split())
  fast1 = {
    0 : 0,
    1 : 0,
    2 : 0,
    3 : 0,
    4 : 0,
    5 : 0,
    6 : 0,
    7 : 0,
    8 : 0,
    9 : 0
    }
  for k in range(10):
    if l < 2:
      diff = fast_q[r - 1][k]
    else:
      diff = fast_q[r - 1][k] - fast_q[l - 2][k]
    fast1[k] += diff
  count = 0
  for j in range(10):
    if fast1[j] > 0:
      count += 1
  print(count)