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: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
 
    def to_sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= (i & -i)
        return s
 
    def add(self, i, x):
        while i <= self.n:
            self.data[i] += x
            i += (i & -i)
 
    def get(self, i, j):
        return self.to_sum(j)-self.to_sum(i-1)

import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))
#print(C)
LR = []
ans = [0 for _ in range(Q)]
for i in range(Q):
  temp= list(map(int,input().split()))
  LR.append((temp,i)) #クエリとID
LR.sort(key=lambda x : x[0][1]) #右端で昇順にソート
#print(LR)
CMAX = max(C)
Tree = BIT(N)
last = [-1 for _ in range(CMAX)] #色を0index
left,right = LR[0][0]
for j in range(right):
  mae = last[C[j]-1]
  last[C[j]-1] = j
  if mae !=-1:
    Tree.add(mae+1,-1) #BITは1から
  Tree.add(last[C[j]-1]+1,1) #BITは1から
  #print(Tree.get(left,right))
#print(last)
D = []
#for i in range(1,N+1):
#  detemp = Tree.get(i,i)
#  D.append(detemp)
#print(D)

temp = Tree.get(left,right)
ID = LR[0][1]
ans[ID] = temp
lastright = right  
#print(Tree.get(left,right))
for i in range(1,Q):
  left,right = LR[i][0]
  #print(right,lastright)
  if lastright < right:
    for j in range(lastright,right):
      mae = last[C[j]-1]
      last[C[j]-1] = j
      #print(C[j],mae,j,last[C[j]-1] )
      if mae !=-1:
        #rint(C[j],"A")
        Tree.add(mae+1,-1) #BITは1index
      Tree.add(j+1,1) #BITは1index
  temp = Tree.get(left,right)
  ID = LR[i][1]
  ans[ID] = temp
  lastright = right
  #print(last)


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

Submission status: Accepted

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

class BIT:
    def __init__(self,len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)
        
    # sum(A0 ~ Ai)
    # O(log N)
    def query(self,i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx&(-idx)
        return res

    # Ai += x
    # O(log N)
    def add(self,i,x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx&(-idx)
    
    # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0)
    # O(log N)
    def lower_left(self,w):
        if (w < 0):
            return -1
        x = 0
        k = 1<<(self.N.bit_length()-1)
        while k > 0:
            if x+k < self.N and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k
            k //= 2
        return x

n,q = map(int,rd().split())
c = list(map(int,rd().split()))
lr = []
for i in range(q):
    l,r = map(int,rd().split())
    lr.append([l,r,i])
lr.sort(key = lambda x:x[1])

last = [-1]*(n+1)
bit = BIT(n+1)
ans = [0]*q
current = 1
for i in range(q):
    # rightに達するまで
    while current <= lr[i][1]:
        # 今の色が過去にあった場合、bitの値を0に戻す
        if last[c[current-1]] != -1:
            bit.add(last[c[current-1]], -1)
        last[c[current-1]] = current
        bit.add(current, 1)
        current += 1
    ans[lr[i][2]] = bit.query(lr[i][1]) - bit.query(lr[i][0] - 1)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=map(int,input().split())
  l.append([L,R,i])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=map(int,input().split())
  l.append([L,R,i])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i,j,k in l:
  while ct<=j:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[k]=BIT.sum(j+1)-BIT.sum(i)

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=map(int,input().split())
  l.append([L*10**6+i,R])
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][0]%10**6]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0]//10**6)

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[]
for i in range(q):
  L,R=map(int,input().split())
  l.append([R,L,i])
l.sort(key=lambda x:x[0])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][0]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][0]+1)-BIT.sum(l[i][1])

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from operator import itemgetter
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

for i in ans:
  print(i)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from operator import itemgetter
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=itemgetter(1))

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l.sort(key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l[i][2]]=BIT.sum(l[i][1]+1)-BIT.sum(l[i][0])

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

Submission status: Accepted

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i].append(i)
l2=sorted(l,key=lambda x:x[1])

L=[-1]*(5*10**5+1)

class Bit:
  def __init__(self,n):
    self.size=n
    self.tree=[0]*(n + 1)
    self.depth=n.bit_length()

  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

BIT=Bit(n+1)

ans=[0]*q
ct=0
for i in range(q):
  while ct<=l2[i][1]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans[l2[i][2]]=BIT.sum(l2[i][1]+1)-BIT.sum(l2[i][0])

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')

