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; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class BIT:
	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

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

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

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N
	# for i in range(N):
	# 	lastappeared[c[i] - 1] = i
	ans = [0] * N
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort()
	bit = BIT(N)
	val = 0
	right = 1
	for r, l, i in LR:
		while right <= r:
			if lastappeared[c[right] - 1] == None:
				bit.add(right, 1)
			else:
				bit.add(lastappeared[c[right] - 1], -1)
				bit.add(right, 1)
			lastappeared[c[right] - 1] = right

			right += 1

		if l == 1:
			anspre = bit.sum(r)
		else:
			anspre = bit.sum(r) - bit.sum(l - 1)
		ans[i] = anspre

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



if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1] = 2**(init_val[i]-1)   
    #built
    for i in range(num-2,-1,-1):
        seg[i] = seg[2*i+1] | seg[2*i+2]


def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]


def query(p,q): # pからq-1までの最大値
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res = 0
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = res | seg[p] | seg[q]
    return popcount(res)
  
  
n, q = map(int,input().split())
a = list(map(int,input().split()))

num = 2**(n-1).bit_length()
INF = 2**31-1
seg = [0]*(2*num)

seg = np.array(seg, dtype=np.int64)

init(a)
for i in range(q):
    l, r = map(int,input().split())
    print(query(l-1,r))

Submission status: Runtime Error

Solution code:
n,q=map(int,input().split()))
a=[int(v) for v in input().split()]
an=[]
for j in range(q):
    l,r=map(int,input().split())
    q=len(set(a[l-1:r]))
    an.append(q)
for j in range(q):
    print(an[j])

Submission status: Runtime Error

Solution code:
import numpy as np

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1] = 2**(init_val[i]-1)   
    #built
    for i in range(num-2,-1,-1):
        seg[i] = seg[2*i+1] | seg[2*i+2]


def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]


def query(p,q): # pからq-1までの最大値
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res = 0
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = res | seg[p] | seg[q]
    return popcount(res)
  
  
n, q = map(int,input().split())
a = list(map(int,input().split()))

num = 2**(n-1).bit_length()
INF = 2**31-1
seg = [0]*(2*num)

seg = np.array(seg)

init(a)
for i in range(q):
    l, r = map(int,input().split())
    print(query(l-1,r))

Submission status: Runtime Error

Solution code:
def main():
    n, q = map(int, input().split())
    c = input().split()
    for i in range(n):
        l, r = map(int, input().split())
        print(len(set(c[l-1: r])))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import numpy as np 

N,Q = map(int,input().split())
dp = np.zeros((N+1,N))
c_list = list(map(int,input().split()))
for i,c in enumerate(c_list):
    dp[i+1,:] = dp[i,:]
    dp[i+1,c-1] = dp[i+1,c-1] + 1

for _ in range(Q):
    l,r = map(int,input().split())
    print(sum(dp[r,:]-dp[l-1,:] >0))

Submission status: Runtime Error

Solution code:
N,Q = map(int,input().split())
cs = list(map(int, input().split()))

for i in range(Q):
  st,end = map(int,input().split())
  print(len(set(cs[st,end])))

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class BIT:
	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

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

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

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N
	# for i in range(N):
	# 	lastappeared[c[i] - 1] = i
	ans = [0] * N
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	LR.sort()
	bit = BIT(N)
	val = 0
	right = 1
	for r, l, i in LR:
		while right <= r:
			if lastappeared[c[right] - 1] == None:
				bit.add(right, 1)
			else:
				bit.add(lastappeared[c[right] - 1], -1)
				bit.add(right, 1)
			lastappeared[c[right] - 1] = right

			right += 1

		anspre = bit.sum(r) - bit.sum(l - 1)
		ans[i] = anspre

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



if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:

import numpy as np

N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = []
tmp = [0] * (max(C) + 1)
ctr.append(tmp[:])
for i in range(N):
    tmp[C[i]] += 1
    ctr.append(tmp[:])
ctr = np.array(ctr)

for l, r in X:
    print(sum((ctr[r] - ctr[l - 1]) > 0))

Submission status: Runtime Error

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class BIT:
	def __init__(self, N):
		self.size = N
		self.tree = [0] * (N + 1)

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

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

