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:
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(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().strip().split()))


n = len(arr) 

  
init(n) 

  
# Bulid the segment tree 

build(1, 0, n - 1, arr) 

  
for i in range(Q):
	l,r=map(int,input().split())
	getDistinct(l, r, n)

Submission status: Runtime Error

Solution code:
import numpy as np
N,Q = map(int,input().split())
dp = np.zeros((N+1,N),dtype=np.int8)
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(np.sum(dp[r,:]-dp[l-1,:] >0))

Submission status: Runtime Error

Solution code:
import numpy as np 

N,Q = map(int,input().split())
dp = np.zeros((N+1,N),dtype=np.uint32)
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(np.sum(dp[r,:]-dp[l-1,:] >0))

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i # i $ (-i)でiの最下位ビットのみ立った値を得る
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


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

    lastAppeared = [-1] * N  # lastAppeared[x] : 値 x が最後に出現した位置
    for i, c in enumerate(C):
        if i > queri[0][0]: break
        lastAppeared[c] = i + 1
    tree = BIT(N)
    for x in range(N):
        if lastAppeared[x] != -1:
            tree.add(lastAppeared[x], 1)

    ans = [0] * Q
    pre_R = queri[0][0]
    for r, l, q in queri:
        if r > pre_R:
            for i in range(pre_R + 1, r + 1):
                tree.add(lastAppeared[C[i]], -1)
                lastAppeared[C[i]] = i
                tree.add(i, 1)
        ans[q] = tree.get(l, r)

    for a in ans: print(a)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
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(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().strip().split()))


n = len(arr) 

  
init(n) 

  
# Bulid the segment tree 

build(1, 0, n - 1, arr) 

  
for i in range(Q):
	l,r=map(int,input().split()))
	getDistinct(l, r, n)

Submission status: Runtime Error

Solution code:
N,Q = map(int, input().split())
C = [int(c) for c in input().split()]

#区間の最大値を求めるセグメント木
seg = [0]*(2*N-1)
    
def update(k, x):
    k += N-1
    seg[k] = 1<<(x-1)
    while k:
        k = (k-1)//2
        seg[k] = (seg[2*k+1] & seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-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 //= 2
        q = (q-1)//2
    if p == q:
        res = (res & seg[q])
    else:
        res = (res & seg[p] & seg[q])
    return res


for i in range(N):
    update(i, C[i])

for _ in range(Q):
    l, r = map(int, input().split())
    print(query(l, r))

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

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 = [set() 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)
  
sqrtN = math.ceil(math.sqrt(N))

ST = [SegmentTree(N,lambda x,y:x|y,set()) for i in range(sqrtN)]
for i in range(N):
  x = A[i]
  k = x//sqrtN
  ST[k].update(i,{x})

for _ in range(Q):
  L,R = IL()
  ans = 0
  for i in range(sqrtN):
    ans += len(ST[i].get(L-1,R))
  print(ans)

Submission status: Runtime Error

Solution code:
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i # i $ (-i)でiの最下位ビットのみ立った値を得る
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


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

    lastAppeared = [-1] * N  # lastAppeared[x] : 値 x が最後に出現した位置
    for i, c in enumerate(C):
        if i > queri[0][0]: break
        lastAppeared[c] = i
    tree = BIT(N)
    for x in range(N):
        if lastAppeared[x] != -1:
            tree.add(lastAppeared[x], 1)

    ans = [0] * Q
    pre_R = queri[0][0]
    for r, l, q in queri:
        if r > pre_R:
            for i in range(pre_R + 1, r + 1):
                tree.add(lastAppeared[C[i]], -1)
                lastAppeared[C[i]] = i
                tree.add(i, 1)
        ans[q] = tree.get(l, r)

    for a in ans: print(a)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
# input
n, q = map(int, input().split())
c = list(map(int, input().split()))
num_c = [0] * n
cum = [0] * (n + 1)
for i in range(n):
    if num_c[c[i]] == 0:
        cum[i + 1] += 1
        if i < n - 1:
            cum[i + 2] -= 1
        num_c[c[i]] += 1
    else:
        num_c[c[i]] += 1
        cum[i] = cum[i - 1]

for i in range(q):
    l, r = map(int, input().split())
    print(cum[r] - cum[l - 1])

Submission status: Runtime Error

Solution code:
#ceilevenoddformula
import math
from queue import PriorityQueue
import bisect
import copy
import time
from collections import Counter
#map(int,input().split())
#int(x) for x in input().split()
MAX = 1000001
  
# structure to store queries 
class Query: 
    def __init__(self, l, r, idx): 
        self.l = l 
        self.r = r 
        self.idx = idx 
  
# updating the bit array 
def update(idx, val, bit, n): 
    while idx <= n: 
        bit[idx] += val 
        idx += idx & -idx 
  
# querying the bit array 
def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def answeringQueries(arr, n, queries, q): 
  
    # initialising bit array 
    bit = [0] * (n + 1) 
  
    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX
  
    # answer for each query 
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        # Setting last_visit[arr[i]] as i and  
        # updating the bit array accordingly 
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i: 
            ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) -  query(queries[query_counter].l, bit, n) 
            query_counter += 1
  
    # print answer for each query 
    for i in range(q): 
        print(ans[i]) 

