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:
import sys
from operator import add, itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(lambda n: int(n) - 1, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    query = sorted([(left - 1, right, idx) for idx, (left, right) in enumerate(lr)], key=itemgetter(1))
    seg_tree = SegmentTree([0] * N, add, 0)
    c_to_idx = [-1] * N
    
    p_right = 0
    ans = [0] * Q
    for left, right, idx in query:
        for i in range(p_right, right):
            if c_to_idx[c[i]] != -1:
                seg_tree.update(c_to_idx[c[i]], 0)
            seg_tree.update(i, 1)
            c_to_idx[c[i]] = i
        p_right = right
        ans[idx] = seg_tree.query(left, right)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

N, Q = map(int, input().split())
C = list(map(int, input().split()))
query = []

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

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

class BIT:
  from operator import add, sub
  X_unit = 0
  X_f = add
  X_f_rev = sub

  def __init__(self, seq):
    N = len(seq)
    self.N = N
    self.X = seq[:]
    for i in range(self.N):
      j = i + ((i+1) & -(i+1))
      if j < self.N:
        self.X[j] = self.X_f(self.X[i], self.X[j])
  
  def set_val(self, i, x):
    while(i < self.N):
      self.X[i] = self.X_f(self.X[i], x)
      i += (i+1) & -(i+1)

  def cum_val(self, i):
    res = self.X_unit
    while(i > -1):
      res = self.X_f(res, self.X[i])
      i -= (i+1) & -(i+1)
    return res

  def fold(self, L, R):
    return self.X_f_rev(self.cum_val(R-1), self.cum_val(L-1))

GJ = [-1]*N
bit = BIT([0]*N)
ans = [0]*Q
st = 0

for i in range(N):
  if GJ[C[i]-1] != -1:
    bit.set_val(GJ[C[i]-1], -1)
  GJ[C[i]-1] = i
  bit.set_val(i, 1)
  if st < Q:
    while query[st][2] == i+1:
      ans[query[st][0]] = bit.fold(query[st][1]-1, query[st][2])
      st += 1
      if st == Q:
        break

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

Submission status: Accepted

Solution code:
"""
O_______________________________________________________________________________________________________________O
*                                                                                                               *
*                        xxxxx                                                                                  *
*                       xxxxxxx                                                 xxxxxxxxxxxxxxxxx               *
*                      xxxxxxxxx                                           xxxxxxxxxx      xxxxxxxxxxx          *
*                     xxxxx xxxxx                                      xxxxx                     xxxxxxxxxx     *
*                    xxxxx   xxxxx                                  xxxxx                             xxxxxxx   *
*                   xxxxx     xxxxx                               xxxxx                                         *
*                  xxxxx       xxxxx                             xxxxx                                          *
*                 xxxxx         xxxxx                           xxxxx                                           *
*                xxxxx           xxxxx                          xxxxx                                           *
*               xxxxx             xxxxx                        xxxxx                                            *
*              xxxxx               xxxxx                       xxxxx                                            *
*             xxxxx                 xxxxx                     xxxxx                                             *
*            xxxxxxxxxxxxxxxxxxxxxxxxxxxxx                    xxxxx                                             *
*           xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                             *
*          xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx                   xxxxx                                            *
*         xxxxx                         xxxxx                  xxxxx                                            *
*        xxxxx                           xxxxx                  xxxxx                                           *
*       xxxxx                             xxxxx                 xxxxx                                           *
*      xxxxx                               xxxxx                 xxxxx                                          *
*     xxxxx                                 xxxxx                 xxxxx                                         *
*    xxxxx                                   xxxxx                  xxxxx                             xxxxxxx   *
*   xxxxx                                     xxxxx                    xxxxx                     xxxxxxxxxx     *
*  xxxxx                                       xxxxx                       xxxxxxxxxx      xxxxxxxxxxx          *
* xxxxx                                         xxxxx                           xxxxxxxxxxxxxxxxx               *
*                                                                                                               *
O_______________________________________________________________________________________________________________O
"""
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*q
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  for l,ind in queries[i]:
    ans[ind]=bitt.sum(l,i-1)
print(*ans)

Submission status: Accepted

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    Mo_argsort = cc_export(Mo_argsort, (i8[:,:],))
    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))

Submission status: Accepted

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def Ra():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
sys.setrecursionlimit(10**9)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################


class Bit:
    def __init__(self,n,init=None):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        if init!=None:
            for i in range(len(init)):
                self.add(i,init[i])
        
    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        if i<0:return NotImplemented
        k=0
        while i<=self.size and k<100:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        if i<0:return NotImplemented
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def __getitem__(self,key):
        return self.sum(key+1)-self.sum(key)

    def __setitem__(self,key,value):
        self.add(key,value-self.sum(key+1)+self.sum(key))

    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)

