Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


class Segtree_op():
    # 単位元及び操作を設定して使うこと
    # queryでは、区間の(l, r)を指定する ex: (0, 5) => [0, 1, 2, 3, 4]
    # 特定の1点は (i, i+1)
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        return lch + rch
    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2

class BIT():
    # A1 ... AnのBIT(1-indexed)
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    # A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    # Ai += x O(logN)
    def update(self, idx, x):
        # print(idx)
        while idx <= self.n:
            # print(idx)
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)

def solve():
    n, q = getList()
    nums = getList()
    qs = []
    ans = [0 for i in range(q)]
    las = [0 for i in range(n+3)]
    qs_append = qs.append
    for i in range(q):
        ql, qr = getList()
        qs_append((ql, qr, i))

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


    st = BIT(n)
    tmpr = 0
    for qq in qs:
        l, r, id = qq
        # print(qq)
        if r > tmpr:
            for i in range(tmpr + 1, r + 1):
                cur = nums[i - 1]
                st.update(i, 1)
                # print("s")
                if las[cur] != 0:
                    st.update(las[cur], -1)
                las[cur] = i
                # print(r)
            tmpr = r
        # st.show()
        # print(st.query(r) - st.query(l-1), l, r)
        ans[id] = st.query(r) - st.query(l-1)


    # ans.sort(key=lambda x: x[1])
    for an in ans:
        print(an)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

Solution code:
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]
'''
from queue import PriorityQueue
n,k = ip()
x = ip()
pq = PriorityQueue()
for i in x:
    pq.put((-1)*i)
print(sorted(x,reverse=True))
for i in range(k):
    ele = abs(pq.get())
    print(ele)
    if ele%2:
        pq.put((-1)*(ele//2))
        pq.put((-1)*((ele//2) +1))
    else:
        pq.put((-1)*(ele//2))
        pq.put((-1)*(ele//2))
print(abs(pq.get()))
'''
#dt = {} for i in x: dt[i] = dt.get(i,0)+1
import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]

# Python3 code to find number of 
# distinct numbers in a subarray 
MAX = MAX = 1000001

# structure to store queries 
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]) 

# Driver Code 
if __name__ == "__main__": 
    n,q = ip()
    a = ip()
    queries = []
    for i in range(q):
        l,r = ip()
        queries.append(Query(l-1,r-1,i))
    queries.sort(key = lambda x: x.r) 
    answeringQueries(a, n, queries, q)

Submission status: Accepted

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

class Seg_sum():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 0
        self.func = lambda a,b : a+b

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

n,q = map(int,readline().split())
c = tuple(map(int,readline().split()))
lr = tuple(map(int,read().split()))
it = iter(lr)
lrq = [[] for _ in range(n)]
for i,l,r in zip(range(q),it,it):
    lrq[r-1].append((l-1,i))

st = Seg_sum([1]*(n+1))
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
for r in range(n):
    for l,i in lrq[r]:
        while(c_ind <= r):
            bef = before[c[c_ind]]
            if(bef!=-1):
                st.update(bef,0)
            before[c[c_ind]] = c_ind
            c_ind += 1

        ans[i] = st.query(l,r+1)

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

Submission status: Accepted

Solution code:
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# Python3 code to find number of  
# distinct numbers in a subarray 
MAX = 500001
  
# structure to store queries 
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]) 
  
# Driver Code 
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[]
for i in range(q):
  c,d=map(int,input().split())

  queries.append(Query(c-1,d-1,i))
queries.sort(key = lambda x: x.r) 
answeringQueries(a, n, queries, q)

Submission status: Accepted

Solution code:
from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for l, r, z in query:
    for i in range(right, r):
        num = appear[c[i]]
        if num != -1:
            bit.add(num+1, -1)
        appear[c[i]] = i
        bit.add(i+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

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

Submission status: Accepted

Solution code:
class BinaryIndexedTree():
    def __init__(self, N):
        self.N = N
        self.arr = [0] * (N+1)

    def query(self, i):
        ret = 0
        i += 1
        while i:
            ret += self.arr[i]
            lsb = i & (-i)
            i -= lsb
        return ret

    def add(self, i, v):
        i += 1
        while i < self.N+1:
            lsb = i & (-i)
            self.arr[i] += v
            i += lsb


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

    queries = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        queries[i] = [l, r, i]
    queries.sort(key=lambda x: x[1])

    bit = BinaryIndexedTree(N)
    numdupls = 0
    prevs = [-1] * N
    cur = 0
    ans = [-999] * Q
    for i in range(Q):
        l, r, qindex = queries[i]
        while cur < r:
            c = C[cur] - 1
            if prevs[c] != -1:
                bit.add(prevs[c], 1)
                numdupls += 1
            prevs[c] = cur
            cur += 1
        ans[qindex] = r-l+1 - (numdupls - bit.query(l-2))
#        print(ans, "l=", l, "r=", r, numdupls, bit.query(l-2))
    for i in range(Q):
        print(ans[i])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


class Bit:
    """1-indexed"""

    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


N, Q = map(int, input().split())
C = tuple(map(int, input().split()))
queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])

