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:
I = [int(_) for _ in open(0).read().split()]
N, Q=I[:2]
C = I[2:2 + N]
LR = I[2 + N:]
2 ** 40
2 ** 20
Query = []
for i, lr in enumerate(zip(LR[::2], LR[1::2])):
    l, r = lr
    Query += [r * 2 ** 40 + l * 2 ** 20 + i]
for i, c in enumerate(C):
    Query += [(i + 1) * 2 ** 40 + c]
Query.sort()
c_i = [-1] * (N + 1)

class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  # build
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])
 
    def update(self, p, v):  # set value at position p (0-indexed)
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_right(self, p, v):  # apply operator from the right side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def operate_left(self, p, v):  # apply operator from the left side
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])
 
    def query(self, l, r):  # result on interval [l, r) (0-indexed)
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)
 

ans = [0] * Q
st = SegmentTree([0] * (N + 5), lambda x,y:x+y, 0)
for q in Query:
    x, yz = divmod(q, 2 ** 40)
    y, z = divmod(yz, 2 ** 20)
    if y==0:
        if c_i[z] != -1:
            st.operate_right(c_i[z], -1)
        c_i[z] = x
        st.operate_right(x, 1)
    else:
        ans[z] = st.query(y, x + 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n,q = map(int, input().split())
cs = list(map(int, input().split()))

prevs = [-1] * (n+1)
# 左端
sts = [-1] * n
for i,c in enumerate(cs):
    c -= 1
    if prevs[c] != -1:
        sts[prevs[c]] = i
    prevs[c] = i

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+10)

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

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

bit = BIT(n)
ans = [0] * q
for l in range(n-1,-1,-1):
    # 矢印を追加
    if sts[l] != -1:
        bit.add(sts[l], 1)
    for r,i in qs[l]:
        cnt = bit.sum(r)
        ans[i] = r - l + 1 - cnt

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

Submission status: Accepted

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

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

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

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

index = list(left_index_dict.keys())
index.sort()
i = 0

N = n
bit = [0] * (N+1)

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

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

ans = [0] * q

for l, r, _i in lr:
    while i < len(index) and index[i] < l:
        for j in left_index_dict[index[i]]:
            add(j, 1)
        i += 1
    ans[_i] = sum(r) - sum(l-1)

for ansi in ans:
    print(ansi)

Submission status: Accepted

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = tuple(sorted(r*U+i for i, (l, r) in enumerate(LR)))
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Accepted

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(n+1)
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Accepted

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

n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Accepted

Solution code:
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
U = 10**6
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted(r*U+i for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for w in W:
  r, i = divmod(w, U)
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Accepted

Solution code:
from sys import stdin

class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        # self.el = [0]*(n+1)
    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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

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

query = []

for i in range(Q):
    l,r = map(int, stdin.readline().split())
    query.append((i,l,r))

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

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

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

Submission status: Accepted

Solution code:
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

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = 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])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = [-1 for _ in range(q)]
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[lr[pos][2]] = bit.sum(r) - bit.sum(l - 1)
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
    
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# Binary Indexed Tree (Fenwick Tree)
class BIT:
  def __init__(self, n):
    self.n = n
    self.bit = [0]*(n+1)
    self.el = [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):
    # assert i > 0
    self.el[i] += x
    while i <= self.n:
      self.bit[i] += x
      i += i & -i
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i-1)
  def lower_bound(self,x):
    w = i = 0
    k = 1<<((self.n).bit_length())
    while k:
      if i+k <= self.n and w + self.bit[i+k] < x:
        w += self.bit[i+k]
        i += k
      k >>= 1
    return i+1

def solve():
  N, Q = map(int, input().split())
  C = list(map(int, input().split()))
  lis = [-1]*(N+1) #各色が最後に出た位置
  bit = BIT(N) #良い玉の位置
  ans = [0]*Q
  A = [list(map(int, input().split()))+[i] for i in range(Q)]
  A.sort(key=lambda x:x[1])
  now = 0
  for l,r,ind in A:
    for i in range(now,r):
      if lis[C[i]]>=0:
        bit.add(lis[C[i]]+1,-1)
      lis[C[i]] = i
      bit.add(i+1,1)
    ans[ind] = bit.get(l,r)
    now = r
  return ans
print(*solve(),sep='\n')

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
for i in range(Q[0][2],-1,-1):
    if YOI[C[i]]==-1:
        YOI[C[i]]=i
        B.add(i+1,1)

# 
ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
left=Q[0][1]; right=Q[0][2]
#print(B.data)
# right=-1
for l in Q[1:]:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    #print(B.data)
for i in ANS:
    print(i)

Submission status: Accepted

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
# for i in range(Q[0][2],-1,-1):
#     if YOI[i]==-1:
#         YOI[C[i]]=i
#         B.add(i+1,1)
# 
# 
# ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
# left=Q[0][1]; right=Q[0][2]
#print(B.data)
right=-1
for l in Q:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    #print(B.data)
for i in ANS:
    print(i)

Submission status: Accepted