# 要素updateと区間クエリ
class SegmentTree(object):

    def __init__(self, A, e, fn):  # O(N)
        """
        :param A: 区間クエリの対象となる配列
        :param e: 単位元 fn(a, e) = fn(e, a) = a
        :param fn: (a, b) -> x な関数 a, bは交換則を満たす
        """
        self.e = e
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.tree = [e] * 2 * self.length
        for i in range(len(A)):
            self.tree[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.tree[i] = self.fn(self.tree[2 * i + 1], self.tree[2 * i + 2])

    # 配列のi番目をxに更新する
    def update(self, i, x):  # O(logN)
        i += self.length - 1
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.fn(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    # 区間[p, q)に関するクエリに答える
    def query(self, p, q):  # O(logN)
        if q <= p:
            return self.e
        p += self.length - 1
        q += self.length - 2
        res = self.e
        while q - p > 1:
            if p & 1 == 0:
                res = self.fn(res, self.tree[p])
            if q & 1 == 1:
                res = self.fn(res, self.tree[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.fn(res, self.tree[p])
        else:
            res = self.fn(self.fn(res, self.tree[p]), self.tree[q])
        return res

    # 現在のi番目の要素を取得する
    def at(self, i):  # O(1)
        return self.tree[i + self.length - 1]


N, Q = MI()
C = LMI()
LR = []
for i in range(Q):
    l, r = MI0()
    LR.append((i, l, r))

LR.sort(key=lambda x: x[2])
seg = SegmentTree([0] * N, 0, lambda a, b: a + b)
idx = dict()
cur = 0
ans = [0] * Q
for i, l, r in LR:
    while cur <= r:
        if C[cur] in idx:
            seg.update(idx[C[cur]], 0)
            seg.update(cur, 1)
            idx[C[cur]] = cur
        else:
            seg.update(cur, 1)
            idx[C[cur]] = cur
        cur += 1
    ans[i] = seg.query(l, r + 1)
for a in ans:
    print(a)

Submission status: Accepted

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


class Bit:
    def __init__(self, n):
        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


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

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

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

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

Submission status: Accepted

Solution code:
import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 # 1-index
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def _sum(self, i):
        ret = 0
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def get_sum(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self._sum(r) - self._sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i+1

def Main():
    n, q = read_ints()
    c = read_int_list()
    query = [(read_ints()) for _ in range(q)]
    
    que = defaultdict(list)
    for i, (l, r) in enumerate(query):
        que[r].append([l, i])

    ans = [0] * q    
    last = [-1] * (n + 1)
    bit = BinaryIndexedTree(n)
    
    for i, x in enumerate(c):
        if last[x] > 0:
            bit.add(last[x]-1, -1)
        last[x] = i + 1
        bit.add(last[x]-1, 1)
        
        if len(que[i + 1]) > 0:
            for l, j in que[i + 1]:
                ans[j] = bit.get_sum(l, i+1)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    Main()

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n+1)

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

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


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

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

lr.sort(key=lambda x: x[1])

rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]]+1, -1)
    rightest[c[i]] = i
    bit.add(i+1, 1)

    while current_q < Q and lr[current_q][1] == i:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1] + 1) - bit.sum(lr[current_q][0])
        current_q += 1

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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())

qu=[list(map(int, input().split())) +[i] for i in range(q)]
qu.sort(key=lambda x:x[1])
bit=[0]*(n+1)

last=[-1]*(n+1)

def add(t,x):
    while t<=n:
        bit[t]+=x
        t += t&(-t)

def query(t):
    res=0
    while t:
        res+=bit[t]
        t-=t&(-t)
    return res

used=1
ans=[0]*q
for l,r,i in qu:
    while used<=r:
        add(used,1)
        if last[c[used-1]]>=0:
            add(last[c[used-1]],-1)
        last[c[used-1]]=used
        used+=1
    ansi=query(r)-query(l-1)
    ans[i]=ansi
for ansi in ans:
    print(ansi)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        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
 
n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)

Submission status: Accepted

Solution code:
from sys import stdin
input = stdin.readline
class Bit:
    def __init__(self, n):
        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

n, q = map(int, input().split())
tmp = list(map(int, input().split()))
color = [-1]
for v in tmp:
    color.append(v)
qry = [None]*q
ans = [0]*q
p = 0
for _ in ans:
    l, r = map(int, input().split())
    qry[p] = [l-1, r, p]
    p += 1
qry.sort(key=lambda x: x[1])
dic = {}
last_update_idx = 1
bit = Bit(n)
for l, r, i in qry:
    if last_update_idx < r+1:
        st = set()
        for j in range(last_update_idx, r+1):
            if not color[j] in st and color[j] in dic:
                bit.add(dic[color[j]], -1)
            dic[color[j]] = j
            st.add(color[j])
        for v in st:
            bit.add(dic[v], 1)
        last_update_idx = r+1
    ans[i] = bit.sum(r) - bit.sum(l)
for v in ans:
    print(v)

Submission status: Accepted

Solution code:
from typing import Union
import sys
from operator import itemgetter

Num = Union[int, float]


