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
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=[0]+L()
Q=[L()+[i] for i in range(q)]
Q.sort(key=lambda x:x[1])
ans=[0]*(q)
lastapp=[0 for i in range(n+1)]

No=2
while No<=n:
    No*=2
BIT=[0]*(No+1)
def addbit(i,x):
    while i<=No:
        BIT[i]+=x
        i+= i&-i
def getsum(i):
    s=0
    while i:
        s+=BIT[i]
        i-= i&-i
    return s
def sumbit(l,r):
    return getsum(r)-getsum(l-1)

j=1
for l,r,i in Q:
    while j<=r:
        t=c[j]
        if lastapp[t]:
            addbit(lastapp[t],-1)
        addbit(j,1)
        lastapp[t]=j
        j+=1
    ans[i]=sumbit(l,r)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def update(x,i):
    if good[x]==-1:
        good[x]=i
        bit.add(i,1)
    else:
        bit.add(good[x],-1)
        good[x]=i
        bit.add(good[x],1)
    return
    
N,Q=map(int,read().split())
c=tuple(map(int,read().split()))
Query=[]
for i in range(Q):
    l,r=map(lambda x:int(x)-1,read().split())
    Query.append(r*10**12+l*10**6+i)
Query.sort()
ans=[-1]*Q
good=[-1]*(N+1)
bit=BIT(N)

i=0
for w in Query:
    R=w//10**12
    w%=10**12
    L=w//10**6
    w%=10**6
    while(i<=R):
        update(c[i],i)
        i+=1
    ans[w]=bit.cum(L,R+1)

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

Submission status: Accepted

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

class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+2)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array, start=1):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        i += 1
        while i <= self.n:
            self.tree[i] += x
            i += i & -i

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = 0    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k <= self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos-1, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res

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

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((l,r))

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

# A = [2,3,4,6,7,11,13,14]
# B = Bit(8)
# B.built(A)
# print(list(B.get(i,i+1) for i in range(len(A))))
# print(B)
# print(B.sum(3))
# print(B.get(3,6))
# print(list(B.lower_bound(i) for i in range(64)))

Submission status: Accepted

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

class Bit:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i+1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i+1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res

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

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((l,r))

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def update(x,i):
    if good[x]==-1:
        good[x]=i
        bit.add(i,1)
    else:
        bit.add(good[x],-1)
        good[x]=i
        bit.add(good[x],1)
    return
    
N,Q=map(int,read().split())
c=tuple(map(int,read().split()))
Query=[]
for i in range(Q):
    l,r=map(lambda x:int(x)-1,read().split())
    Query.append((l,r,i))
Query.sort(key=lambda x:x[1])
ans=[-1]*Q
good=[-1]*(N+1)
bit=BIT(N)

i=0
for L,R,w in Query:
    while(i<=R):
        update(c[i],i)
        i+=1
    ans[w]=bit.cum(L,R+1)

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

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=list(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    li=[list(map(lambda x:int(x)-1,read().split()))+[i] for i in range(Q)]
    Query=[(li[i][0],li[i][1],i) for i in range(Q)]
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
read=sys.stdin.buffer.readline

class BIT:
    def __init__(self,N):
        self.N=N
        self.bit=[0]*N
    def add(self,a,w):
        x=a
        while(x<self.N):
            self.bit[x]+=w
            x|=x+1
    def get(self,a):
        ret,x=0,a-1
        while(x>=0):
            ret+=self.bit[x]
            x=(x&(x+1))-1
        return ret
    def cum(self,l,r):
        return self.get(r)-self.get(l)

def main():
    def update(x,i):
        if good[x]==-1:
            good[x]=i
            bit.add(i,1)
        else:
            bit.add(good[x],-1)
            good[x]=i
            bit.add(good[x],1)
        return
    
    N,Q=map(int,read().split())
    c=tuple(map(int,read().split()))
    Query=[]
    for i in range(Q):
        l,r=map(lambda x:int(x)-1,read().split())
        Query.append((l,r,i))
    Query.sort(key=lambda x:x[1])
    ans=[-1]*Q
    good=[-1]*(N+1)
    bit=BIT(N)

    i=0
    for L,R,w in Query:
        while(i<=R):
            update(c[i],i)
            i+=1
        ans[w]=bit.cum(L,R+1)

    print(*ans,sep='\n')
    return
    
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.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))

