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
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.buffer.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A):
        n = 1 << (len(A) - 1).bit_length()
        tree = [0] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = tree[i << 1] + tree[i << 1 | 1]
        self._n = n
        self._tree = tree

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._tree[i << 1] + self._tree[i << 1 | 1]

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = 0
        while l < r:
            if l & 1:
                l_val = l_val + self._tree[l]
                l += 1
            if r & 1:
                r -= 1
                r_val = self._tree[r] + r_val
            l >>= 1
            r >>= 1
        return l_val + r_val


def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))

    A = [0] * n
    next = [-1] * n
    used = [-1] * n
    for i in range(n - 1, -1, -1):
        c = C[i]
        A[i] = 1
        if used[c] != -1:
            next[i] = used[c]
            A[used[c]] = 0
        used[c] = i

    tree = SegmentTree(A)
    queries = [[] for _ in range(n)]
    for i in range(q):
        l, r = map(int, input().split())
        queries[l - 1].append((r, i))

    ans = [0] * q
    for l in range(n):
        for r, i in queries[l]:
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)

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

Submission status: Accepted

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

class BIT():

    def __init__(self, length_or_list, func, e):
        self.func = func
        self.e = e
        if isinstance(length_or_list, int):
            self.n = length_or_list + 1
            self.data = [self.e] * self.n
        else:
            self.n = len(length_or_list) + 1
            self.data = [self.e] + length_or_list
            for i in range(1, self.n):
                self.data[i + (i & -i)] = self.func(self.data[i + (i & -i)], self.data[i])        

    def point_append(self, index, delta):
        index += 1
        while index < self.n:
            self.data[index] = self.func(self.data[index], delta)
            index += index & -index
        
    def prefix_folded(self, end):
        res = 0
        while end > 0:
            res = self.func(res, self.data[end])
            end -= end & -end
        return res


N, Q = map(int, input().split())
cs = list(map(int, input().split()))
lrs = [tuple(map(int, input().split())) for _ in range(Q)]

#クエリを終了位置rでソート。
ilrs = sorted(((i, l-1, r-1) for i, (l, r) in enumerate(lrs)), key = lambda t: t[2])

#重複を区間としてし、終了位置でソートされた状態で列挙。
duplicates = []
indices = [-1 for _ in range(N+1)]
for i, c in enumerate(cs):
    if indices[c] != -1:
        duplicates.append((indices[c], i))
    indices[c] = i

#あとは平面走査と呼ばれる探査
ilrs.reverse()
duplicates.reverse()
starts = BIT(N, add, 0)
ans = [-1] * Q
for i in range(N):
    if duplicates and duplicates[-1][1] == i:
        dupstart, _ = duplicates.pop()
        starts.point_append(dupstart, 1)
    while ilrs[-1][2] == i:
        ans_i, l, r = ilrs.pop()
        ans[ans_i] = (r - l + 1) - (starts.prefix_folded(r + 1) - starts.prefix_folded(l))
        if not ilrs:
            break
    else:
        continue
    break

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

Submission status: Accepted

Solution code:
import sys
 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()
 
def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])
 
    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])
 
main()

Submission status: Accepted

Solution code:
# 解説の解法はAtCoder expressみたいな二次元累積和っぽい考え方を平面走査とBIT(セグ木)で高速化
# ここではとりあえず遅延セグ木を用いてけんちょんさんの解法を投げてみる https://drken1215.hatenablog.com/entry/2019/01/01/234400
# 遅延セグ木がTLEしたので,BITで...


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)  # bitは(1based indexっぽい感じなので)

    def init(self, ls):
        assert len(ls) <= self.n
        # lsをbitの配列に入れる
        for i, x in enumerate(ls):  # O(n log n 掛かりそう)
            self.add(i, x)

    def add(self, i, x):
        '''i番目の要素にxを足し込む'''
        i += 1  # 1 based idxに直す
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        '''[i,j)の区間の合計を取得'''
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        '''[,i)の合計を取得'''
        # 半開区間なので i+=1しなくていい
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret


class RangeAddBIT:  # range add query
    # [l,r)にxを加算する
    # [0,[l,r), i)のとき→bit.sum(i)+(rx-lx) (iによらない)
    # [0,[l,i),r)のとき→bit.sum(i)+(ix-lx)
    # [0,i),[l,r)のとき→bit.sum(i) (iによらない)
    # を加算できれば良い。bit.sum(i)が0だと見立てるとわかりやすいかも？
    # 場合分け2つ目における1項目をbit1,2項目をbit2とする
    def __init__(self, n: int):
        self.n = n
        self.bit1 = BIT(n)  # bit1.sum(i)*iで xiを達成したい部分 imos方的に使う
        self.bit2 = BIT(n)  # bit2.sum(i)で -xlを達成したい部分が手に入る。 r<iで区間加算後の和に相当する

    def add(self, l: int, r: int, x):
        '''[l,r)の要素にxを足し込む'''
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x * l)
        self.bit2.add(r, x * r)

    def sum(self, l, r):
        '''[l,r)の区間の合計を取得'''
        return self._sum(r) - self._sum(l)

    def _sum(self, i: int):
        '''[,i)の合計を取得'''
        return self.bit1._sum(i) * i + self.bit2._sum(i)


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd
N, Q = ints()
C = ints()
L, R = read_col(Q)
query = defaultdict(lambda: list())  # lごとのqueryを格納しておく
for i, (l, r) in enu(zip(L, R)):
    query[r].append((l - 1, i))

segtree = RangeAddBIT(N + 10)  # l-rまでの種類数を格納(rを広げながら更新していく)
idxprev = defaultdict(lambda: -1)  # 各色の前に出現したidx [prevの位置+1,再出現の位置+1)に区間加算する

ans = [-1] * Q
r_now = 0  # 現在の考慮する位置
for r in sorted(query.keys()):
    for j in range(r_now, r):
        prev = idxprev[C[j]]
        segtree.add(prev + 1, j + 1, 1)
        idxprev[C[j]] = j
    r_now = j
    for l, i in query[r]:
        ans[i] = segtree.sum(l, l + 1)
print(*ans, sep='\n')

# TLEなんですけど...

Submission status: Accepted

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

class BIT():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        self.UNITY_SUM = 0
        self.dat = [[self.UNITY_SUM for i in range(n + 1)] for j in range(2)]
    
    def sub_ADD(self, p, a, x):
        i = a
        while i < len(self.dat[p]):
            self.dat[p][i] = self.dat[p][i] + x
            i += i & -i
    
    def ADD(self, a, b, x):
        self.sub_ADD(0, a, x * -(a - 1))
        self.sub_ADD(1, a, x)
        self.sub_ADD(0, b, x * (b - 1))
        self.sub_ADD(1, b, x * (-1))
    
    def sub_SUM(self, p, a):
        res = self.UNITY_SUM
        i = a
        while i > 0:
            res += self.dat[p][i]
            i -= i & -i
        return res
    
    def SUM(self, a, b):
        return self.sub_SUM(0, b - 1) + self.sub_SUM(1, b - 1) * (b - 1) - self.sub_SUM(0, a - 1) - self.sub_SUM(1, a - 1) * (a - 1)
    
    def PRINT(self):
        for i in range(1, len(self.dat[0])):
            print(self.SUM(i, i + 1), end = "")
            print(",", end = "")
        print()

def main():
    N, Q = map(int,readline().split())
    C = list(map(int,readline().split()))  #対象のリスト
    S = sys.stdin.readlines()
    lefts = [0] * Q
    rights = [0] * Q
    ids = [0] * Q
    for i in range(Q):
        lefts[i], rights[i] = map(int,S[i].split())
        lefts[i] -= 1
        ids[i] = i
    
    ids = sorted(ids, key=lambda x: rights[x])

    bit = BIT(N+5)
    prev = [-1] * 1100000
    res = [0] * Q
    r = 0
    for i in ids:
        while r < rights[i]:
            bit.ADD(prev[C[r]]+2, r+2, 1)
            prev[C[r]] = r
            r += 1
        tmp = bit.SUM(lefts[i]+1, lefts[i]+2)
        res[i] = max(res[i], tmp)
    for i in range(Q):
        print(res[i])

main()

Submission status: Accepted

Solution code:
def main(N,Q,C,LR,A):
    data=[0]*(N+1)
    def add(i,x):
        i+=1
        while i<=N:
            data[i]+=x
            i+=i&-i
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[A[q]][1]==i+1:
            a[A[q]]=sum(LR[A[q]][0]-1,LR[A[q]][1])
            q+=1
    return a

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

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

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

