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

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class BitSum:
    def __init__(self, n):
        self.n = n + 1
        self.table = [0] * self.n

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

    def sum(self, i):
        i += 1
        res = 0
        while i > 0:
            res += self.table[i]
            i -= i & -i
        return res

n,q=MI()
cc=LI()
lri=[]
mx=500005

for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r-1,i))

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


last=[-1]*mx
st=BitSum(mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r+1):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    
    now=r+1
    ans[i]=st.sum(r)-st.sum(l-1)
print(*ans,sep="\n")

Solution (Python):
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        
        
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

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


def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        queries.append((i, l, r))
    queries.sort(key=itemgetter(2))

    ans = [0] * q
    
    last_visit = [-1] * (n + 1)
    query_counter = 0
    bit = BIT1(n)
    for i in range(n):
        if last_visit[c[i]] != -1:
            bit.add(last_visit[c[i]] + 1, -1)

        last_visit[c[i]] = i
        bit.add(i + 1, +1)

        while query_counter < q and queries[query_counter][2] == i:
            idx, l, r = queries[query_counter]
            ans[idx] = bit.sum(r + 1) - bit.sum(l)
            query_counter += 1

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline


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

        for i, j in enumerate(a):
            self.update(i, j)

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

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    if n>5*10**5 or q>5*10**5:
        a=1/0
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)

Solution (Python):
import sys
input = sys.stdin.readline


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

        for i, j in enumerate(a):
            self.update(i, j)

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

    def get(self, i):
        s = 0
        i += 1
        while i != 0:
            s = s + self.a[i]
            i -= i & (-i)
        return s


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split()))] for i in range(q)]
    que.sort(key=lambda x: x[1][1])
    ans = [0] * q

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            ans[que[j][0]] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    print(*ans)

Solution (Python):

import sys,math

from sys import stdin,stdout;mod=int(1e9 + 7);from statistics import mode
from collections import *;from math import ceil,floor,inf,factorial,gcd,log2,sqrt
ii1=lambda:int(stdin.readline().strip())
is1=lambda:stdin.readline().strip()
iia=lambda:list(map(int,stdin.readline().strip().split()))
isa=lambda:stdin.readline().strip().split()






MAX = 500001


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


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


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

def answeringQueries(arr, n, queries, q):

    bit = [0] * (n + 1)

    last_visit = [-1] * MAX

    ans = [0] * q

    query_counter = 0
    for i in range(n):
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        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
    for i in range(q):
        print(ans[i])

if __name__ == "__main__":
    n,q=iia()
    a=iia()
    queries=[]
    for i in range(q):
        aa,bb=iia()
        aa-=1
        bb-=1
        queries.append(Query(aa,bb,i))
    queries.sort(key = lambda x: x.r)
    answeringQueries(a, n, queries, q)

Solution (Python):
import sys
from collections import defaultdict, deque, Counter
import math


from bisect import bisect_left, bisect_right


sys.setrecursionlimit(1000000)


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():
    
    
    
    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():
    
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    
    def update(self, idx, x):
        
        while idx <= self.n:
            
            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
        
        if r > tmpr:
            for i in range(tmpr + 1, r + 1):
                cur = nums[i - 1]
                st.update(i, 1)
                
                if las[cur] != 0:
                    st.update(las[cur], -1)
                las[cur] = i
                
            tmpr = r
        
        
        ans[id] = st.query(r) - st.query(l-1)


    
    for an in ans:
        print(an)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    
    solve()

Solution (Python):

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()))
'''

import sys;input = sys.stdin.readline
inp,ip = lambda :int(input()),lambda :[int(w) for w in input().split()]



MAX = MAX = 1000001


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


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


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

def answeringQueries(arr, n, queries, q): 

	
	bit = [0] * (n + 1) 

	
	
	
	last_visit = [-1] * MAX

	
	ans = [0] * q 

	query_counter = 0
	for i in range(n): 

		
		
		if last_visit[arr[i]] != -1: 
			update(last_visit[arr[i]] + 1, -1, bit, n) 

		
		
		last_visit[arr[i]] = i 
		update(i + 1, 1, bit, n) 

		
		
		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

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


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)

Solution (Python):
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)

        
        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)))

Solution (Python):
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline


MAX = 500001
  

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

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

def query(idx, bit, n): 
    summ = 0
    while idx: 
        summ += bit[idx] 
        idx -= idx & -idx 
    return summ 
  
def answeringQueries(arr, n, queries, q): 
  
    
    bit = [0] * (n + 1) 
  
    
    
    
    last_visit = [-1] * MAX
  
    
    ans = [0] * q 
  
    query_counter = 0
    for i in range(n): 
  
        
        
        if last_visit[arr[i]] != -1: 
            update(last_visit[arr[i]] + 1, -1, bit, n) 
  
        
        
        last_visit[arr[i]] = i 
        update(i + 1, 1, bit, n) 
  
        
        
        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
  
    
    for i in range(q): 
        print(ans[i]) 
  

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)

Solution (Python):
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")

Solution (Python):
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))

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


if __name__ == "__main__":
    main()

Solution (Python):
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')

Solution (Python):
import sys

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




MAX = 1000001


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



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



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


def answeringQueries(arr, n, queries, q):

    
    bit = [0] * (n + 1)

    
    
    
    last_visit = [-1] * MAX

    
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        
        
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

        
        
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        
        
        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

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






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()

Solution (Python):


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)

Solution (Python):
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()

Solution (Python):


from sys import stdin,stdout
import sys
sys.setrecursionlimit(10**5)
MAX = 500001

def input():
    return stdin.readline().strip()

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



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



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


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

    
    
    
    last_visit = [-1] * MAX

    
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        
        
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

        
        
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        
        
        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

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



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)

Solution (Python):
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)

Solution (Python):
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)))

Solution (Python):

def bitadd(a,w,bit): 
 
    x = a
    while x <= (len(bit)-1):
        bit[x] += w
        x += x & (-1 * x)
 
def bitsum(a,bit): 
 
    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)

Solution (Python):
"""
Binary indexed tree
0-indexed, 関数は閉区間
0からの区間加算、1点更新
"""
class BIT: 
    def __init__(self, n):
        self.size = n
        self.tree = [0]*(n+1)
        self.depth = n.bit_length()
        self.n0 = 1<<self.depth

    def get_sum(self, i): 
        s = 0; i += 1
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def query(self,l,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
        
    
    def bisect_left(self,w):
        
        
        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



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")

Solution (Python):
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()