class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.bit = [0] * (self.size + 1)
    
    def add(self, k: int, x: Num) -> None:
        """
        (0-index で) k 番目の要素に x をたす。
        >>> b = FenwickTree(5)
        >>> b.add(0, 10)
        >>> b.bit
        [0, 10, 10, 0, 10, 0]
        """
        if not 0 <= k < self.size:
            raise IndexError(f"FenwickTree.add(): size is {self.size}. accessed [{k}]")
        k += 1    # 1-index
        while k <= self.size:
            self.bit[k] += x
            LSB = k & (-k)
            k += LSB
    
    def _accum_sum(self, k: int) -> Num:
        """ (1-index, 内部関数) bit の 1 ~ k 番目の要素の和を求める。"""
        s = 0
        while k > 0:
            s += self.bit[k]
            LSB = k & (-k)
            k -= LSB
        return s
    
    def sum(self, l: int, r: int) -> Num:
        """
        (0-index で) [l, r) 区間の和を求める。
        >>> b = FenwickTree(5)
        >>> b.add(1, 10)
        >>> b.add(2, 20)
        >>> b.sum(1, 3)
        30
        """
        if not 0 <= l <= r <= self.size:
            raise IndexError(f"FenwickTree.sum(): size is {self.size}. got slice is [{l}:{r}]")
        # 0-index の数列における [l]...[r-1] の閉区間を計算。1-index なら [l+1]...[r]。
        return self._accum_sum(r) - self._accum_sum(l)



def input(): return sys.stdin.readline().rstrip()

def mi(): return map(int, input().split())

def mi_0(): return map(lambda x: int(x)-1, input().split())


def solve(n, q, interval, query):
    """
    [s, t] なる点を含むリスト interval
    [l, r(, query-number)] (0-index) なるクエリを q 個含むリスト query。l <= s and t <= r なる点の個数は何個か？
    """
    query_to_ans = [-1] * q
    query.sort(key=itemgetter(0))
    interval.sort(key=itemgetter(0))
    ft = FenwickTree(5 * 10 ** 5 + 5)
    # main
    for l, r, query_num in reversed(query):
        # l 以上のものを全て処理対象に入れる
        while interval and l <= interval[-1][0]:
            _, t = interval.pop()
            ft.add(t, 1)
        query_to_ans[query_num] = (r - l + 1) - ft.sum(0, r+1)
    # output
    for ans in query_to_ans:
        print(ans)



def main():
    n, q = mi()
    L = tuple(mi())
    prev = dict()
    intervals = []
    for i in range(n):
        if L[i] not in prev:
            prev[L[i]] = i
        else:
            intervals.append((prev[L[i]], i))
            prev[L[i]] = i
    query = []
    for i in range(q):
        l, r = mi_0()
        query.append((l, r, i))
    solve(n, q, intervals, query)
    


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


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

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

print(*res, sep='\n')

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.buffer.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


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

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


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

query_.sort(key=lambda x: x[1])

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

Submission status: Accepted

Solution code:
def segfunc(x,y):
  return x+y
ide_ele=0
class SegTree():
  def __init__(self,init_val,segfunc,ide_ele):
    n=len(init_val)
    self.segfunc=segfunc
    self.ide_ele=ide_ele
    self.num=1<<(n-1).bit_length()
    self.tree=[ide_ele]*2*self.num
    for i in range(n):
      self.tree[self.num+i]=init_val[i]
    for i in range(self.num-1,0,-1):
      self.tree[i]=self.segfunc(self.tree[2*i], self.tree[2*i+1])
  def update(self,k,x):
    k+=self.num
    self.tree[k]=x
    while k>1:
      self.tree[k>>1]=self.segfunc(self.tree[k],self.tree[k^1])
      k>>=1
  def query(self,l,r):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree([0]*n,segfunc,ide_ele)
lr=[[]for _ in range(n+1)]
for i in range(q):
  l,r=map(int,input().split())
  lr[r]+=[(l,i)]
d={}
for i in range(n):
  if not d.get(c[i]):d[c[i]]=[i]
  else:d[c[i]]+=[i]
for i in d:
  st.update(d[i][-1],1)
ans=[0]*q
r=n
while r>0:
  if lr[r]:
    l,i=lr[r].pop()
    ans[i]=st.query(l-1,r)
  while not lr[r] and r>0:
    if d[c[r-1]]:st.update(d[c[r-1]].pop(),0)
    if d[c[r-1]]:st.update(d[c[r-1]][-1],1)
    r-=1
for i in ans:print(i)

Submission status: Accepted

Solution code:
def solve():
    import sys
    input = sys.stdin.readline

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()

Submission status: Accepted

Solution code:
def solve():
    import sys
    input = sys.stdin.readline

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()