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:
N, Q = map(int, input().split())
L = list(map(int, input().split()))

for i in range (0, Q):
	A, B = map(int, input().split())
	print(len(set(L[A-1:B])))

Submission status: Time Limit Exceeded

Solution code:
"""

最後に登場したindexで考える
l以下のやつを除く
最後に登場したindexをBITにいれる

bit[i] = 最後に登場したindexがiの色の数

"""

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

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

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

li = [ [] for i in range(N+2)]
ans = [None] * Q
for i in range(Q):
    L,R = map(int,input().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)

for i in ans:
    print (i)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split(" "))
clist = list(map(int, input().split(" ")))
for i in range(q):
  a,b = map(int, input().split(" "))
  clist_selected = clist[a-1:b]
  print(len(list(set(clist_selected))))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c =list(map(int,input().split()))
l=[0]*q
r=[0]*q
for i in range(q):
    l[i],r[i]=map(int,input().split())

for elem in zip(l,r):
    print(len(set(c[elem[0]-1:elem[1]])))

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[i] for i in range( l - 1, r ) )))

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:
# F

import numpy as np

n, q = map(int, input().split())
c_l = [int(x) for x in input().split()]
q_l = [[int(x) for x in input().split()] for y in range(q)]

a_l = [[0] * n for x in range(n)]
for i in range(n):
    for j in range(i, n):
        a_l[j][c_l[i] - 1] += 1

for i in range(q):
    _l, _r = q_l[i]
    _r_l = np.array(a_l[_r-1])
    if _l == 1:
        print(np.count_nonzero(_r_l > 0))
    else:
        _l_l = np.array(a_l[_l-2])
        _d_l = _r_l - _l_l
        print(np.count_nonzero(_d_l > 0))

Submission status: Time Limit Exceeded

Solution code:
# From: https://github.com/cheran-senthil/PyRival/blob/master/pyrival/data_structures/SegmentTree.py
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size : _size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)


import io
import os
from collections import defaultdict
from bisect import bisect_left, bisect_right


def solve(N, Q, C, LR):
    valToIndices = defaultdict(list)
    for i, c in enumerate(C):
        valToIndices[c].append(i)
    THRESHOLD = 500
    autoIncrement = defaultdict(lambda: len(autoIncrement))
    data = [0] * N
    for i, c in enumerate(C):
        if len(valToIndices[c]) < THRESHOLD:
            data[i] = 1 << autoIncrement[c]
    for k in list(valToIndices.keys()):
        if len(valToIndices[k]) < THRESHOLD:
            del valToIndices[k]
    segTree = SegmentTree(data, 0, lambda x, y: x | y)

    for l, r in LR:
        r += 1
        mask = segTree.query(l, r)
        lowFreqCount = 0
        while mask:
            lowFreqCount += mask & 1
            mask >>= 1
        highFreqCount = 0
        for x, indices in valToIndices.items():
            if bisect_right(indices, r - 1) - bisect_left(indices, l):
                highFreqCount += 1
        print(lowFreqCount + highFreqCount)


if __name__ == "__main__":
    input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) - 1 for x in input().split()] for i in range(Q)]  # 0-indexed
    solve(N, Q, C, LR)

Submission status: Time Limit Exceeded

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


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


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


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


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


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


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


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


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


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


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


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


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


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


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


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


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


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd


def lcm(a, b):
    # 最小公倍数
    g = gcd(a, b)
    return a // g * b


from bisect import bisect_left, bisect_right, insort_left

from functools import reduce