def bucket_sort(A, M, key):
    from itertools import accumulate

    N = len(A)
    C = [0] * (M+1)
    res = [()] * N
    for i in range(N):
        C[A[i][key]] += 1
    C = list(accumulate(C))

    for i in range(N-1, -1, -1):
        res[C[A[i][key]]-1] = A[i]
        C[A[i][key]] -= 1
    return res

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))
events = bucket_sort(events, N, 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:
class BIT:
    # 1-indexed
    def __init__(self, n):
        self.size = n + 1
        self.bit = [0] * self.size

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

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

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

Submission status: Accepted

Solution code:
import sys


class BinaryIndexedTree():
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__node = [0] * (self.__n + 1)
        self.__data = [0] * (self.__n + 1)

        S = [0] * (self.__n + 1)
        for i in range(self.__n):
            S[i + 1] = S[i] + A[i]

        for i in range(1, self.__n + 1):
            self.__data[i] = A[i - 1]
            self.__node[i] = S[i] - S[i - (i & -i)]

    def add(self, i, v):
        self.__data[i] += v
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        if i == j:
            return self.__data[i]
        else:
            return self.sum(j) - self.sum(i - 1)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))

    P = [[] for _ in range(N)]
    for i, c in enumerate(C):
        P[c - 1].append(i)

    right = [0] * N
    for p in P:
        if len(p):
            right[p.pop()] = 1
    BIT = BinaryIndexedTree(right)

    query = [[] for _ in range(N)]
    for i, s in enumerate(sys.stdin.readlines()):
        l, r = map(int, s.split())
        query[r - 1].append((l - 1, i))

    ans = [None] * Q

    cur = N - 1
    for r, q in enumerate(reversed(query)):
        r = (N - 1) - r
        while q:
            l, i = q.pop()
            while r < cur:
                c = C[cur] - 1
                p = P[c]
                if len(p):
                    BIT.add(p.pop() + 1, 1)
                cur -= 1
            tmp = BIT.get(l + 1, r + 1)
            ans[i] = tmp

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys


class BinaryIndexedTree():
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__node = [0] * (self.__n + 1)
        self.__data = [0] * (self.__n + 1)

        S = [0] * (self.__n + 1)
        for i in range(1, self.__n + 1):
            S[i] = S[i - 1] + A[i - 1]
            self.__data[i] = A[i - 1]
            self.__node[i] = S[i] - S[i - (i & -i)]

    def add(self, i, v):
        self.__data[i] += v
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        if i == j:
            return self.__data[i]
        else:
            return self.sum(j) - self.sum(i - 1)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))

    P = [[] for _ in range(N)]
    for i, c in enumerate(C):
        P[c - 1].append(i)

    right = [0] * N
    for p in P:
        if len(p):
            right[p.pop()] = 1
    BIT = BinaryIndexedTree(right)

    query = [[] for _ in range(N)]
    for i, s in enumerate(sys.stdin.readlines()):
        l, r = map(int, s.split())
        query[r - 1].append((l - 1, i))

    ans = [None] * Q

    cur = N - 1
    for r, q in enumerate(reversed(query)):
        r = (N - 1) - r
        while q:
            l, i = q.pop()
            while r < cur:
                c = C[cur] - 1
                p = P[c]
                if len(p):
                    BIT.add(p.pop() + 1, 1)
                cur -= 1
            tmp = BIT.get(l + 1, r + 1)
            ans[i] = tmp

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,q = map(int,input().split())
c = tuple(map(int,input().split()))
qs = [[] for _ 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.num=n
        self.dat=[0]*(self.num+1)
        self.depth=n.bit_length()
    
    def add(self,i,x):
        i+=1
        while i<=self.num:
            self.dat[i]+=x
            i+=i&-i
    
    def sum(self,i):
        i+=1
        s=0
        while i>0:
            s+=self.dat[i]
            i-=i&-i
        return s
    
    def lower_bound(self,x):
        sum_=0
        pos=0
        for i in range(self.depth,-1,-1):
            k=pos+(1<<i)
            if k<=self.num and sum_+self.dat[k]<x:
                sum_+=self.dat[k]
                pos+=1<<i
        return pos, sum_

ps = [-1 for _ in range(n)]
pi = [-1 for _ in range(n+1)]
for i in range(n):
  l = pi[c[i]]
  if l != -1:
    ps[l] = i
  pi[c[i]] = i
    
d = BIT(n)
ans = [0 for _ in range(q)]
for x in range(n-1,-1,-1):
  if ps[x] != -1:
    d.add(ps[x],1)
  for r,i in qs[x]:
    ans[i] = (r-x+1)-d.sum(r)

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

Submission status: Accepted

Solution code:
import sys


class BinaryIndexedTree():
    '''
    1-indexed
    '''
    def __init__(self, A):
        self.__n = len(A)
        self.__node = [0] * (self.__n + 1)
        self.__data = [0] * (self.__n + 1)

        S = [0] * (self.__n + 1)
        for i in range(self.__n):
            S[i + 1] = S[i] + A[i]

        for i in range(1, self.__n + 1):
            self.__data[i] = A[i - 1]
            self.__node[i] = S[i] - S[i - (i & -i)]

    def add(self, i, v):
        self.__data[i] += v
        while i <= self.__n:
            self.__node[i] += v
            i += i & -i

    def sum(self, i):
        ''' [1, i]の和
        '''
        rst = 0
        while i > 0:
            rst += self.__node[i]
            i -= i & -i
        return rst
    
    def get(self, i, j):
        '''[i, j]の和
        '''
        if i == j:
            return self.__data[i]
        else:
            return self.sum(j) - self.sum(i - 1)


def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))

    P = [[] for _ in range(N)]
    for i, c in enumerate(C):
        P[c - 1].append(i)

    right = [0] * N
    for p in P:
        if len(p):
            right[p.pop()] = 1
    BIT = BinaryIndexedTree(right)

    query = [[] for _ in range(N)]
    for i in range(Q):
        l, r = map(int, sys.stdin.readline().split())
        query[r - 1].append((l - 1, i))

    ans = [None] * Q

    cur = N - 1
    for r, q in enumerate(reversed(query)):
        r = (N - 1) - r
        while q:
            l, i = q.pop()
            while r < cur:
                c = C[cur] - 1
                # BIT.update(cur + 1, 0)
                p = P[c]
                if len(p):
                    BIT.add(p.pop() + 1, 1)
                cur -= 1
            tmp = BIT.get(l + 1, r + 1)
            ans[i] = tmp

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import numpy as np
from sys import exit, stdin
import copy
from collections import deque, Counter


