题解 | #Different Integers#

思路离线查询，树状数组维护

查询按右端点r排序，遍历查询，当一个数字全出现了，那就把这个数字第一次出现的下标单点+1

查询[l+1,r-1]的区间和，用总的去减就可以了

import sys,random,bisect
from collections import deque,defaultdict,Counter
input = lambda :sys.stdin.readline().rstrip()
mi = lambda :map(int,input().split())
li = lambda :list(mi())
ii = lambda :int(input())
 
class BIT1:
    __slots__ = "size", "bit", "tree"
    def __init__(self, n: int):
        self.size = n
        self.tree = [0]*(n+1)

    def add(self, index: int, delta: int) -> None:
        while index <= self.size:
            self.tree[index]+=delta
            index += index & -index

    def _query(self, index: int) -> int: 
        res = 0
        while index > 0:
            res += self.tree[index]
            index -= index & -index
        return res

    def queryRange(self, left: int, right: int) -> int:
        return self._query(right) - self._query(left - 1)


while True:
    try:
        n,q=li()
        arr=li()
        bit=BIT1(n+5)
        query=[]
        res=[0]*q
        for i in range(q):
            l,r=li()
            query.append([i,l-1,r-1])
        query.sort(key=lambda x:x[2])
        brr=list(range(n-1,-1,-1))
        cnt=Counter(arr)
        mx=len(cnt)
        fidx={}
        for i,a in enumerate(arr):
            if a not in fidx:
                fidx[a]=i
        for i,l,r in query:
            while brr and brr[-1]<r:
                x=brr.pop()
                cnt[arr[x]]-=1
                if cnt[arr[x]]==0:
                    bit.add(fidx[arr[x]]+1,1)
            if r-l==1:
                res[i]=mx
            else:
                res[i]=mx-bit.queryRange(l+2,r)
        for i in res:
            print(i)
    except:
        break