b = Bit(N)
last = [None] * (N + 1)

cur = 1
ans = [0] * Q
for l, r, i in queries:
    while cur <= r:
        if last[C[cur - 1]] is not None:
            b.add(last[C[cur - 1]], -1)
        last[C[cur - 1]] = cur
        b.add(cur, 1)
        cur += 1
    ans[i] = b.sum(r) - b.sum(l - 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

# Reference: https://www.geeksforgeeks.org/queries-number-distinct-elements-subarray/
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 1000001

# structure to store queries
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])


# This code is contributed by
# sanjeev2552


def main():
    N, Q = map(int, readline().split())
    C = list(map(int, readline().split()))
    (*LR,) = map(int, read().split())

    queries = [0] * Q
    for i, (l, r) in enumerate(zip(*[iter(LR)] * 2)):
        queries[i] = Query(l - 1, r - 1, i)

    queries.sort(key=lambda x: x.r)
    answeringQueries(C, N, queries, Q)

    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

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
 
    def __len__(self):
        return self.size

n, q = LI()
c = LI()
lr = [LI() + [i] for i in range(q)]
lr.sort(key=itemgetter(1))
last = [-1] * (n+1)
ans = [0]*q
BIT = BinaryIndexedTree(n+1)
R = 0
for l, r, i in lr:
    while R < r:
        if last[c[R]] >= 0:
            BIT.add(last[c[R]], -1)
        last[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:
import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans

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

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Idx = (L>>9&1).astype(np.bool)
    B[Idx] = L[Idx]>>9<<20|(1<<20)-R[Idx]
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Accepted

Solution code:
# Python3 code to find number of
# distinct numbers in a subarray
from sys import stdin,stdout
import sys
sys.setrecursionlimit(10**5)
MAX = 500001

def input():
    return stdin.readline().strip()
# structure to store queries
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])


# Driver Code
if __name__ == "__main__":
    n, q = map(int, input().split())
    a = [int(k) for k in input().split()]
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        queries.append(Query(l-1, r-1, i))
    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

# This code is contributed by
# sanjeev2552

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,q=map(int,input().split())
C=[int(i) for i in input().split()]
LR=[]
for i in range(q):
    l,r=map(int,input().split())
    LR.append((i,l,r))
LR.sort(key=lambda x:x[2])


LST=[0]*(n+1)
Ans=[0]*q

n_max=5*10**5+1
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)

def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s

def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT
cur=0
for i,l,r in LR:
    while cur<r:
        if LST[C[cur]]!=0:
            bitadd(BIT,LST[C[cur]],-1)
        LST[C[cur]]=cur+1
        bitadd(BIT,LST[C[cur]],1)
        cur+=1
    if l==1:
        Ans[i]=bitsum(BIT,r+1)
    else:
        Ans[i]=bitsum(BIT,r+1)-bitsum(BIT,l-1)
for ans in Ans:
    print(ans)

Submission status: Accepted

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

N, Q = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))

query = []

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

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

rt = 0
L = [None for _ in range(N)]
res = [0 for _ in range(Q)]
bit = [0 for _ in range(N + 1)]

for l, r, id in query:
    while rt < r:
        if L[C[rt]] is not None:
            idx = L[C[rt]] + 1
            while idx <= N:
                bit[idx] -= 1
                idx += idx & -idx
        L[C[rt]] = rt
        idx = rt + 1
        while idx <= N:
            bit[idx] += 1
            idx += idx & -idx
        rt += 1
    sr = 0
    sl = 0
    idx = r
    while idx:
        sr += bit[idx]
        idx -= idx & -idx
    idx = l
    while idx:
        sl += bit[idx]
        idx -= idx & -idx
    res[id] = sr - sl

print('\n'.join(map(str, res)))

Submission status: Accepted

Solution code:

def bitadd(a,w,bit): #aにwを加える(1-origin)
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): #ind 1～aまでの和を求める
 
    ret = 0
    x = a
    while x > 0:
        ret += bit[x]
        x -= x & (-1 * x)
    return ret

from sys import stdin
N,Q = map(int,stdin.readline().split())

c = list(map(int,stdin.readline().split()))
last = [1] * (N+1)

li = [ [] for i in range(N+2)]
ans = [None] * Q
for i in range(Q):
    L,R = map(int,stdin.readline().split())
    L += 1
    R += 1
    li[R].append((L,i))

BIT = [0] * (N+2)
bitadd(1,N,BIT)

