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:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1

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

C=[None]
for c in list(map(int,input().split())):
    C.append(c)

pos=[list(map(lambda x:int(x),input().split())) for i in range(Q)]
pos = sorted([[l,r,i] for i,(l,r) in enumerate(pos)],key=lambda x:x[1])


last_appeared=[0]*(N+1) #last_appeared[i]: iが最後に現れた場所(1-origin)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
#for (l,r),i in pos:
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r]]=cur_r #lastの更新
        cur_r+=1

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


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

Submission status: Wrong Answer

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_()
    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)
    d = defaultdict(int)
    for i in range(q):
        l, r = lr[i]
        d[(l, r)] = i
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = defaultdict(lambda:-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
    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:
            l, r = lr[t]
            tmp = sum(r) - sum(l - 1)
            ans[d[(l, r)]] = tmp
            t += 1
    for ai in ans:
        print(ai) 
    return


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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,Q = map(int, input().split())
CList = list(map(int, input().split()))
List = [list(map(int, input().split())) for i in range(Q)]

for i in range(N-1):
    #List[i][0] List[i][1]
    #print((List[i][0]),(List[i][1]))
    
    print(len(set(CList[(List[i][0])-1:(List[i][1])])))

#print("-1")

Submission status: Wrong Answer

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_()
    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)
    d = defaultdict(int)
    for i in range(q):
        l, r = lr[i]
        d[(l, r)] = i
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = defaultdict(lambda:-1)
    bit = [0 for _ in range(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
    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:
            l, r = lr[t]
            if l == 0:
                tmp = sum(r)
            else:
                tmp = sum(r) - sum(l - 1)
            ans[d[(l, r)]] = tmp
            t += 1
    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,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_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    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 = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    d = defaultdict(int)
    for i in range(q):
        l, r = lr[i]
        d[(l, r)] = i
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (10 ** 5 + 1)
    b = BinaryIndexedTree(n + 1)
    t = 0
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        b.add(i, 1)
        dp[ci] = i
        if l != -1:
            b.add(l, -1)
        while t < q and lr[t][1] <= i:
            l, r = lr[t]
            if l == 0:
                tmp = b.sum(r)
            else:
                tmp = b.sum(r) - b.sum(l - 1)
            ans[d[(l, r)]] = tmp
            t += 1
    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,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_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    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 = 0
        s = 0
        step = 1 << self.size.bit_length()
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                print(self.bit[i + step - 1], i, step)
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    d = defaultdict(int)
    for i in range(q):
        l, r = lr[i]
        d[(l, r)] = i
    print(d)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (10 ** 5 + 1)
    b = BinaryIndexedTree(n + 1)
    t = 0
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        b.add(i, 1)
        dp[ci] = i
        if l != -1:
            b.add(l, -1)
        while t < q and lr[t][1] <= i:
            l, r = lr[t]
            tmp = b.sum(r) - b.sum(l - 1)
            ans[d[(l, r)]] = tmp
            # print(tmp,l,r)
            t += 1
    for ai in ans:
        print(ai) 
    return


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    #from random import randint
    my_input = sys.stdin.readline
    N, Q = map(int, my_input().split())
    A = list(map(int, my_input().split()))
    # N = 5 * 10 ** 5
    # Q = N
    # A = [randint(1, 5 * 10 ** 5) for _ in range(N)]
    MAX_A = 5 * 10 ** 5
    query = []
    for q in range(Q):
        l, r = map(int, my_input().split())
        # l, r = randint(0, N), randint(0, N)
        # l, r = min(l, r), max(l, r)
        query.append((l, r, q))


    # 一番後ろの1を削りながら0までやるイメージ
    # 1-indexed
    # 閉区間
    # 区間[s, t]の和 => BIT.add(t) - BIT.add(s - 1)

    class BinaryIndexedTree:
        def __init__(self, n):
            self.size = n
            self.bit = [0] * (n + 1)

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

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

        def reset(self):
            self.bit = [0] * (self.size + 1)


    BIT = BinaryIndexedTree(N)
    X = [-1] * (MAX_A + 1)
    for i, a in enumerate(A, start=1):
        X[a] = i
    for x in X:
        if x == -1:
            continue
        BIT.add(x, 1)

    ans = [-1] * Q
    query.sort(key=lambda x: x[1])

    for l, r, i in query:
        BIT.add(X[A[r - 1]], -1)
        X[A[r - 1]] = r
        BIT.add(r, 1)
        ans[i] = BIT.sum(r) - BIT.sum(l - 1)

    for a in ans:
        print(a)
    #print(*ans, sep='\n')


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()
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 = [self.e] * (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)
  
ST = SegmentTree(N,lambda x,y:x|y,0)
for i in range(N):
  x = A[i]
  ST.update(i,1<<x)
"""
for _ in range(Q):
  L,R = IL()
  print(count_bit(ST.get(L-1,R)))
"""

Submission status: Wrong Answer

Solution code:
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x:x[1])
curR = 0
#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
for j in range(Q):
    l,r,i = queries[j]
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
print(ans)

Submission status: Wrong Answer

Solution code:
n, q = map(int,  input().split())
colors = list(map(int, input().split()))
li = [[] for i in range(n)]

for j in range(n):
    c = colors[j]
    li[c-1].append(j)
print(li)

for i in range(q):
    ans = 0
    l ,r = map(int, input().split())
    for j  in range(n):
        if len(li[j]) > 0:
            for k in range(len(li[j])):
                ban = li[j][k]
                if l-1 <=  ban <=  r-1:
                    ans += 1
                    break
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

L = [np.array([0] * N) for _ in range(N + 1)]

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

for i in range(N):
    L[i+1] += L[i]
    L[i+1][C[i] - 1] += 1

print(L)

for _ in range(Q):
    l, r = map(int,input().split())
    tmp = L[r] - L[l-1]
    print(np.count_nonzero(tmp))

Submission status: Wrong Answer

Solution code:
import numpy as np

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
l = np.array([0 for i in range(q)], dtype = np.int64)
r = np.array([0 for i in range(q)], dtype = np.int64)
cnt = 0
wk = []
print(c)

for i in range(q):
    L, R = map(int, input().split())
    l[i] = L
    r[i] = R
for i in range(q):
    wk = []
    cnt = 0
    for j in range(r[i] - l[i] + 1):
        if c[l[i] + j -1] not in wk:
            cnt += 1
            wk.append(c[l[i] + j -1])
    print(cnt)

Submission status: Wrong Answer

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.tree[i]
      i -= i & -i
    return s

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

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lrini = [tuple(map(int,input().split())) for i in range(q)]
ans = defaultdict(int)
lr = sorted(lrini,key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[L<<20+R] = bit.sum(L+1)
  cnt = R
for l,r in lr:
  print(ans[(l-1)<<20+r])

Submission status: Wrong Answer

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


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

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

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

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

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

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














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

Submission status: Time Limit Exceeded

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] + self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l + val_r

N, Q = map(int, input().split())
A = list(map(int, input().split()))
T = {}
s_tree = segtree(N + 1, 0)
for i in range(N):
    if A[i] not in T:
        s_tree.update(i+1, 1)
        T[A[i]] = [i+1]
    else:
        T[A[i]].append(i+1)
Next = [i for i in range(N+1)]

for k, v in T.items():
    for j in range(len(v)-1):
        Next[v[j]] = v[j+1]

Ans = [0]*Q
K = {}
for i in range(Q):
    l, r = map(int, input().split())
    if l not in K:
        K[l] = [[r, i]]
    else:
        K[l].append([r, i])

for i in range(N):
    if i + 1 not in K:
        pass
    else:
        for k, v in K[i+1]:
            Ans[v] = s_tree.get(i+1, k)
    s_tree.update(Next[i+1], 1)
for i in Ans:
    print(i)