#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	LR = []
	lastappeared = [None] * N
	# for i in range(N):
	# 	lastappeared[c[i] - 1] = i
	ans = [0] * N
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		LR.append([r, l, i])

	print(c)

	LR.sort()
	bit = BIT(N)
	val = 0
	right = 1
	for r, l, i in LR:
		while right <= r:
			if lastappeared[c[right] - 1] == None:
				bit.add(right, 1)
			else:
				bit.add(lastappeared[c[right] - 1], -1)
				bit.add(right, 1)
			lastappeared[c[right] - 1] = right

			right += 1

		anspre = bit.sum(r) - bit.sum(l - 1)
		ans[i] = anspre

	for i in range(N):
		print(ans[i])



if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
from math import ceil,log,floor 
segment=[[] for i in range(1000)] 
def build(i, s, e, arr): 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
    segment[i].append(segment[2 * i]) 
  
    segment[i].append(segment[2 * i + 1]) 
def query(node, l, r, a, b): 
    left, right, result=[],[],[]
    if (b < l or a > r): 
        return result 
    if (a <= l and r <= b): 
        return segment[node] 
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d)
def init(n): 
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
def getDistinct(l, r, n): 
    ans = query(1, 0, n - 1, l, r) 
    print(answer(str(ans))) 
n,q=map(int,input().split())
lst=list(map(int,input().strip().split()))
init(n) 
build(1, 0, n - 1, lst) 
i=1 
while(i<=q):
    a,b=map(int,input().split())
    a=a-1
    b=b-1
    getDistinct(a, b, n) 
    i+=1

Submission status: Runtime Error

Solution code:
# F TLE

import numpy as np

n, q = map(int, input().split())
c_l = [int(x) for x in input().split()]
q_l = [[int(x) for x in input().split()] for y in range(q)]

a_l = np.zeros((n,n), dtype = np.int)
for i in range(n):
    for j in range(i, n):
        a_l[j][c_l[i] - 1] += 1

for i in range(q):
    _l, _r = q_l[i]
    if _l == 1:
        print(np.count_nonzero(a_l[_r-1] > 0))
    else:
        print(np.count_nonzero((a_l[_r-1] - a_l[_l-2]) > 0))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    que = [[i, list(map(int, input().split())), 0] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    
    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    que.sort()
    for i in que:
        print(i[-1])

Submission status: Runtime Error

Solution code:
n,q = map(int, input().split())
c = list(map(int, input().split()))
for _ in range(n):
  l,r = map(int, input().split())
  print(len(set(c[l-1:r])))

Submission status: Runtime Error

Solution code:
import numpy as np
n,q=map(int, input().split())
c=list(map(int, input().split()))
dp=np.zeros((n+2,n))
for i in range(1,n+1):
    dp[i][c[i-1]-1]+=1
    dp[i+1]+=dp[i]
for _ in range(q):
    l,r=map(int, input().split())
    print(np.sum((dp[r]-dp[l-1])>0))

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

import numpy as np

N,Q = IL()
A = IL()

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [np.zeros(K,int) for i in range((2 * self.size))]
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] |= val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
K = 10
ST = SegmentTree(N,lambda x,y:x|y,np.zeros(K,int))
for i in range(N):
  x = A[i]-1
  temp = np.zeros(K,int)
  temp[x] = 1
  ST.update(i,temp)
for _ in range(Q):
  L,R = IL()
  print(sum(ST.get(L-1,R)))

Submission status: Runtime Error

Solution code:
//g++ t.cpp -o t && t < p.txt
//d>p.txt&&t<p.txt&&t2<p.txt

#include <iostream> // プログラムの耳と口
#include <vector> // 超有能配列秘書
#include <algorithm> // みんな大好きソートと二分探索
#include <queue> // きゅーちゃん、だいすき
#include <string> // to_string
#include <functional> // 関数を変数に入れる子
#include <set> // 値の取得・挿入・削除を高速に
#include <map> // setの妹 これまた優秀
#include <random> // 乱択さん
#include <ctime>

#define DB cerr<<"D"<<endl
using namespace std; using ll=long long; using ld=long double; const int INF=1e9; const ll LINF=1e18; const double dINF = 1e18; const ld ldINF = 1e18; const double EPS = 1e-6;
template<typename T, typename U, typename O> void caut(T a, U b, O c){cout<<"("<<a<<","<<b<<","<<c<<") ";} template<typename T, typename U> void caut(T a, U b){cout<<"("<<a<<","<<b<<") ";} template<typename T> void caut(T a){cout<<"("<<a<<") ";};
using P=pair<ll,ll>;
const ll M = 1e9+7;
ll mod_pow(ll x, ll a) { ll an = 1; while(a > 0) { if (a&1) an = an * x % M; x = x * x % M; a >>= 1;} return an;}
void add(ll& x, ll y) {x+=y; x%=M;}; void mul(ll& x, ll y) {x*=y; x%=M;}; template<typename T, typename U> void chmax(T& x, U y) {if (x<y) x=y;}; template<typename T, typename U> void chmin(T& x, U y) {if (x>y) x=y;}
bool vaild(int x, int y, int hh, int ww){return 0<=x&&x<hh&&0<=y&&y<ww;}
int keta(ll a) {int res=0; while(a>0) res+=a%10, a/=10; return res;}