class SqrtDecomposedList:
    def __init__(self, ls, segfunc, identity_element):
        from math import sqrt, ceil
        from copy import copy
        self.f = segfunc  # queryのfunction
        self.ide = identity_element
        self.n = len(ls)
        self.ls = copy(ls)
        self.b = ceil(sqrt(self.n))
        self.bucket = [self.ide] * (self.b + 1)
        self._build()

    def _build(self):
        for d in range(self.b):
            self.bucket[d] = set(self.ls[(d * self.b):((d + 1) * self.b)])
            # reduce(
            #     self.f, self.ls[(d * self.b):((d + 1) * self.b)], self.ide)

    def __getitem__(self, idx):
        return self.ls[idx]

    def update(self, i, x):
        '''i番目の要素をxに更新する O(√n)'''
        self.ls[i] = x
        s = i // self.b * self.b
        t = s + self.b
        # print(i, self.b, i // self.b, s, t)
        self.bucket[i // self.b] = reduce(self.f,
                                          self.ls[s:t], self.ide)

    def query(self, l, r):
        '''半開区間[l,r)で指定すること O(√n)'''
        if r - l < 2 * self.b:
            return set(self.ls[l:r])
        l_bucket = (l - 1) // self.b + 1
        r_bucket = r // self.b  # 半開区間なのでこれでいい
        ret = reduce(self.f, self.bucket[l_bucket:r_bucket], self.ide)
        ret |= set(self.ls[l:(l_bucket * self.b)])
        ret |= set(self.ls[(r_bucket * self.b):r])

        return ret


def segfunc(x, y):  # セット
    return x | y


N, Q = ints()
C = ints()
# for c in ints():
#     C.append({c})

ls = SqrtDecomposedList(C, segfunc, set())
# セグ木か？面倒なので平方分割で
ans = []
for _ in range(Q):
    l, r = ints()
    # print(ls.bucket)
    # print(ls.query(l - 1, r))
    ans.append(len(ls.query(l - 1, r)))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from collections import Counter
n,q = map(int,input().split())
a = np.array(list(map(int,input().split())))
for i in range(q):
    l,r = map(int,input().split())
    c = Counter(a[l-1:r])
    print(len(c.keys()))

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree():  #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

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

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

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 = BinaryIndexedTree(N)

for l, r, id in query:
    while rt < r:
        if L[C[rt]] is not None:
            bit.add(L[C[rt]] + 1, -1)
        L[C[rt]] = rt
        bit.add(rt + 1, 1)
        rt += 1
    res[id] = bit.sum(r) - bit.sum(l)

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

Submission status: Time Limit Exceeded

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


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

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

    # print(qs)
    st = Segtree_op(n)
    tmpr = -1
    for qq in qs:
        l, r, id = qq
        # print(r, tmpr)
        if r > tmpr:
            for i in range(tmpr+1, r+1):

                cur = nums[i-1]
                st.update(i, 1)
                if las[cur] != -1:
                    st.update(las[cur], 0)
                las[cur] = i
            tmpr = r

        # print(las)
        # st.show()
        ans.append([st.query(0, r+1) - st.query(0, l), id])
        # print(st.query(0, r+1) - st.query(0, l), l, r)





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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N,Q = map(int,input().split())
C = list(map(int,input().split()))
LR = [tuple(map(int,input().split())) for i in range(Q)]

class SegTree:
    def __init__(self,arr,func,unit):
        self.func = func
        self.unit = unit
        n = 1
        while n < len(arr):
            n *= 2
        self.n = n
        nodes = [set() for _ in range(2*n-1)]
        nodes[n-1:n-1+len(arr)] = [set([a]) for a in arr]
        for i in range(n-2,-1,-1):
            nodes[i] = func(nodes[2*i+1],nodes[2*i+2])
        self.nodes = nodes

    def update(self,i,val):
        i += self.n-1
        self.nodes[i] = val
        while i >= 0:
            i = (i - 1) // 2
            self.nodes[i] = self.func(self.nodes[2*i+1], self.nodes[2*i+2])

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