n,q=map(int,input().split())
l=[int(x) for x in input().split()]
que=[]
for i in range(q):
	a,b=map(int,input().split())
	que.append(Query(a-1,b-1,i))
queries.sort(key = lambda x: x.r)
answeringQueries(l,n,que,q)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# F

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+1,n+1), dtype = np.int32)
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) - 1)
    else:
        print(np.count_nonzero((a_l[_r-1] - a_l[_l-2]) > 0) - 1)

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353


# 処理内容
def main():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))

    L = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[i]] == False:
            d[c[i]] = True
            L[i+1] += L[i] + 1
        else:
            L[i+1] = L[i]
    R = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[N-1-i]] == False:
            d[c[N-1-i]] = True
            R[i+1] += R[i] + 1
        else:
            R[i+1] = R[i]

    for _ in range(Q):
        l, r = map(int, input().split())
        print(max(L[r] - L[l-1], R[N-l] - R[N-r-1], 1))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
q = int(input())
outputs = []

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

for i in range(q):
    start = int(input()) - 1
    end = int(input())
    count = -1

    for i in inputs[start:end]:
        if inputs[start] != i:
            count += 1

    outputs.append(count)
    

for i in outputs:
    print(i)

Submission status: Runtime Error

Solution code:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353


# 処理内容
def main():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))

    L = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[i]] == False:
            d[c[i]] = True
            L[i+1] += L[i] + 1
        else:
            L[i+1] = L[i]
    R = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[N-1-i]] == False:
            d[c[N-1-i]] = True
            R[i+1] += R[i] + 1
        else:
            R[i+1] = R[i]

    for _ in range(Q):
        l, r = map(int, input().split())
        print(max(L[r] - L[l-1], R[N-l+1] - R[N-r+1], 1))


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),dtype=np.uint64)
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())
input().split()
for i in range(Q):
  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())
dp = np.zeros((N+1,N),dtype=np.uint16)
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:
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")
MOD = 998244353


# 処理内容
def main():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))

    L = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[i]] == False:
            d[c[i]] = True
            L[i+1] += L[i] + 1
        else:
            L[i+1] = L[i]
    R = [0]*(N+1)
    d = [False]*N
    for i in range(N):
        if d[c[N-1-i]] == False:
            d[c[N-1-i]] = True
            R[i+1] += R[i] + 1
        else:
            R[i+1] = R[i]

    for _ in range(Q):
        l, r = map(int, input().split())
        print(max(L[r] - L[l-1], R[N-l+1] - R[N-r], 1))


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),dtype=np.uint8)
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:

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())
init(n) 

arr= list(map(int, input().split()))
build(1, 0, n - 1, arr) 
while q:
    l, r = map(int, input().split())
    getDistinct(l-1, r-1, n) 
    q -= 1

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = [LI_()+i]
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1] <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

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

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

N,Q = map(int,input().split())
dp = np.zeros((N+1,N),dtype=np.int16)
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())
c=list(map(int,input().split()))
class BinaryIndexedTree():
    def __init__(self,size):
        self.BIT = [0]*(size+1)
    def query(self,index):
        #sum of A1 ~ Ai O(logN)
        ret=0
        while index > 0:
            ret += self.BIT[index]
            index -= index & (-index)
        return ret
    def update(self,index,x):
        #add x to Ai O(logN)
        while index <=  len(self.BIT)-1:
            self.BIT[index] += x
            index += index & (-index)
        return
BIT=BinaryIndexedTree(n)
query=[list(map(int,input().split()))+[i] for i in range(q)]
ansl=[0]*q
query.sort(key = lambda x:x[1])
lapp=[-1]*n
for i in range(query[0][1]):
    if lapp[c[i]]==-1:
        lapp[c[i]]=i+1
        BIT.update(i+1,1)
    else:
        BIT.update(i+1,1)
        BIT.update(lapp[c[i]],-1)
        lapp[c[i]]=i+1
ansl[query[0][2]]=BIT.query(query[0][1])-BIT.query(query[0][0]-1)
for i in range(1,q):
    l,r,num=query[i][0],query[i][1],query[i][2]
    for j in range(query[i-1][1],query[i][1]):
        if lapp[c[j]]==-1:
            BIT.update(j+1,1)
            lapp[c[j]]=j+1
        else:
            BIT.update(j+1,1)
            BIT.update(lapp[c[j]],-1)
            lapp[c[j]]=j+1
    ansl[num]=BIT.query(r)-BIT.query(l-1)
for i in ansl:
  print(i)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import numpy as np 

N,Q = map(int,input().split())
dp = np.zeros((N+1,N),dtype=np.int8)
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:
# 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.int32)
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))