Solution code:
def main(N,Q,C,LR,A):
    data = [0]*(N+1)
    def add(i,x):
        i+=1
        while i <= N:
            data[i]+= x
            i+=i&-i 
            #下桁から最初に1が出現するところまで拾う
            #111 -> 1 , 1100 -> 100 , 1010 -> 1
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc = CC('my_module')
  
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return njit(f)
  
    main=cc_export(main,(i8,i8,i8[:],i8[:,:],i8[:]))
    cc.compile()
    exit()
  
def input(): return sys.stdin.buffer.readline()
N,Q=map(int, input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
#print(C)
LR_ = [0] * (Q*2)
for i in range(Q):
    LR_[i*2],LR_[i*2+1] = input().split()
LR=np.array(LR_, dtype=np.int64).reshape(Q,2)
#print(LR)
A=np.argsort(LR[:,1])

from my_module import main
print(*main(N,Q,C,LR,A),sep='\n')

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp(True)
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (510000)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            if mp[da[now]]!=-1:
                fw.add(mp[da[now]], -1)
            mp[da[now]] = now
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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



my_main()

Submission status: Accepted

Solution code:
from collections import Counter, defaultdict, deque
import bisect
from sys import stdin, stdout
from itertools import repeat
import math
 
# sys.stdin = open('input')
 
def inp(force_list=False):
    re = map(int, raw_input().split())
    if len(re) == 1 and not force_list:
        return re[0]
    return re
 
def inst():
    return raw_input().strip()
 
def gcd(x, y):
   while(y):
       x, y = y, x % y
   return x
 
mod = 1000000007
def idx(c):
    return ord(c) - ord('a')

class Fenwick(object):
    def __init__(self, n):
        self.n = n
        self.da = [0] * n
    
    def add(self, pos, x):
        while pos < self.n:
            self.da[pos] += x
            pos |= pos + 1

    def ps(self, pos):
        re = 0
        while pos >= 0:
            re += self.da[pos]
            pos &= pos + 1
            pos -= 1
        return re

    def sum(self, x, y):
        return self.ps(y) - self.ps(x-1)

def my_main():
    n, nq = inp()
    da = inp()
    q = []
    for i in range(nq):
        l, r = inp()
        q.append((l, r, i))
    q.sort(key=lambda e:e[-2])
    mp = [-1] * (n+5)
    now = -1
    fw = Fenwick(n)
    ans = [0] * nq
    for l, r, idx in q:
        l -= 1
        r -= 1
        while now < r:
            now += 1
            try:
                if mp[da[now]]!=-1:
                    fw.add(mp[da[now]], -1)
                mp[da[now]] = now
            except:
                pass
            fw.add(now, 1)
        ans[idx] = fw.sum(l, r)

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


            

 
 
 
 
my_main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    
    readline = sys.stdin.readline
    readall = sys.stdin.read
    MI = lambda: map(int, readline().split())
    LI = lambda: list(map(int, readline().split()))
    
    class BIT:
        '''
        0-indexed
        '''
        def __init__(self, N):
            self.size = N
            self.tree = [0] * (N + 1)
            self.depth = N.bit_length()

        def _bitsum(self, i):
            ret = 0
            while i:
                ret += self.tree[i]
                i ^= i & -i
            return ret

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(self, i, x):
            i += 1
            while i <= self.size:
                self.tree[i] += x
                i += i & -i
            return

        def lower_bound(self, x):
            sum_ = 0
            pos = 0
            v = 1 << self.depth
            for i in range(self.depth, -1, -1):
                k = pos + v
                if k <= self.size and sum_ + self.tree[k] < x:
                    sum_ += self.tree[k]
                    pos += v
                v >>= 1
            return pos + 1, sum_

    
    N,Q=MI()
    C=LI()
    
    Query =[]
    
    M=10**6
    M2=10**12
    for i in range(Q):
        l, r = MI()
        l-=1
        r-=1
        Query.append(r*M2 + l*M + i)
    Query.sort()
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for q in Query:
        r = q // 10 ** 12
        l = (q % 10 ** 12) // 10 ** 6
        i = q % 10 ** 6
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Accepted

Solution code:
SHIFT = 1 << 20


class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

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

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

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

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


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append(le << 20 | j)

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for le in Query[i]:
            j = le % SHIFT
            le >>= 20
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

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

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

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

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


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append((le, j))

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for (le, j) in Query[i]:
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class fenwick_tree:
    """
    区間の一点更新と，区間和の取得がO(log n)で可能なデータ構造
    1-indexedで実装
    """

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

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

    def sum_acc(self, i, j):
        """ [i,j] の和を返す """
        return self.sum_until(j) - self.sum_until(i-1)

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


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [[] for _ in range(N+1)]
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query[ri].append((le, j))

    Query.append((-1, -1, -1))

    lastappend = [-1] * (N + 1)
    bit = fenwick_tree(N)
    ans = [0]*Q

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            bit.add(lastappend[a], -1)
        lastappend[a] = i
        bit.add(i, 1)
        for (le, j) in Query[i]:
            ri = i
            ans[j] = bit.sum_acc(le, ri)

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


if __name__ == '__main__':
    main()