class BIT:
    def __init__(self, a=0):
        self.n = a
        self.d = [0] * (a + 1)

    def add(self, i, x=1):
        i += 1
        while i <= self.n:
            self.d[i] += x
            i += i & (-i)

    def sum(self, *i):
        if len(i) == 1:
            x = 0
            tmp = i[0] + 1
            while tmp:
                x += self.d[tmp]
                tmp -= tmp & (-tmp)
            return x
        else:
            return sum(self, i[1] - 1) - sum(self, i[0] - 1)


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

app = [-1] * (N + 1)
ps = [[] for _ in range(N)]
for i in range(N):
    tmp = app[C[i]]
    if tmp != -1:
        ps[tmp].append(i)
    app[C[i]] = i

qs = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, stdin.readline().split())
    l -= 1
    r -= 1
    qs[l].append(copy.deepcopy([r, i]))

ans = [0] * Q
d = BIT(N)
for x in range(N - 1, -1, -1):
    for y in ps[x]:
        d.add(y, 1)
    for p in qs[x]:
        r = p[0]
        i = p[1]
        ans[i] = (r - x + 1) - d.sum(r)

for re in ans:
    print(re)

Submission status: Accepted

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

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

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.elem[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.elem[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.elem[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.elem[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))

class RangeSet:
    """ 与えられた数列の区間内の種類数を求める """
    def __init__(self, n, array, query):
        """
        :param n: 要素数
        :param array: 整数で種類付けされた数列
        """
        self.n = n
        self.BIT = Bit(self.n)
        self.lastAppeared = [-1]*(self.n + 1)
        self.array = []
        self.query = []
        for i, c in enumerate(array):
            self.array.append(c)
            self.lastAppeared[c] = i
        for i, lr in enumerate(query):
            l, r = lr
            l -= 1
            r -= 1
            self.query.append((l,r,i))
        self.query.sort(key=lambda x: x[1])
        for x in self.lastAppeared:
            if x != -1:
                self.BIT.add(x, 1)

    def solve(self):
        res = [0] * len(self.query)
        r0 = 0
        for l, r, i in self.query:
            for R in range(r0, r + 1):
                self.BIT.add(self.lastAppeared[self.array[R]], -1)
                self.lastAppeared[self.array[R]] = R
                self.BIT.add(R, 1)
            res[i] = self.BIT.get(l, r + 1)
            r0 = r
        return res

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

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((l,r))

RS = RangeSet(N, C, query)
res = RS.solve()
print(*res, sep="\n")