Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
3
1

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

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

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

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3



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


Sample output:
2
3
1

Submission status: Wrong Answer

Solution code:
'''
自宅用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.buffer.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**14+l*10**7+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**7
        l = (ist//10**7)%10**7
        r = ist//10**14
        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: Wrong Answer

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**14+l*10**7+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**7
        l = (ist//10**7)%10**7
        r = ist//10**14
        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: Wrong Answer

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 = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*10**14+l*10**7+i)

    qi.sort()

    ans = [-1]*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**7
        l = (ist//10**7)%10**7
        r = ist//10**14
        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: Wrong Answer

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

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]
Qs = sorted(Qs,key = lambda x: (x[1]//sqrtN,x[2]))

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

now = DD(int)
nl = nr = 0
cnt = 0
block = 1
for i,l,r in Qs:
  """
  if l >= sqrtN*block:
    while l >= sqrtN*block:
      block += 1
    while nr > r:
      if now[A[nr-1]] == 1:
        cnt -= 1
      now[A[nr-1]] -= 1
      nr -= 1
  """
  while nr < r:
    if now[A[nr]] == 0:
      cnt += 1
    now[A[nr]] += 1
    nr += 1
  if nl < l:
    while nl < l:
      if now[A[nl]] == 1:
        cnt -= 1
      now[A[nl]] -= 1
      nl += 1
  else:
    while nl > l:
      if now[A[nl-1]] == 0:
        cnt += 1
      now[A[nl-1]] += 1
      nl -= 1

  ans[i] = cnt
  
print(*ans,sep="\n")

Submission status: Wrong Answer

Solution code:
import copy

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

def AddingCum(Cs):
  AllCs=list(set(sorted(Cs)))
  Each=[0]*len(AllCs)
  Cum=[]
  Cum.append(Each)
  index=0
  for c in Cs:
    if index>0:
      newappend=copy.copy(Cum[-1])
      Cum.append(newappend)

    for i in range(len(AllCs)):
      if AllCs[i]==c:
        #rint(index)
        Cum[index][i]+=1
        break
    index+=1
  return Cum

def countnumall(Cum,l,r):
  numall=0
  for k in range(len(Cum[0])):
    #print(k)
    if l==1:
      ushiro=0
    else:
      ushiro=l-2
    
    if Cum[r-1][k]-Cum[ushiro][k]>0:
      numall+=1
  #print("-----",l,r)
  return numall

Cum=AddingCum(Cs)

for i in range(Q):
  l,r = map(int,input().split())
  print(countnumall(Cum,l,r))

Submission status: Wrong Answer

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

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

    # ABC174-F

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

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

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

    def rem(i):
        global 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: Wrong Answer

Solution code:
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append((l, r, 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 l, r, i in query:
    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)

print(ans)

Submission status: Wrong Answer

Solution code:
import copy
N,Q=map(int,input().split())
Cs=list(map(int,input().split()))

AllCs=list(set(sorted(Cs)))
Each=[0]*len(AllCs)
Cum=[]
Cum.append(Each)

index=0
for c in Cs:
  #print(c)
  #print(Cum)
  if index>0:
    newappend=copy.copy(Cum[-1])
    Cum.append(newappend)

  for i in range(len(AllCs)):
    if AllCs[i]==c:
      #rint(index)
      Cum[index][i]+=1
      break
  index+=1      

#print(Cum)

for i in range(Q):
  l,r = map(int,input().split())
  numall=0
  for k in range(len(AllCs)):
    #print(k)
    if l==1:
      ushiro=0
    else:
      ushiro=l-2
    
    if Cum[r-1][k]-Cum[ushiro][k]>0:
      numall+=1
  #print("-----",l,r)
  print(numall)

Submission status: Wrong Answer

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


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

    # ABC174-F

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

    Bsize = int(N ** 0.5) + 1
    query = []
    for q in range(Q):
        l, r = map(int, input().split())
        query.append((l - 1, r - 1, q))
    query.sort(key=lambda x: x[1])
    query.sort(key=lambda x: x[0] // Bsize)
    exit()

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

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

    def rem(i):
        global 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: Wrong Answer

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 = [int(i) for i in ipt().split()]
    qi = []
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append((r,l,i))

    qi.sort()

    ans = [-1]*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 r,l,i in qi:
        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: Wrong Answer

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


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

    # ABC174-F

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

    Bsize = int(N ** 0.5) + 1
    query = []
    for q in range(Q):
        l, r = map(int, input().split())
        query.append((l - 1, r - 1, q, l // Bsize))
    query.sort(key=lambda x: x[1])
    query.sort(key=lambda x: x[3])
    exit()

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

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

    def rem(i):
        global 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: Wrong Answer

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


n,q=map(int,input().split())
c=list(map(int,input().split()))
lr=[list(map(int,input().split())) for i in range(q)]

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    # [1,i]の足し算
    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
    # [i,j]の足し算
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

for i in range(q):
    lr[i].append(i)
last=[-1]*(n+1)
bi=BIT(n)
lr.sort(lambda x: x[1])
# print(lr)
now=0
# last[c[now-1]]=now
# # bi.add(now,1)
# print(last)
# print(bi.el)

anslst=[-1]*q
for i in range(q):
    l,r,j=lr[i]
    while now!=r:
        now+=1
        if last[c[now-1]]!=-1:
            bi.add(c[now-1],-1)
        last[c[now-1]]=now
        bi.add(now,1)
    # print(last)
    # print(bi.el)
    # print(bi.get(l,r))
    anslst[j]=bi.get(l,r)

for i in range(q):
    print(anslst[i])

Submission status: Wrong Answer

Solution code:
import copy
N, Q = map(int, input().split())

colors = list(input().split())

colur_nums = [{} for _ in range(N)]

temp_colors = {}
for i, c in enumerate(colors):
    
    if c not in temp_colors:
        temp_colors[c] = 0
    temp_colors[c] += 1

    colur_nums[i] = copy.deepcopy(temp_colors)
    print(i,colur_nums[i])

result = []
for _ in range(Q):
    l, r = map(int, input().split())
    l = l-1
    r = r-1

    if l == 0:
        result.append(len(colur_nums[r]))
    else:
        minus_nums = colur_nums[l-1]
        all_nums = colur_nums[r]

        rest_count = 0
        for c in all_nums.keys():
            if c not in minus_nums or all_nums[c] > minus_nums[c]:
                rest_count += 1
        result.append(rest_count)

for r in result:
    print(r)

Submission status: Wrong Answer

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


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [tuple(list(map(int, input().split())) + [i]) for i in range(q)]


bit = BIT(n)
memo = {}
ans = [0] * q
ind = 0

for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

print("\n".join(map(str, ans)))

Submission status: Wrong Answer

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


def read():
    N, Q = map(int, input().strip().split())
    C = list(map(int, input().strip().split()))
    LR = []
    for i in range(Q):
        l, r = map(int, input().strip().split())
        LR.append((l-1, r))
    return N, Q, C, LR


def solve(N, Q, C, LR):
    D = math.ceil(math.sqrt(N))
    Z = [Counter() for i in range(N//D+2)]
    for i in range(0, N//D):
        Z[i] = Counter(C[i*D:(i+1)*D])
    for l, r in LR:
        chunk_l = l // D
        chunk_r = r // D
        if chunk_r - chunk_l <= 1:
            print(len(Counter(C[l:r])))
        else:
            p1 = len(Counter(C[l:(chunk_l+1)*D]))
            p3 = len(Counter(C[chunk_r*D:r]))
            z = Counter()
            for i in range(chunk_l+1, chunk_r):
                z += Z[i]
            p2 = len(z)
            print(p1+p2+p3)


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l-1, r-1, i)
    return res

#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
        pre = r
    pre = lr[0][1]
    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 pre <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_() + [i]
    return res

#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
        pre = r
    return
    pre = lr[0][1]
    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 pre <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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

Submission status: Wrong Answer

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

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

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

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append(r,l,i)
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_() + [i]
    return res

#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
        pre = r
    pre = lr[0][1]
    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 pre <= i:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
n,q=map(int,input().split())
col=list(map(int,input().split()))
dd=defaultdict(lambda:[])
j=1
for i in col:
	dd[i].append(j)
	j+=1
for _ in range(q):
	l,r=map(int,input().split())
	if l==r:
		print(1)
	else:
		c=0
		for i in dd:
			if (dd[i][-1]>=l)and(dd[i][0]<=r):
				c+=1	
		print(c)

Submission status: Wrong Answer

Solution code:
import copy
from collections import defaultdict
n, q = map(int,input().split())
c = list(map(int,input().split()))
ds = [defaultdict(int)]
lr = []

for i in range(q):
    l,r = map(int,input().split())
    lr += [(i, (l, r))]
lr.sort(key=lambda x: x[1])


def calc_dict(l,r):
    ret = defaultdict(int)
    for k,v in ds[r].items():
        ret[k] = v-ds[l-1][k]
    return ret


def calc_color(dict):
    ret = 0
    for k,v in dict.items():
        if v > 0:
            ret += 1
    return ret


for cc in c:
    d = copy.copy(ds[-1])
    d[cc] += 1
    ds += [d]

left = 0
right = 0
ans = [] * n
color = 0
d = defaultdict(int)
for i in range(q):
    l, r = lr[i][1]
    if left < l:
        d = calc_dict(l,r)
        color = calc_color(d)
        ans += [(lr[i][0], color)]
        left = l
        right = r
        continue
    for j in range(right+1, r+1):
        if d[c[j]] == 0:
            color += 1
        d[c[j]] += 1
    ans += [(lr[i][0], color)]

ans.sort()
for i in range(q):
    print(ans[i][1])

Submission status: Wrong Answer

Solution code:
import collections

n,q=map(int,input().split())
c=list(map(int,input().split()))

a = [0]*(n+1)

for i in range(n+1):
    if i == 0:
        a[i] = 0
    elif i == 1:
        a[i] = 10**c[i-1]
    else:
        a[i] = a[i-1] + 10**c[i-1]

for i in range(q):
    l,r=map(int,input().split())
    x = str(a[r]-a[l-1])
    print(len(x)-x.count('0'))

#for i in range(q):
#    l,r=map(int,input().split())
#    print(len(collections.Counter(c[l-1:r])))