def compress(L):
    dc={v:i for i,v in enumerate(sorted(set(L)))}
    return [dc[i] for i in L]
    
show_flg=False
show_flg=True

ans=0

n,Q=LI()
c=LI_()

q=[(i,LI())for i in range(Q)]

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

bt=Bit0(-~n)
lst=[-1]*-~n

ans=[0]*Q
R=0
for j,(l,r) in q:
    while R<r:
        col=c[R]
        if lst[col]!=-1:
            bt.add(lst[col],-1)
        lst[col]=R
        bt.add(lst[col],1)
        R+=1
    ans[j]=bt.sum(r+1)-bt.sum(l-1)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

#Ai+=x O(logN)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

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

LRI.sort(key=lambda x:x[0])
lastAppend =[-1]*(N+1)
#A1 ... AnのBIT(1-indexed)
BIT=[0]*(N+1)
ANS=[0]*Q
now=1
for r,l,i in LRI:
  while now<=r:
    c=C[now-1]
    #初めてその種類が登場
    if lastAppend[c]==-1:
      BIT_update(BIT,now,1,N)
    #その種類の登場が2回目　
    else:
      BIT_update(BIT,now,1,N)
      BIT_update(BIT,lastAppend[c],-1,N)
    lastAppend[c]=now                
    now+=1
  ANS[i]=BIT_query(BIT,r)-BIT_query(BIT,l-1)

for ans in ANS:
  print(ans)

Submission status: Accepted

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

def BIT_query(BIT,idx):
  res_sum=0
  if idx==0:
    return 0
  while idx>0:
    res_sum+=BIT[idx]
    idx-=idx&(-idx)
  return res_sum

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

def main():
  N,Q=map( int, input().split())
  C=list( map( int, input().split()))
  LRI=[]
  for i in range(Q):
    l,r=map( int, input().split())
    LRI.append((r,l,i))
  LRI.sort(key=lambda x:x[0])
  lastAppend=[-1]*(N+1)
  BIT=[0]*(N+1)
  ANS=[0]*Q
  now=1
  for r,l,i in LRI:
    while now <= r:
      c=C[now-1]
      if lastAppend[c]== -1:
        BIT_update(BIT,now,1,N)
      else:
        BIT_update(BIT,now,1,N)
        BIT_update(BIT,lastAppend[c],-1,N)
      lastAppend[c]=now                
      now+=1
    ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):a[i]-=1
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
Bit=BinaryIndexedTree(n+1)
ans=[-1]*q
for i in range(n):
  Bit.add(lastAppeared[a[i]],-1)
  Bit.add(i+1,1)
  lastAppeared[a[i]]=i+1
  for l,ind in queries[i]:
    ans[ind]=Bit.sum(l+1,i)
print(*ans)

Submission status: Accepted

Solution code:
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
ans=[0]*q
queries=[[]for _ in range(n)]
for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[-1]*n
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]-1]!=-1:
    bitt.add(lastAppeared[a[i]-1],-1)
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]-1]=i
  for l,ind in queries[i]:
    ans[ind]=bitt.sum(l,i-1)
print(*ans)

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

def Mo(n,q,c,qi):
    ans = [0]*q
    ln = [-1]*(n+1)

    #BITの構成
    BIT = [0]*(n+1)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    #Rが小さい方から見ていく,BITによる累積和の処理を含む
    pr = 0
    for i,l,r in qi:
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)
    return ans

def main():
    n,q = map(int,ipt().split())
    c = [int(i) for i in ipt().split()]
    qi = []
    base = 10**6+1
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*(base**2)+l*base+i)
    qi.sort()

    qs = [(i%(base),(i//base)%base,i//(base**2))for i in qi]

    ans = Mo(n,q,c,qs)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
 
sys.setrecursionlimit(500005)
stdin = sys.stdin
 
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()
 
n, q = na()
a = na()
lasts = [-1] * (n+1)
rs = []
for i in range(n):
  if lasts[a[i]] != -1:
    rs.append((lasts[a[i]], i))
  lasts[a[i]] = i
 
rs.sort(key=itemgetter(0))
 
qs = []
for i in range(q):
  u = na()
  qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=itemgetter(0))
 
def addfenwick(ft, i, v):
  if v == 0 or i < 0: return
  i += 1
  while i < len(ft):
    ft[i] += v
    i += i&-i
 
def sumfenwick(ft, i):
  s = 0
  i += 1
  while i > 0:
    s += ft[i]
    i -= i&-i
  return s
 
ft = [0] * (n+10)
anss = [0] * q
p = len(rs)-1
for q in qs[::-1]:
  while p >= 0 and rs[p][0] >= q[0]:
    addfenwick(ft, rs[p][1], 1)
    p -= 1
  anss[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])
 
for v in anss:
  print(v)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.buffer.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort(key=itemgetter(0))
ans = [0] * Q
for event in events:
    # 色の区間が来たら、点を追加
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    # クエリが来たら、点の数を数える
    else:
        r, _, l, i = event
        total = r - l + 1
        # 区間全体 - この時の領域内の点の数
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
from numpy import*
def main(n,q,c,z):
  a=zeros(q,int64)
  t=zeros(9**6,int64)
  b=zeros(9**6,int64)
  j=0
  for i in argsort(z[:,1]):
    l,r=z[i,0],z[i,1]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:
        t[x]+=1
        x+=x&-x
      while y<=n:
        t[y]-=1
        y+=y&-y
    while l:
      a[i]+=t[l]
      l-=l&-l
  return a
if sys.argv[-1]=='ONLINE_JUDGE':
  from numba.pycc import CC
  cc=CC('my_module')
  cc.export('main','i8[:](i8,i8,i8[:],i8[:,:])')(main)
  cc.compile()
  exit()
from my_module import main
(n,q),c,*z=[int_(t.split())for t in open(0)]
print(' '.join(map(str,main(n,q,c,int_(z)).tolist())))

Submission status: Accepted

Solution code:
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:z[x][1]):
 l,r=z[i]
 while j<r:
  d=c[j];j+=1;x,y,b[d]=b[d]+1,j+1,j
  while x<=n:t[x]+=1;x+=x&-x
  while y<=n:t[y]-=1;y+=y&-y
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Accepted