segt = SegTree(C, lambda x,y:x|y, set())
ans = []
for l,r in LR:
    ans.append(len(segt.query(l-1,r)))
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
for i in range(q):
    start,finish=map(int,input().split())
    arr=[]
    ans=0
    for i in range(start-1,finish):
        if c[i] not in arr:
            arr.append(c[i])
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n, q = (int(i) for i in input().split())
nums = [0] # not a color
nums = [int(i) for i in input().split()]
nums_info = []
colors = defaultdict(lambda: 0)
for num in nums:
    colors[num] += 1
    nums_info.append(dict(colors))
#print(nums_info)
for _ in range(q):
    s, e = (int(i) for i in input().split())
    s -= 2
    e -= 1
    if s < 0:
        print(len(nums_info[e].keys()))
        continue
    if e - s == len(nums_info[e]) - len(nums_info[s]):
      	print(e - s)
      	continue
    count = 0
    for k, v in nums_info[e].items():
        if k in nums_info[s] and nums_info[s][k] == v:
            continue
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, Q = MI()
    c = [set([i]) for i in LI()]

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

    unit = set([])

    class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
        def __init__(self, N, seg_func, unit):
            self.N = N
            self.func = seg_func
            self.unit = unit
            self.tree = [self.unit] * (2 * self.N)

        def build(self, init_value):  # 初期値を[N,2N)に格納
            for i in range(self.N):
                self.tree[i + self.N] = init_value[i]
            for i in range(self.N - 1, 0, -1):
                self.tree[i] = self.func(self.tree[i << 1], self.tree[i << 1 | 1])

        def fold(self, L, R):  # [L,R)の区間取得
            L += self.N
            R += self.N
            vL = self.unit
            vR = self.unit
            while L < R:
                if L & 1:
                    vL = self.func(vL, self.tree[L])
                    L += 1
                if R & 1:
                    R -= 1
                    vR = self.func(self.tree[R], vR)
                L >>= 1
                R >>= 1
            return self.func(vL, vR)

    seg = SegTree(N, seg_func, unit)
    seg.build(c)

    for i in range(Q):
        l, r = MI()
        print(len(seg.fold(l - 1, r)))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((l,r,i))
queries.sort(key = lambda x:x[1])
curR = 0
#A1 ... AnのBIT(1-indexed)
BIT = [0]*(N+1)

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

#Ai += x O(logN)
def BIT_update(idx,x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return
for j in range(Q):
    l,r,i = queries[j]
    while curR < r:
        curR += 1
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
num=[]
def ap(n1,n2,n3):
    num.append([n1,n2,n3])
for i in range(q):
    l,r=map(int,input().split())
    ap(l,r,i)
num.sort(key=lambda x: x[1])
la=[-1]*max(c)
bit=[0]*n
ans=list(range(q))
num1=0
for i in range(q):
    n0=num[i][0]
    n1=num[i][1]
    for j in range(num1,n1):
        num2=c[j]
        num3=la[num2-1]
        if num3==-1:
            la[num2-1]=j
            bit[j]=1
        else:
            bit[num3]=0
            la[num2-1]=j
            bit[j]=1
    ans[num[i][2]]=sum(bit[n0-1:n1])
    num1=n1-1
for i in ans:
    print(i)

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

Solution code:
n, q = map(int, input().split())
list_number = []
answer = []
a = list(input().split())
for _ in range(q):
    l, r = map(int, input().split())
    for i in range(l - 1, r):
        list_number.append(a[i])
    answer.append(len(set(list_number)))
    list_number = []

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

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            
    def union(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            return self.tree[a]
        else:
            self.tree[a] = self.union(a*2) | self.union(a*2+1)
            return self.tree[a]
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        while y - x > 1:
            if x % 2 == 1:
                tl = tl | self.tree[x]
                x += 1
            if y % 2 == 0:
                tr = self.tree[y] | tr
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            print(len(tl|tr|self.tree[x]))
        else:
            print(len(tl|tr|self.tree[x]|self.tree[y]))
            
N,Q,*f = map(int, open(0).read().split())
c = f[:N]
lr = [f[N+i*2:N+i*2+2] for i in range(Q)]
if N == 1:
    for i in range(Q):
        print(1)
else:
    st = SegmentTree(c)
    st.union(1)
    for l,r in lr:
        st.query(l-1,r-1)

Submission status: Time Limit Exceeded

Solution code:
param_n, param_q = map(int, input().split())
list_str = str(input()).split(' ')

for i in range(param_q):
    param_a, param_b = map(int, input().split())
    print(len(list(set(list_str[param_a-1:param_b]))))

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())
colors = list(map(int, input().split()))
li = [[] for i in range(n)]

for j in range(n):
    c = colors[j]
    li[c-1].append(j)

for i in range(q):
    ans = 0
    l ,r = map(int, input().split())
    for j  in range(n):
        if len(li[j]) > 0:
            for k in range(len(li[j])):
                ban = li[j][k]
                if l-1 <=  ban <=  r-1:
                    ans += 1
                    break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=(int(x) for x in input().split())
c=[x for x in input().split()]

for _ in range(q):
  l,r=(int(x) for x in 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()))