def input(): return sys.stdin.buffer.readline()
N,Q=map(int,input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
LR=np.array(sys.stdin.buffer.read().split(),dtype=np.int64).reshape(Q,2)
A=np.argsort(LR[:,1])

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

Submission status: Accepted

Solution code:
NN = 19
XX = [0] * (2**(NN+1)-1)

def addvalue(j, x):
    i = 2**NN + j - 1
    while i >= 0:
        XX[i] += x
        i = (i-1) // 2

def rangesum(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    s = 0
    while l < r:
        if l%2:
            s += XX[l-1]
            l += 1
        if r%2:
            r -= 1
            s += XX[r-1]
        l >>= 1
        r >>= 1
    return s

N, Q = map(int, input().split())
C = [int(a) - 1 for a in input().split()]
X = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    X[r-1].append((l - 1, i))
last = [-1] * N
ANS = [-1] * Q
addvalue(1, N)
for r in range(N):
    c = C[r]
    addvalue(last[c] + 2, -1)
    addvalue(r + 2, 1)
    last[c] = r
    for l, i in X[r]:
        ANS[i] = rangesum(l + 2, 1 << NN)
    
print(*ANS, sep = "\n")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


class SegmentTreeSUM(object):  # 1-indexed [l,r)
    def __init__(self, size):
        self.len = 1 << (size-1).bit_length()
        # print(self.len)
        self.array = [0 for _ in range(2 * self.len)]

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i] = self.array[i] + x
            i >>= 1
        # print(self.array)

    def get(self, i):  # 0-indexed
        return self.array[i + self.len]

    def get_sum(self, l, r):  # 0-indexed
        L = l+self.len
        R = r+self.len
        ANS = 0

        while L < R:
            if L & 1:
                ANS = ANS + self.array[L]
                L += 1

            if R & 1:
                R -= 1
                ANS = ANS + self.array[R]
            L >>= 1
            R >>= 1

        return ANS


N, Q = na()
c_array = na()

tree = SegmentTreeSUM(N)


q_array = []
for i in range(Q):
    l, r = na()
    q_array.append([i, l-1, r])

q_array = sorted(q_array, key=lambda x: x[2])
ans = [0] * Q
last_idx = [-1] * (N+1)
q_idx = 0
for i, c in enumerate(c_array):
    tree.update(i, 1)
    if last_idx[c] != -1:
        tree.update(last_idx[c], -1)
    last_idx[c] = i
    while(q_idx < Q and q_array[q_idx][2] == (i+1)):
        idx, l, r = q_array[q_idx]
        ans[idx] = tree.get_sum(l, r)
        q_idx += 1


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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

n, q = map(int, sys.stdin.readline().split())
c = list(map(int, sys.stdin.readline().split()))
lr = [list(map(int, sys.stdin.readline().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
BIT = BinaryIndexedTree(n+1)
LastAppeared = [-1] * (n+1)
ans = [0] * q
R = 0
for l, r, i in lr:
    while R < r:
        if LastAppeared[c[R]] != -1:
            BIT.add(LastAppeared[c[R]], -1)
        LastAppeared[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1
    ans[i] = BIT.sum(r) - BIT.sum(l-1)

for i in ans:
    print(i)

Submission status: Accepted

Solution code:
from operator import itemgetter
N,Q = map(int, input().split())
C = [int(c) for c in input().split()]
L = [[int(l) for l in input().split()] for _ in range(Q)]

for i in range(Q):
    L[i].append(i)
M = pow(2, len(bin(N))-2)
BIT = [0]*(M+1)
L.sort(key=itemgetter(1))
memo = [0]*(N+1)

ans = [0]*Q
i = 1
j = 0
while i <= N:
    c = C[i-1]
    idx = i
    if i <= L[j][1]:
        if memo[c] > 0:
            k = memo[c]
            while k <= M:
                BIT[k] -= 1
                k += k&(-k)
        memo[c] = i
        while idx <= M:
            BIT[idx] += 1
            idx += idx&(-idx)
    if i == L[j][1]:
        cnt = 0
        n = L[j][1]
        while n > 0:
            cnt += BIT[n]
            n -= n&(-n)
        n = L[j][0]-1
        while n > 0:
            cnt -= BIT[n]
            n -= n&(-n)
        ans[L[j][2]] = cnt
        j += 1
        if j == Q:
            break
        elif L[j][1] == i:
            i -= 1
    i += 1

for a in ans:
    print(a)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    1-indexedの配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            raise ValueError("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i # i $ (-i)でiの最下位ビットのみ立った値を得る
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


def main():
    """
    区間の種類数を答える問題は典型みたい。
    https://hama-du-competitive.hatenablog.com/entry/2016/10/01/001418
    ポイントはクエリをrの昇順に整理しておくこと。
    玉の各種類ごとに、それが最後にどこで出現したかをBITに記録していく。
    """
    N, Q = map(int, input().split())
    C = [0] + list(map(int, input().split()))
    queri = []
    for q in range(Q):
        l, r = map(int, input().split())
        queri.append(r * 10**12 + l * 10**6 + q)
    queri.sort()
    # print("queri={}".format(queri))

    lastAppeared = [0] * (N + 1)  # lastAppeared[x] : 値 x が最後に出現した位置
    r0 = queri[0] // 10**12
    for i, c in enumerate(C):
        if i == 0: continue
        if i > r0: break
        lastAppeared[c] = i
    tree = BIT(N)
    for x in range(1, N + 1):
        if lastAppeared[x] != 0:
            tree.add(lastAppeared[x], 1)

    ans = [0] * Q
    pre_R = r0
    for x in queri:
        r, x = x // 10**12, x % 10**12
        l, q = x // 10**6, x % 10**6
        if r > pre_R:
            for i in range(pre_R + 1, r + 1):
                if lastAppeared[C[i]] != 0:
                    tree.add(lastAppeared[C[i]], -1)
                lastAppeared[C[i]] = i
                tree.add(i, 1)
        ans[q] = tree.get(l, r)
        pre_R = r
        # print("q={}, lastAppeared={}, ans={}".format(q, lastAppeared, ans[q]))

    for a in ans: print(a)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

Submission status: Accepted

Solution code:

class BinaryIndexedTree:
    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 bisearch_fore(self, l, r, x):
        """ 区間[l, r]を左から右に向かってx番目の値がある位置 """
        l_sm = self.sum(l - 1)
        ok = r + 1
        ng = l - 1
        while ng + 1 < ok:
            mid = (ok + ng) // 2
            if self.sum(mid) - l_sm >= x:
                ok = mid
            else:
                ng = mid
        if ok != r + 1:
            return ok
        else:
            return 1<<60

def resolve():
    N, Q = map(int, input().split())
    A = list(map(int, input().split()))


    pi = [-1] * (N + 1)  # 各数について最後に出てきた場所
    ps = [[] for i in range(N)]

    for i in range(N):
        l = pi[A[i]]
        if l != -1:
            ps[l].append(i)
        pi[A[i]] = i

    qs = [[] for i in range(N)]
    for i in range(Q):
        l, r = map(lambda x:int(x)-1, input().split())
        qs[l].append((r, i))

    BIT = BinaryIndexedTree(N + 1)
    ans = [0] * Q

    for x in range(N - 1, -1, -1):
        for y in ps[x]:
            BIT.add(y, 1)

        for r, i in qs[x]:
            ans[i] = (r - x + 1) - BIT.sum(r)

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



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[[]for _ in[0]*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=[0]*(n+1)
ans=[0]*q
for i,ai in enumerate(a):
  x=lastAppeared[ai-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[ai-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[[]for _ in[0]*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=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Submission status: Accepted

Solution code:
def main():
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[[]for _ in[0]*n]
  for i in range(q):
    l,r=x[n+i*2],x[n+i*2+1]
    l-=1
    r-=1
    queries[r].append((l,i))
  lastAppeared=[0]*n
  bit=[0]*(n+1)
  ans=[0]*q
  for i in range(n):
    x=lastAppeared[a[i]-1]+1
    while x<=n+1:
      bit[x-1]-=1
      x+=x&-x
    x=i+2
    while x<=n+1:
      bit[x-1]+=1
      x+=x&-x
    lastAppeared[a[i]-1]=i+1
    for l,ind in queries[i]:
      x=i+2
      while x:
        ans[ind]+=bit[x-1]
        x-=x&-x
      x=l+1
      while x:
        ans[ind]-=bit[x-1]
        x-=x&-x
  print(*ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
n,q,*x=map(int,open(0).read().split())
a=x[:n]
queries=[[]for _ in[0]*n]
for i in range(q):
  l,r=x[n+i*2],x[n+i*2+1]
  l-=1
  r-=1
  queries[r].append((l,i))
lastAppeared=[0]*n
bit=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]-1]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]-1]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Submission status: Accepted

Solution code:
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=[0]*(n+1)
ans=[0]*q
for i in range(n):
  x=lastAppeared[a[i]]+1
  while x<=n+1:
    bit[x-1]-=1
    x+=x&-x
  x=i+2
  while x<=n+1:
    bit[x-1]+=1
    x+=x&-x
  lastAppeared[a[i]]=i+1
  for l,ind in queries[i]:
    x=i+2
    while x:
      ans[ind]+=bit[x-1]
      x-=x&-x
    x=l+1
    while x:
      ans[ind]-=bit[x-1]
      x-=x&-x
print(*ans)

Submission status: Accepted

Solution code:
MAX = 1000001

import sys

input = sys.stdin.readline


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)