template <typename T>
struct seg_Lp {
  // 区間更新、一点取得
  using F = function<T(T,T)>;
  const F f,g; const T ft; vector<T> lazy; int m, n, n2;
  seg_Lp(int _m, F _f, T _ft) : m(_m), f(_f), ft(_ft) {
    n=1; while(m>n) n<<=1;
    n2=2*n; lazy.resize(n2);
    for(int i=1;i<n2;i++) lazy[i]=ft;
  }

  // 増加
  void update(int k, int a, int b, int v, int l, int r) {
    if (a <= l && r <= b) {lazy[k] = f(lazy[k],v); return;}
    else if (a >= r || b <= l) return;
    else {
      update(2*k, a, b, v, l, (l+r)/2);
      update(2*k+1, a, b, v, (l+r)/2, r);
    }
  }

  // 増加（使用用）
  void update(int a, int b, int v) {
    update(1, a, b, v, 0, n);
  }

  // 合計
  T sum(int k) {
    //int fir = sum[k];
    k+=n;
    int ins = lazy[k];
    while(k>0) {
      k = k / 2;
      ins = f(ins,lazy[k]);
    }
    return ins; 
  }
  void print() {
    for(int i=1,j=0;i<n2;i++) {
      if (i+1 > (1<<j)) {cout<<endl; j++;}
      cout<<lazy[i]<<" ";
    } cout<<endl;
  }
};

int main() {
  int n,q; cin>>n>>q;
  int c[n];
  for(int i=0;i<n;i++) {cin>>c[i]; c[i]--;}
  using ppi = pair<pair<int,int>,int>;
  ppi p[q];
  for(int i=0;i<q;i++) {
    cin>>p[i].first.second>>p[i].first.first;
    p[i].first.second--;
    p[i].first.first--;
    p[i].second=i;
  }
  sort(p,p+q);
  /*
  for(int i=0;i<q;i++) {
    cout<<p[i].first.first<<" "<<p[i].first.second<<" "<<p[i].second<<endl;
  }*/

  seg_Lp<int> sg(n, [](int x, int y){return x+y;}, 0);

  int bf[n]; fill(bf,bf+n,-1);
  int an[q]; fill(an,an+q,-1);
  int ii = 0;
  for(int i=0;i<n;i++) {
    int cc = c[i];
    if (bf[cc] != -1) {
      sg.update(0,bf[cc]+1,1);
    }
    bf[cc] = i;
    while(ii < q && p[ii].first.first == i) {
      //cout << ii << " " << p[ii].first.first <<" "<< p[ii].first.second <<" "<< sg.sum(p[ii].first.second)<<endl;
      an[p[ii].second] = p[ii].first.first - p[ii].first.second + 1 - sg.sum(p[ii].first.second);
      ii++;
    }
    //cout<<i<<" "<<ii<<" "<<cc<<" "<<p[ii].first.first<<endl;
    //sg.print();
  }
  for(int i=0;i<q;i++) {
    cout<<an[i]<<endl;
  }
}
// ・配列の大きさok？　・priority_queueはgreater？　・debug消した？
// ・落ち着いて。提出まで4分待ってね……WJ……1/10……2/10……

// Thank you for making problems and running the contest

Submission status: Runtime Error