for i in range(N):

    nc = c[i]
    lastind = last[nc]
    last[nc] = i+2

    bitadd(lastind,-1,BIT)
    bitadd(i+2,1,BIT)

    for l,qind in li[i+2]:
        ans[qind] = bitsum(i+2,BIT) - bitsum(l-1,BIT)

print (*ans)

Submission status: Accepted

Solution code:
"""
Binary indexed tree
0-indexed, 関数は閉区間
0からの区間加算、1点更新
"""
class BIT: #0-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth
#        self.element = [0]*(n+1)
    def get_sum(self, i): #a_0 + ... + a_{i} #閉区間
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,r): #a_l + ... + a_r 閉区間
        return self.get_sum(r) - self.get_sum(l-1) 
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        # self.element[i] += x
    #def get(self,i): return element[i]        
    def bisect_left(self,w):
        #和が w 以上になる最小の index
        #w が存在しない場合 self.size を返す
        if w <= 0: return 0
        x,k = 0,self.n0
        for _ in range(self.depth):
            k >>= 1
            if x+k <= self.size and self.tree[x+k] < w:
                w -= self.tree[x+k]
                x += k
        return x

# coding: utf-8
# Your code here!
import sys
readline = sys.stdin.readline
read = sys.stdin.read

n,Q = [int(i) for i in readline().split()]
a = [int(i) for i in readline().split()]
q = [[int(i) for i in readline().split()]+[j] for j in range(Q)]


q.sort(key = lambda x: x[1])
last = [-1]*(n+1)
ans = [0]*Q
idx = 0
B = BIT(n+1)
for i in range(n):
    c = a[i]
    if last[c] != -1:
        B.add(last[c],-1)
    last[c] = i
    B.add(i,1)

    while idx < Q and q[idx][1] <= i+1:
        ans[q[idx][2]] = B.query(q[idx][0]-1,q[idx][1]-1)
        idx += 1
    
print(*ans,sep="\n")

Submission status: Accepted

Solution code:
def main():
    import sys
    my_input = sys.stdin.readline
    N, Q = map(int, my_input().split())
    A = list(map(int, my_input().split()))

    MAX_A = 5 * 10 ** 5
    query = []
    for q in range(Q):
        l, r = map(int, my_input().split())
        query.append((l, r, q))

    class BinaryIndexedTree:
        def __init__(self, n):
            self.size = n
            self.bit = [0] * (n + 1)

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

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

        def reset(self):
            self.bit = [0] * (self.size + 1)


    BIT = BinaryIndexedTree(N)
    X = [-1] * (MAX_A + 1)
    for i, a in enumerate(A, start=1):
        X[a] = i
    for x in X:
        if x == -1:
            continue
        BIT.add(x, 1)

    ans = [-1] * Q
    query.sort(key=lambda x: x[1])

    mr = 0
    for l, r, i in query:
        while mr < r:
            mr += 1
            BIT.add(X[A[mr - 1]], -1)
            X[A[mr - 1]] = mr
            BIT.add(mr, 1)
        ans[i] = BIT.sum(r) - BIT.sum(l - 1)

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np


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

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

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

    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i in range(q):
        segments.append((rrr[i], 1, lll[i], i))

    segments.sort()
    bit = np.zeros(n + 2, dtype=np.int64)
    ans = np.zeros(q, dtype=np.int64)

    for r, tp, l, i in segments:
        if tp == 0:
            bit_add(bit, n + 2, l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit_sum(bit, r + 2) - bit_sum(bit, l + 1))
    return ans


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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class SegTree:
  def segfunc(self, x, y):
    return x + y
  def __init__(self, n, ide_ele, init_val):
    #####単位元######
    self.ide_ele = ide_ele
    #num:n以上の最小の2のべき乗
    self.num = 2 ** (n - 1).bit_length()
    self.seg = [self.ide_ele] * 2 * self.num
    #set_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]) 
  def update(self, k, x):
    k += self.num - 1
    self.seg[k] = x
    while k + 1:
      k = (k - 1) // 2
      self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2]) 
  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
qs = []
for i in range(Q):
  l, r = map(int, input().split())
  qs.append((l, r, i))
qs.sort(key = lambda x: x[1])
last = [0] * (N + 1)
fwk = SegTree(N + 1, 0, last)
for i in range(qs[0][1]): last[a[i]] = i + 1
for x in last:
  if x: fwk.update(x, fwk.query(x, x + 1) + 1)
#print(last)
res = [0] * Q
rlast = qs[0][1]
for l, r, i in qs:
  #print(l, r)
  if rlast == r:
    res[i] = fwk.query(l, r + 1)
  else:
    for x in range(rlast, r):
      if last[a[x]]: fwk.update(last[a[x]], fwk.query(last[a[x]], last[a[x]] + 1) - 1)
      fwk.update(x + 1, fwk.query(x + 1, x + 2) + 1)
      last[a[x]] = x + 1
    rlast = r
    res[i] = fwk.query(l, r + 1)
for r in res: print(r)