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: Time Limit Exceeded

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
    i8 = numba.int64
    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[:],i4[:],i4[:],i4[:],i4,i4)")
    cc.compile()

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    C = np.array([0] + list(map(int, input().split())), dtype=np.int32)
    LR = np.array(list(map(int, sys.stdin.read().split())), dtype=np.int32)
    L = LR[::2]
    R = LR[1::2]
    B = np.array([(l>>9<<20)|r for l, r in zip(L, R)], dtype=np.int32)
    Order = np.array(sorted(range(Q), key=lambda x: B[x]), dtype=np.int32)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}

ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0
for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(lambda n: int(n) - 1, rl().split()))
    
    init_val = [{ci} for ci in c]
    segfunc = lambda a, b: a | b
    seg_tree = SegmentTree(init_val, segfunc, set())
    
    ans = []
    for _ in range(Q):
        left, right = map(int, rl().split())
        left -= 1
        ans.append(len(seg_tree.query(left, right)))
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
for i in range(Q):
    value = []
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        if c[j - 1] not in value:
            value.append(c[j - 1])
    print(len(value))

Submission status: Time Limit Exceeded

Solution code:
import sys, math, collections
input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

sqrtN = math.sqrt(N)

query = []
result = [0] * M

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

query.sort(key=lambda x : (x[0] // sqrtN, x[1]))

s, e, n = query[0]
Cnt = collections.Counter()
ans = 0
for i in range(s, e + 1):
    Cnt[A[i]] += 1
    if Cnt[A[i]] == 1: ans += 1

result[n] = ans

for si, ei, i in query[1:]:
    while si < s:
        s -= 1
        Cnt[A[s]] += 1
        if Cnt[A[s]] == 1: ans += 1
    while si > s:
        Cnt[A[s]] -= 1
        if not Cnt[A[s]]: ans -= 1
        s += 1
    while ei > e:
        e += 1
        Cnt[A[e]] += 1
        if Cnt[A[e]] == 1: ans += 1
    while ei < e:
        Cnt[A[e]] -= 1
        if not Cnt[A[e]]: ans -= 1
        e -= 1
    result[i] = ans

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

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lr = [list(map(int,input().split())) for i in range(q)]
ans = [0]*q
for i in range(q):
  lr[i].append(i)
lr.sort(key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R,p in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[p] = bit.sum(L+1)
  cnt = R
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

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

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

M = int(N**0.5)
K = (N + M - 1) // M

query = []

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

query.sort(key = lambda x: (x[0] // M, x[1]))

lt, rt = 0, 0
S = [0 for _ in range(N)]
tmp = 0
res = [0 for _ in range(Q)]

for l, r, i in query:
    while lt > l:
        lt -= 1
        if S[C[lt]] == 0:
            tmp += 1
        S[C[lt]] += 1
    while rt < r:
        if S[C[rt]] == 0:
            tmp += 1
        S[C[rt]] += 1
        rt += 1
    while lt < l:
        if S[C[lt]] == 1:
            tmp -= 1
        S[C[lt]] -= 1
        lt += 1
    while rt > r:
        rt -= 1
        if S[C[rt]] == 1:
            tmp -= 1
        S[C[rt]] -= 1
    res[i] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
for i in range(Q):
    value = []
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        if value.count(c[j - 1]) == 0:
            value.append(c[j - 1])
    print(len(value))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

div = max(int(Q**.5), 1)
B = N // div

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1] ^ -(v[0]//B & 1)))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
def list_difference(list1, list2):
    result = list1.copy()
    for value in list2:
        if value in result:
            result.remove(value)

    return result

L=list()
N,Q=map(int,input().split())
c=list(map(int,input().split()))
for i in range(N):
  L.append(c[:i+1])
L.append([])
for i in range(Q):
  l,r=map(int,input().split())
  print(len(set(list_difference(L[r-1], L[l-2]))))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())

c = list(map(int, input().split()))


for i in range(Q):
    value = []
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        if value.count(c[j - 1]) == 0:
            value.append(c[j - 1])
    print(len(value))

Submission status: Time Limit Exceeded

Solution code:
import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

class segtree:
    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        """
        [q_left, q_right] (閉区間) の値を集計して返します。
        """

        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)

def concat(a,b):
    c = a.union(b)
    return c

def main():
    INF = 999999999999999999999999
    MOD = 10**9+7

    n,q = get_nums_l()
    C = get_nums_l()

    sg = segtree(n, concat, set())

    for i,c in enumerate(C):
        # log(sg)
        sg.update(i, {c})

    for i in range(q):
        l,r = get_nums_l()
        print(len(sg.get(l-1,r-1)))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
@numba.njit("i4[:](i4[:],i4[:],i4[:],i4[:],i4,i4)")
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

input = sys.stdin.readline
N, Q = map(int, input().split())
C = np.array([0] + list(map(int, input().split())), dtype=np.int32)
LR = np.array(list(map(int, sys.stdin.read().split())), dtype=np.int32)
L = LR[::2]
R = LR[1::2]
B = np.array([(l>>9<<20)|r for l, r in zip(L, R)], dtype=np.int32)
Order = np.array(sorted(range(Q), key=lambda x: B[x]), dtype=np.int32)
Ans = proc(C, L, R, Order, N, Q)
print("\n".join(map(str, Ans.tolist())))

Submission status: Time Limit Exceeded

Solution code:
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
queries.sort()
queries.append([10*20,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][0]==i:
    r,l,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

B = max(1, int(N**.5))

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1] ^ -(v[0]//B & 1)))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res


def main():
    n,q = map(int,ipt().split())
    c = [set([int(i)]) for i in ipt().split()]+[set()]

    def segfunc(x,y):
        return x|y

    ST = SegTree(c,segfunc,set())
    for i in range(q):
        l,r = map(int,ipt().split())
        print(len(ST.query(l-1,r)))

    return None

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
m, n = map(int, input().split())
lis = list(map(int, input().split()))
for lp in range(n):
    a, b = map(int, input().split())
    print(len(set(lis[a - 1:b])))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from os import path

if(path.exists('input.txt')):
    sys.stdin = open("input.txt","r")
    sys.stdout = open("output.txt","w")

n,q = map(int,input().split())
c = list(map(int,input().split()))
for i in range(0,q):
    count = 0
    seen = {}
    l,r = map(int,input().split())
    #print(c)
    seen = c[l-1:r]
    print(len(set(seen)))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r):
        l += self.n
        r += self.n
        s = self.one
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.b[r - 1])
            if l & 1:
                s = self.func(s, self.b[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return s


c = [int(i) for i in input().split()]
seg = SegmentTree([{i} for i in c], lambda x, y: x | y, set())
for _ in range(q):
    l, r = [int(i) for i in input().split()]
    print(len(seg.get_segment(l-1, r)))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

class BIT:
    '''
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()

    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret

    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)

    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_


def solve():
    n, q = nm()
    c = nl()
    g = [(i, *nl()) for i in range(q)]
    g.sort(key=lambda x: x[2])
    ans = [0]*q
    b = BIT(n + 10)
    last = [n + 5]*(n+1)
    cr = -1
    for i, l, r in g:
        l -= 1; r -= 1
        while cr < r:
            cr += 1
            b.bitadd(last[c[cr]], -1)
            last[c[cr]] = cr
            b.bitadd(cr, 1)
        ans[i] = b.bitsum(l, r+1)
    prn(ans)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
l = 0
r = 0

for _ in range(q):
    l, r = map(int, input().split())
    rangeQ = set(c[l-1:r])
    print(len(rangeQ))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip('\r\n')

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

B = max(1, int(N**.5))

Qs = []
for i in range(Q):
	l, r = map(lambda s: int(s)-1, input().split())
	Qs.append((l, r+1, i))

Qs.sort(key=lambda v: (v[0]//B, v[1]))

cnt = [0] * (N+1)
diff = 0

ans = [-1] * Q

left, right = 0, 0

def add(i):
	global cnt, diff
	x = C[i]
	cnt[x] += 1
	if cnt[x] == 1:
		diff += 1

def remove(i):
	global cnt, diff
	x = C[i]
	cnt[x] -= 1
	if cnt[x] == 0:
		diff -= 1

for l, r, i in Qs:
	while right < r:
		add(right)
		right += 1

	while r < right:
		right -= 1
		remove(right)

	while left < l:
		remove(left)
		left += 1

	while l < left:
		left -= 1
		add(left)

	ans[i] = diff

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

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
c=list(map(int,input().split()))
for i in range(Q):
  l,r=map(int,input().split())
  print(len(set(c[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

m, n = map(int, input().split())
lis = list(map(int, input().split()))
for lp in range(n):
    a, b = map(int, input().split())
    print(len(Counter(lis[a - 1:b]).keys()))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500005)
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().strip()

n, q = na()
a = na()
lasts = [-1] * (n+1)
rs = []
for i in range(n):
    if lasts[a[i]] != -1:
        rs.append((lasts[a[i]], i))
    lasts[a[i]] = i

rs.sort(key=lambda k: k[0])

qs = []
for i in range(q):
    u = na()
    qs.append((u[0]-1, u[1]-1, i))
qs.sort(key=lambda k: k[0])

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

ft = [0] * (n+10)
anss = [0] * q
p = len(rs)-1
for q in qs[::-1]:
    while p >= 0 and rs[p][0] >= q[0]:
        addfenwick(ft, rs[p][1], 1)
        p -= 1
    anss[q[2]] = q[1]-q[0]+1-sumfenwick(ft, q[1])

for v in anss:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
C = [0] + list(map(int, input().split()))
Ans = [0] * Q
sq = 1000
LR = list(map(int, sys.stdin.read().split()))
L = LR[::2]
R = LR[1::2]
B = [(l>>9<<20)|r for l, r in zip(L, R)]
Order = sorted(range(Q), key=lambda x: B[x])

pl = pr = 0
ans = 0
A = [0] * (N+1)
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
print("\n".join(map(str, Ans)))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
for i in range(q):
    l,r = map(int,input().split())
    print(len(set(c[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
while q:
    l, r = map(int, input().split())
    print(len(set(c[l-1:r])))
    q -= 1

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# 0-indexed BIT
class BIT:
    def __init__(self, li):
        self.n, self.data = len(li) + 1, [0] + li
        for i in range(1, self.n):
            if i + (i & -i) < self.n: self.data[i + (i & -i)] += self.data[i]

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

    # sum of [0, i)
    def acc(self, i):
        res = 0
        while i > 0:
            res += self.data[i]
            i -= i & -i
        return res

    # sum of [l, r)
    def get(self, l, r = None):
        if r is None: r = l+1
        return self.acc(r) - self.acc(l)


def main():
    N, Q = LI()
    C = LI()
    lr = sorted(enumerate(LIR(Q)), key=lambda x: x[1][1])
    rightmostIndex = [-1]*(N+1)
    tree = BIT([0]*N)
    left, right = 0, 0
    ans = [None] * Q

    for i, (l, r) in lr:
        while right < r:
            if rightmostIndex[C[right]] < 0:
                rightmostIndex[C[right]] = right
            else:
                tree.add(rightmostIndex[C[right]], -1)
                rightmostIndex[C[right]] = right
            tree.add(right, 1)
            right += 1

        ans[i] = tree.get(l-1, r)


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


if __name__ == '__main__':
    main()