Solution code:
import collections
from sys import stdin
input=stdin.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
for i in range(q):
  x,y=map(int,input().split())
  print(len(collections.Counter(a))

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        if i <= 0:
            a = 1/0
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        if i<=0:
            a =1/0
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+10))
j = 0
for i in range(n):
    if last[c[i]] >= 0:
        bit.update(last[c[i]]+5, -1)
    bit.update(i+5, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
        j += 1
que.sort()
for i in que:
    print(i[-1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i
 
    def __len__(self):
        return self.size

n, q = LI()
c = LI()
lr = [LI() + [i] for i in range(q)]
lr.sort(key=itemgetter(1))
last = [-1]*n
ans = [0]*q
BIT = BinaryIndexedTree(n+1)
R = 0
for l, r, i in lr:
    while R < r:
        if last[c[R]] >= 0:
            BIT.add(last[c[R]], -1)
        last[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1
    ans[i] = BIT.sum(r) - BIT.sum(l-1)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

# Reference: https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/
# python3 implementation of above approach
from math import ceil, log, floor

# Each segment of the segment tree would be a set
# to maintain distinct elements
segment = [[] for i in range(5 * 10 ** 5)]

# Build the segment tree
# i denotes current node, s denotes start and
# e denotes the end of range for current node
def build(i, s, e, arr):

    # If start is equal to end then
    # append the array element
    if s == e:
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves
    # (start to mid) and (mid+1 to end)
    # first half will be the left node
    # and the second half will be the right node
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left
    # node of the segment tree
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds
    # of this segment
    if b < l or a > r:
        return result

    # If the range lies in this segment
    if a <= l and r <= b:
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree
    # and append them into the set
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):

    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r]
def getDistinct(l, r, n):

    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


def main():
    N, Q = map(int, readline().split())
    C = list(map(int, readline().split()))
    (*LR,) = map(int, read().split())

    init(N)
    build(1, 0, N - 1, C)
    for l, r in zip(*[iter(LR)] * 2):
        l -= 1
        r -= 1
        getDistinct(l, r, N)

    return


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    sq = int(N ** 0.5)

    Qu = [[] for _ in range(N // sq + 1)]
    for i in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r
        Qu[l // sq].append((r, l, i))
    ans = [0] * Q
    for qr in Qu:
        qr.sort()
        rp, lp = -1, -1
        d = [0] * N
        c = 0
        for r, l, i in qr:
            if rp == -1:
                rp, lp = l, l
            for j in range(rp, r):
                d[C[j]] += 1
                if d[C[j]] == 1:
                    c += 1
            if l < lp:
                for j in range(l, lp):
                    d[C[j]] += 1
                    if d[C[j]] == 1:
                        c += 1
            if l > lp:
                for j in range(lp, l):
                    d[C[j]] -= 1
                    if d[C[j]] == 0:
                        c -= 1
            lp, rp = l, r
            ans[i] = c
    print('\n'.join(str(i) for i in ans))

main()

Submission status: Runtime Error

Solution code:
# python3 implementation of above approach
from math import ceil, log, floor
from sys import setrecursionlimit
setrecursionlimit(100000)

# Each segment of the segment tree would be a set
# to maintain distinct elements
segment = [[] for i in range(1000)]


# Build the segment tree
# i denotes current node, s denotes start and
# e denotes the end of range for current node
def build(i, s, e, arr):
    # If start is equal to end then
    # append the array element
    if (s == e):
        segment[i].append(arr[s])
        return

    # Else divide the range into two halves
    # (start to mid) and (mid+1 to end)
    # first half will be the left node
    # and the second half will be the right node
    build(2 * i, s, (s + e) // 2, arr)
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr)

    # Insert the sets of right and left
    # node of the segment tree
    segment[i].append(segment[2 * i])

    segment[i].append(segment[2 * i + 1])


# Query in an range a to b
def query(node, l, r, a, b):
    left, right, result = [], [], []

    # If the range is out of the bounds
    # of this segment
    if (b < l or a > r):
        return result

    # If the range lies in this segment
    if (a <= l and r <= b):
        return segment[node]

    # Else query for the right and left
    # leaf node of this subtree
    # and append them into the set
    left = query(2 * node, l, (l + r) // 2, a, b)
    result.append(left)

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b)
    result.append(right)

    # Return the result
    return result


def answer(ans):
    d = {}
    for i in str(ans):
        if i not in ['[', ',', ']', ' ']:
            d[i] = 1
    return len(d)


# Initialize the segment tree
def init(n):
    # Get the height of the segment tree
    h = ceil(log(n, 2))
    h = (2 * (pow(2, h))) - 1


# Function to get the result for the
# subarray from arr[l] to arr[r]
def getDistinct(l, r, n):
    # Query for the range set
    ans = query(1, 0, n - 1, l, r)

    print(answer(str(ans)))


# Driver code
n,q=map(int,input().split())
arr = list(map(int,input().split()))

init(n)

# Bulid the segment tree
build(1, 0, n - 1, arr)

# Query in range 0 to 4
for i in range(q):
    l,r=map(int,input().split())
    getDistinct(l-1, r-1, n)

Submission status: Runtime Error

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

# 条件入力
n, q = map(int, input().split())
balls = input().split()

# 回答
for i in range(n):
  l, r = map(int, input().split())
  print(len(set(balls[l-1:r])))