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: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

        #リストで初期化する
        def setL(self,init_val):
            #init_valは操作する数列
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res

    mod=10**9+7
    N,Q=MI()
    C=LI()
    for i in range(N):
        C[i]-=1
    
    rli=[]
    for i in range(Q):
        l,r,=MI()
        l-=1
        r-=1
        rli.append([r,l,i])
        
    rli.sort()
    seg=SegTree(N,0,lambda a,b: a+b)
    R=[-1]*N#各色ごとに最右がどこか保持する
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかseg木で管理
    """
    
    ans=[0]*Q
    now=0
    for ii in range(Q):
        r,l,i=rli[ii]
        while now<r:
            now+=1
            c=C[now]
            if R[c]!=-1:#前のものを削除
                old=R[c]
                seg.update(old,0)
            #最新を追加
            R[c]=now
            seg.update(now,1)
        ans[i]=seg.query(l,r+1)
        
    for i in range(Q):
        print(ans[i])
                
                
            
    
    

main()

Submission status: Wrong Answer

Solution code:
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

    def add(self, index, x):
        while index <= self.size:
            self.data[index] += x
            index += index & -index

    def prefix_sum(self, index):
        res = 0
        while index >= 1:
            res += self.data[index]
            index -= index & -index
        return res
    
    def interval_sum(self, left, right):
        return self.prefix_sum(right) - self.prefix_sum(left-1)

    def __getitem__(self, index):
        return self.sum(index) - self.sum(index-1)

    # def __setitem__(self, index, x):
    #     before = self.__getitem__(index)
    #     self.add(index, -before)
    #     self.add(index, x)

def main():
    from sys import stdin
    input = lambda: stdin.readline()
    LMIIS = lambda: list(map(int,input().split()))


    N,Q = LMIIS()
    # 1-indexedにするためリストの先頭に0を追加
    C = [0] + LMIIS()
    queries = []

    # 順番と一緒にクエリを保存
    for i in range(Q):
        l,r = map(int,input().split())
        queries.append((i,l,r))
    
    # rについてクエリをソート
    queries.sort(key=lambda x: x[2])

    # 玉の種類 -> 良い玉の場所
    good_ball_places = [0] * (N+1)

    # 場所 -> 良い玉が存在するなら1,しないなら0
    good_ball_exists = BinaryIndexedTree()

    #　玉の更新済み範囲
    k = 0
    # クエリの回答
    out = [0] * Q
    for order,l,r in queries:
        for i in range(max(k+1,l),r+1):
            # 位置iの玉の色
            color = C[i]
            # 色colorの良い玉の前の位置
            before = good_ball_places[color]
            # 色colorが区間内で既出なら、前の位置での存在を消去
            if l <= before:
                good_ball_exists.add(before,-1)
            
            # 色colorの良い玉の位置はi
            good_ball_places[color] = i
            # 位置iに良い玉が存在
            good_ball_exists.add(i,1)
        # 良い玉を更新した範囲
        k = r
        # [l,r]に存在する良い玉の数の合計
        out[order] = good_ball_exists.interval_sum(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

Submission status: Wrong Answer

Solution code:
from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[1])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        seg[i+num-1]=init_val[i]   
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 
    
def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0 
num = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r
    ans[index] = query(l,r+1)
for i in range(q):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
import numpy as np

N, Q = input().split()
cn = np.array(input().split(), np.int64)

for _ in range(int(Q)):
  i, j = input().split()
  if i == j:
    print(1)
  print(np.unique(cn[int(i)-1: int(j)]).size)

Submission status: Wrong Answer

Solution code:
class SegTreeLayer:
    def __init__(self, segsize, function, upper_layer=None, lower_layer=None):
        self.data = []
        self.segsize = segsize
        self.function = function
        self.upper_layer = upper_layer
        self.lower_layer = lower_layer

    def update(self, i, value):
        self.data[i] = value

        if not self.upper_layer: return
        v_upper = vi = self.data[i]
        
        j = i-1 if i&1 else i+1
        if j<len(self.data):
            vj = self.data[j]
            v_upper = self.function(vi, vj)
            
        self.upper_layer.update(i//2, v_upper)

    def query(self, ibgn, iend):
        if ibgn%self.segsize==0 and iend-ibgn==self.segsize:
            return self.data[ibgn//self.segsize]

        imid = (ibgn//self.segsize)*self.segsize + self.segsize//2
        if iend<=imid or imid<=ibgn: return self.lower_layer.query(ibgn, iend)
        return self.function(
            self.lower_layer.query(ibgn, imid),
            self.lower_layer.query(imid, iend)
        )

    def extend(self, add, fill):
        self.data.extend([fill]*add)
        ndata = len(self.data)
        ndata_upper_new = (ndata+1)//2 if ndata>1 else 0
        
        if not self.upper_layer and ndata_upper_new>0:
            self.upper_layer = SegTreeLayer(
                self.segsize*2, self.function, lower_layer=self)

        if self.upper_layer:
            ndata_upper_now = len(self.upper_layer.data)
            return self.upper_layer.extend(ndata_upper_new - ndata_upper_now, fill)

        return self

N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = sorted([[q]+list(map(int, input().split())) for q in range(Q)], key=lambda x:x[2])

bottom = SegTreeLayer(1, lambda x,y: x+y)
top = bottom.extend(N, 0)
exit()

I = [None]*(N+1)
i = 0
ans = [None]*Q
for q, l, r in LR:
    while i<r:
        bottom.update(i, 1)
        
        c = C[i]
        i_old = I[c]
        if i_old is not None: bottom.update(i_old, 0)
        
        I[c] = i
        i+=1
    ans[q] = top.query(l-1,top.segsize)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = []
    for e in E:
        if e[2] == -1:
            y_list.append(e[1])
            y_list.sort()
        else:
            ans = bisect.bisect_right(y_list, e[1])
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = [500005] * (2 * Q)
    for e in E:
        ans = bisect.bisect_right(y_list, e[1])
        if e[2] == -1:
            y_list[ans] = e[1]
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = [500005] * (2 * Q)
    for e in E:
        ans = bisect.bisect_right(y_list, e[1])
        if e[2] == -1:
            y_list[ans] = e[1]
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

Submission status: Wrong Answer

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = [500005] * Q
    for e in E:
        ans = bisect.bisect_right(y_list, e[1])
        if e[2] == -1:
            y_list[ans] = e[1]
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - ans

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
            self.p.sum(s) - self.q.sum(s) * s


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


def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = RangeUpdate(N)

    for i, a in enumerate(C, start=1):
        if Query[0][1] >= i:
            lastappend[a] = i
    for la in lastappend:
        if la != 0:
            bit.add(la, la, 1)
    pre = Query[0][1]
    ans = []
    for (le, ri), j in Query:
        if pre < N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, i, 1)
            pre = ri
        ans.append((j, bit.sum(le, ri)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class RangeUpdate:
    def __init__(self, n):
        self.p = Bit(n + 1)
        self.q = Bit(n + 1)

    def add(self, s, t, x):
        t += 1
        self.p.add(s, -x * s)
        self.p.add(t, x * t)
        self.q.add(s, x)
        self.q.add(t, -x)

    def sum(self, s, t):
        t += 1
        return self.p.sum(t) + self.q.sum(t) * t - \
            self.p.sum(s) - self.q.sum(s) * s


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


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0]*(N+1)
    bit = RangeUpdate(N)

    for i, a in enumerate(C, start=1):
        if Query[0][1] < i:
            break
        lastappend[a] = i
    for la in lastappend:
        if la != 0:
            bit.add(la, la, 1)
    pre = Query[0][1]
    ans = []
    for (le, ri), j in Query:
        if pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    bit.add(pre_i, pre_i, -1)
                lastappend[C[i-1]] = i
                bit.add(i, i, 1)
            pre = ri
        ans.append((j, bit.sum(le, ri)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
X.sort(key=lambda x: x[1])
for i, (l, r) in enumerate(X):
    for j in range(k + 1, r + 1):
        if last[C[j - 1]] > 0:
            bit.add(last[C[j - 1]], -1)

        bit.add(j, 1)
        last[C[j - 1]] = j

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

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

Submission status: Wrong Answer

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)
    ans = 0

    answers = np.empty(Q, np.int32)
    nl, nr = 0, 0
    for i in ind:
        pass
    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: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)
arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * 2**60 + l * 2**30 + i for r, l, i in zip(R, L, range(Q)))[::-1]
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2**60)
    l, i = divmod(li, 2**30)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)
mod = 2 ** 30
arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * mod * mod + l * mod + i for r, l, i in zip(R, L, range(Q)))[::-1]
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, mod * mod)
    l, i = divmod(li, mod)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)
mod=10**9+7
arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * mod * mod + l * mod + i for r, l, i in zip(R, L, range(Q)))[::-1]
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, mod * mod)
    l, i = divmod(li, mod)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]
L, R = LR[::2], LR[1::2]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted(r * (2 ** 40) + l * (2 ** 20) + i for r, l, i in zip(R, L, range(Q)))[::-1]
ans = [None] * Q
j = 0
for rli in RLI:
    r, li = divmod(rli, 2 ** 40)
    l, i = divmod(li, 2 ** 20)
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
exit()
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, Q = I[:2]
C = [0] + I[2:2 + N]
LR = I[2 + N:]


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


BIT = BinaryIndexedTree(500010)

arr = [5 * 10**5 + 4] * (5 * 10**5 + 5)
RLI = sorted((lr[1], lr[0], i) for i, lr in enumerate(zip(LR[::2], LR[1::2])))
exit()
ans = [None] * Q
j = 0
for r, l, i in RLI:
    for j in range(j + 1, r + 1):
        BIT.add(arr[C[j]], -1)
        arr[C[j]] = j
        BIT.add(j, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print('\n'.join(map(str, ans)))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from operator import add, itemgetter


class RMQ():
    
    def __init__(self, size, op=min, init_value=10**8):
        """初期化"""
        self.size = size
        self.op = op
        self.init_value = init_value
        n = 2 ** ((size-1).bit_length())
        treesize = n * 2
        st = [init_value] * treesize
        self.st = st
        self.offset = len(st) // 2

    @classmethod
    def from_array(cls, a, op=min, init_value=10**8):
        st = cls(len(a), op=op, init_value=init_value)
        for i, x in enumerate(a):
            st.update(i, x)
        return st

    def update(self, key, value):
        """値の更新"""
        k = self.offset + key
        self.st[k] = value
        k >>= 1
        while k > 0:
            self.st[k] = self.op(self.st[k * 2], self.st[k * 2 + 1])
            k >>= 1

    def _query_bottomup(self, a, b):
        """区間[a, b) に対する累積操作
        """
        a += self.offset
        b += self.offset - 1
        s = self.init_value
        while a < b:
            if a & 1:
                s = self.op(s, self.st[a])
                a += 1
            a >>= 1
            if not b & 1:
                s = self.op(s, self.st[b])
                b -= 1
            b >>= 1
        if a == b:
            s = self.op(s, self.st[a])
        return s

    def _query_topdown(self, a, b, k=1, l=0, r=-1):
        """区間[a, b) に対する累積操作
        k: 着目しているノード (1-indexed)
        l: 探索区間 st[l, r) の左端 (0-indexed)
        r: 探索区間 st[l, r) の右端 (0-indexed)
        """
        if r == -1:
            r = self.offset
        if r <= a or b <= l:
            return self.init_value
        if a <= l and r <= b:
            return self.st[k]
        mid = (l + r) // 2
        lv = self._query_topdown(a, b, k * 2, l, mid)
        rv = self._query_topdown(a, b, k * 2 + 1, mid, r)
        return self.op(lv, rv)

    def query(self, a, b):
        """区間[a, b) に対する累積操作"""
        if a > b:
            raise ValueError("a must be less than equal b.")
        return self._query_bottomup(a, b)


def read():
    N, Q = map(int, input().strip().split())
    C = list(map(int, input().strip().split()))
    # クエリ [l, r) とその順序を持っておく
    LRI = []
    for i in range(Q):
        l, r = map(int, input().strip().split())
        LRI.append((l-1, r, i))
    return N, Q, C, LRI


def solve(N, Q, C, LRI, INF=10**7):
    prev = [0 for i in range(N+1)]
    ans = [0 for i in range(Q)]
    
    rmq = RMQ(N, op=add, init_value=0)
    # Rの昇順にソート
    LRI.sort(key=itemgetter(1))
    r_prev = 0
    for l, r, i in LRI:
        for j in range(r_prev, r):
            c = C[j]
            # A[prev[c]] = 0
            if prev[c] != -1:
                rmq.update(prev[c], 0)
            prev[c] = j
            # A[j] = 1
            rmq.update(j, 1)
        r_prev = r
        ans[i] = rmq.query(l, r)

    for a in ans:
        print(a)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))