INF = (1 << 31) - 1
SEG_LEN = n
SEG = [INF]*(SEG_LEN*2)


def update(i, x):
    i += SEG_LEN
    SEG[i] = 1 << (x-1)
    while i > 0:
        i //= 2
        SEG[i] = SEG[i*2] | SEG[i*2+1]


def find(left, right):
    left += SEG_LEN
    right += SEG_LEN
    ans = 0
    while left < right:
        if left % 2 == 1:
            ans |= SEG[left]
            left += 1
        left //= 2
        if right % 2 == 1:
            ans |= SEG[right-1]
            right -= 1
        right //= 2
    ans = format(ans, 'b').count('1')
    return ans


for i, x in enumerate(c):
    update(i, x)

for _ in range(q):
    l, r = map(int, input().split())
    print(find(l-1, r))

Submission status: Time Limit Exceeded

Solution code:
import collections

N, Q = (int(s) for s in input().rstrip().split())
colors = [int(s) for s in input().rstrip().split()]

for _ in range(Q):
  l, r = (int(s) for s in input().rstrip().split())
  print(len(set(colors[l - 1: r])))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

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

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

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


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+100))
j = 0
for i in range(n):
    if last[c[i]] != -1:
        bit.update(last[c[i]], -1)
    bit.update(i, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i) - bit.get(que[j][1][0]-1)
        j += 1
que.sort()
for i in que:
    print(i[-1])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
c = [0] * n
c = list(map(int,input().split()))
l = [0] * q
r = [0] * q
for i in range(q):
    l[i] , r[i] =  map(int,input().split())

for i in range(q):
    u = len(set(c[l[i]-1:r[i]]))
    print(u)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c =[]
l = []
ans = []
s = ''
c = [int(s) for s in input().split()]
for i in range(q):
    j = 0
    l = [int(s) for s in input().split()]
    for j in range(l[0], l[1] + 1):
        ans.append(c[j - 1])
    s += '\n' + str(len(set(ans)))
    ans.clear()

print(s.strip('\n'))

Submission status: Time Limit Exceeded

Solution code:
n,q=(int(x) for x in input().split())
c=[x for x in input().split()]

for _ in range(q):
  l,r=(int(x) for x in 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()))
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:
# coding: utf-8
n,q = map(int,input().split())
ball_list = (input().split())

for i in range(q):
    begin,end = map(int,input().split())
    t_ball_list = ball_list[begin-1:end]
    print(len(set(t_ball_list)))

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
def segfunc(x,y):
    return x | y

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

#####単位元######
ide_ele = set()

#num:n以上の最小の2のべき乗

n, Q = map(int, input().split())

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

c = list(map(int,input().split()))
init(c)
for _ in range(Q):
    l, r = map(int, input().split())
    ans = query(l-1,r)
    print(len(ans))