Solution code:
import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    
    n = 1 << N.bit_length()
    X = L.copy()
    Y = R.copy()
    s = n >> 1
    B = np.zeros(Q, dtype=np.int64)
    while s > 0:
        rx = X & s > 0
        ry = Y & s > 0
        B += s * s * (3*rx ^ ry)
        Idx2 = ~ry
        Idx1 = rx & Idx2
        X[Idx1] = n-1 - X[Idx1]
        Y[Idx1] = n-1 - Y[Idx1]
        X[Idx2], Y[Idx2] = Y[Idx2], X[Idx2]
        s >>= 1
    
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Accepted

Solution code:
def A(i,x):
 while i<=n:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:z[x][1]):
 l,r=z[i]
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Accepted

Solution code:
def A(i,x):
 while i<n+2:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i in sorted(range(q),key=lambda x:z[x][1]):
 l,r=z[i]
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Accepted

Solution code:
def A(i,x):
 while i<n+2:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*9**6
for i,(l,r)in sorted(zip(range(q),z),key=lambda x:x[1][1]):
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Accepted

Solution code:
def A(i,x):
 while i<n+2:t[i]+=x;i+=i&-i
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
a=[0]*q
j,*b=t=[0]*(n+2)
for i,(l,r)in sorted(zip(range(q),z),key=lambda x:x[1][1]):
 while j<r:d=c[j];j+=1;A(b[d]+1,1);b[d]=j;A(j+1,-1)
 while l:a[i]+=t[l];l-=l&-l
print(*a)

Submission status: Accepted

Solution code:
N=2**20-1
R=range
(n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
t,*o=B=[0]*N
A=[[n]for _ in B]
for i in R(n):A[c[~i]]+=~i+n,
def P(a,x):
	i=a[-1]+1
	while i<N:B[i]+=x;i+=i&-i
for i in A:P(i,1)
for x in sorted(i|z[i][0]<<40|z[i][1]<<20for i in R(q)):
	l,r,i=(x>>40)-1,x>>20&N,x&N
	while t<l:b=A[c[t]];P(b,-1);b.pop();P(b,1);t+=1
	while r:o[i]+=B[r];r-=r&-r
	while l:o[i]-=B[l];l-=l&-l
print(*o[:q])

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


def solve(inp):
    def bit_add(arr, n, i, x):
        while i <= n:
            arr[i] += x
            i += i & -i

    def bit_sum(arr, i):
        result = 0
        while i > 0:
            result += arr[i]
            i ^= i & -i
        return result

    n = inp[0]
    q = inp[1]
    ccc = inp[2:2 + n] - 1
    lll = inp[2 + n::2] - 1
    rrr = inp[3 + n::2] - 1

    bit = np.zeros(n + 2, dtype=np.int64)
    appeared = np.full(n, -1, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    p = 0
    for i in np.argsort(rrr):
        while p <= rrr[i]:
            c = ccc[p]
            before_appeared = appeared[c]
            if before_appeared != -1:
                bit_add(bit, n + 2, before_appeared + 2, -1)
            bit_add(bit, n + 2, p + 2, 1)
            appeared[c] = p
            p += 1

        ans[i] = bit_sum(bit, rrr[i] + 2) - bit_sum(bit, lll[i] + 1)

    return ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC

    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()
    exit()

if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit

    solve = njit('(i8[:],)', cache=True)(solve)
    print('compiled', file=sys.stderr)

inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))