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
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

N,Q = na()

# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
INF = 2**31-1
data = [0 for i in range(2*N0)]
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = 1 << x
    while k >= 0:
        k = (k - 1) // 2
        data[k]  = data[k] | (1 << x)

# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = s | data[R-1]

        if L & 1:
            s = s | data[L-1]
            L += 1
        L >>= 1; R >>= 1
    return bin(s).count("1")

c = na()
for i in range(N):
    update(i, c[i])

for j in range(Q):
    l,r = na()
    print(query(l-1,r))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from operator import add

class SegmentTree():

    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e
        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )
        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        return self.func(left_folded, right_folded)


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

to_consider = []
for c, n in Counter(cs).items():
    if n >= 2:
        to_consider.append(c)

sets = SegmentTree(map(lambda e: Counter([e]) if e in to_consider else Counter(), cs), add, Counter())
for l, r in lrs:
    ans = r - l + 1
    for k, v in sets.folded(l-1, r).items():
        ans -= (v - 1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,q=map(int, input().split())
c=np.array(list(map(int,input().split())))
for _ in range(q):
    l,r  = input().split()
    print(np.unique(c[int(l)-1:int(r)]).size)

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(' '))
cs = input().split(' ')


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

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
table=[[0 for _ in range(n)] for _ in range(n+1)]
C=list(map(int,input().split()))
for i in range(1,n+1):
    c=C[i-1]-1
    for k in range(i,n+1):
        table[k][c]+=1


for _ in range(q):
    l,r=map(int,input().split())
    ans=list(map(lambda x,y: x==y,table[r],table[l-1]))
    print(n-sum(ans))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
cSetLen = len(set(c))

lr = []
for i in range(q):
    l, r = map(int, input().split())
    temp = l
    answer = 0
    while temp < r and answer < cSetLen:
        temp += 1
        answer = len(set(c[l - 1 : temp]))
    if answer == 0:
        print(1)
    else:
        print(answer)

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
list_c = [int(a) for a in input().split()]
P = [list(map(int,input().split())) for i in range(Q)]

for i in range(Q):
    l = P[i][0]
    r = P[i][1]
    list_c_new = list_c[l-1:r]
    set_list = set(list_c_new)
    print(len(set_list))

Submission status: Time Limit Exceeded

Solution code:
##a = int(stdin.readline().rstrip())
##b, c = [int(x) for x in stdin.readline().rstrip().split()]
##s = stdin.readline().rstrip()
##a = list(set(b))  重複を削除
##a = list(map(int,[int(x) for x in stdin.readline().rstrip().split()])) a[0, 1, 2, ...]
##a = [[0] * 2 for _ in range(n)]  a[0,0]
##v = [s[i: i+2] for i in range(0, len(s), 2)]
##  s="12345678" を v=["12","34","56","78"] にするイメージ
##s = "".join(list)リストを文字列に変換[""]は区切り文字
##a.sort(key=itemgetter(1))リストをソートできるよ(from operator import itemgetterが必要)
##sort_p = sorted(p) 昇順ソート

# -*- coding: utf-8 -*-
from sys import stdin
from operator import itemgetter
from collections import deque, Counter
import math
import pprint
from functools import reduce
import numpy as np
import random
import bisect
import copy
# stdin = open("sample.txt")


MOD = 1000000007
INF = float('inf')
alpha = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]

def keta(kazu): # 入力されたintを桁ごとに分解，リストで出力
    kazu_str = str(kazu)
    kazu_list = [int(kazu_str[i]) for i in range(0, len(kazu_str))]
    return kazu_list

def gcd(*numbers): # 最小公倍数
    return reduce(math.gcd, numbers)

def combination(m,n): # mCn
    
    if n > m:
        return 'すまん'
    return math.factorial(m) // (math.factorial(m-n) * math.factorial(n))

def pow_k(x,n):  # (x**n)の計算の高速化
    if n == 0:
        return 1
    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2
    return K * x

def fact(n): # nの素因数分解の結果を辞書で出力 fuct(24) → {2: 3, 3: 1}
    arr = {}
    temp = n
    for i in range(2,int(n**0.5)+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
    if temp != 1:
        arr[temp] = 1
    if arr == {}:
        arr[n] = 1
    return arr
    
def main():
    N, Q = [int(x) for x in stdin.readline().rstrip().split()]
    C = list(map(int,[int(x) for x in stdin.readline().rstrip().split()]))
    for _ in range(Q):
        newC = copy.deepcopy(C)
        L, R = [int(x) for x in stdin.readline().rstrip().split()]
        sort_newC = set(newC[L-1:R])
        print(len(sort_newC))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class SegmentTree:
    def __init__(self, S):
        N = len(S)
        d = N.bit_length()
        T = [0 for _ in range(2 ** (d + 1) - 1)]
        for i, s in enumerate(S):
            T[i + 2 ** d - 1] = 1 << s
        for i in range(2 ** d - 2, -1, -1):
            T[i] = T[2 * i + 1] | T[2 * i + 2]
        self.d = d
        self.T = T

    def update(self, i, a):
            i = i + 2 ** self.d - 1
            while i > 0:
                i = (i - 1) // 2
                self.T[i] = self.T[2 * i + 1] | self.T[2 * i + 2]
    
    def query(self, a, b):
        return self._query(a, b, 0, 0, 2 ** self.d)

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0

        if a <= l and r <= b:
            return self.T[k]
        else:
            s1 = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            s2 = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return s1 | s2


def main():
    N, Q = read_values()
    C = read_list()

    ST = SegmentTree(C)
    for _ in range(Q):
        a, b = read_index()
        print(format(ST.query(a, b + 1), "b").count("1"))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    for i in range(q):
        l, r = lr[i]
        lr[i] = [l, r, i]
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1] <= i:
            f(t)
            t += 1
    for ai in ans:
        print(ai) 
    return


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

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#A1 ... AnのBIT(1-indexed)



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=MI()
	c=LI()
	for i in range(n):
		c[i]={c[i]}
	#####segfunc#####
	def segfunc(x, y):
		return x | y

	ide_ele =set()
	S=SegTree(c,segfunc,ide_ele)

	for _ in range(q):
		ll,rr=MI()
		print(len(S.query(ll-1,rr)))









if __name__ == "__main__":
	main()

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:
import collections
from sys import stdin
input=stdin.readline
n,q=map(int,input().split())
a=tuple(map(int,input().split()))
for i in range(q):
  x,y=map(int,input().split())
  print(len(collections.Counter(a[x-1:y])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = input().split()

# 回答
lrs = list(list(map(int, input().split())) for _ in range(q))
[print(len(set(balls[lr[0]-1:lr[1]]))) for lr in lrs]

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 = [{i} for i in LI()]

    seg = [set()] * (2*N)
    for i in range(N):
        seg[i+N] = c[i]
    for i in range(N-1,0,-1):
        seg[i] = seg[i << 1] | seg[i << 1 | 1]

    def fold(L, R):  # [L,R)の区間取得
        L += N
        R += N
        vL = set()
        vR = set()
        while L < R:
            if L & 1:
                vL = vL | seg[L]
                L += 1
            if R & 1:
                R -= 1
                vR = seg[R] | vR
            L >>= 1
            R >>= 1
        return len(vL | vR)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  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])

  #update(k, x): k番目の値をxに更新 O(logN)
  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

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  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

#segfunc
def segfunc(x,y):
  return x|y 
#ide_ele
ide_ele=set()

seg=SegTree([set()]*N, segfunc, ide_ele)
for i in range(N):
  c=clist[i]
  seg.update(i,{c})

for _ in range(Q):
  l,r=map(int,input().split())
  res=seg.query(l-1,r)
  #print(res)
  print(len(res))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
C = list(map(int, input().split()))
L, R = [0]*Q, [0]*Q
for q in range(Q):
  L[q],R[q] = map(int, input().split())
  
  print(len(set(C[L[q]-1:R[q]])))

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin

def solve():
    n,q= map(int, stdin.readline().rstrip().split())
    c = list(map(int, stdin.readline().rstrip().split()))
    for i in range(q):
        l,r= map(int, stdin.readline().rstrip().split())
        print(len(set(c[l-1:r])))

if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

for i in range(q):
    l, r = map(int, input().split())
    check = set(tamalist[l-1:r])
    # print(check)
    # print(tamalist)
    print(len(check))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
c = 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:
def bfs(x, b):
    length = len(x)

    if length == 1:
        if x[0] not in b:
            b.append(x[0])
            return 1
        return 0
    if length % 2 == 0:
        return bfs(x[int(length / 2):], b) + bfs(x[:int(length / 2)], b)
    else:
        return bfs(x[int(length - 1 / 2):], b) + bfs(x[:int(length - 1 / 2)], b)


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

for i in range(int(q)):
    lst = []
    l, r = input().split()
    print(bfs(c[int(l) - 1: int(r)], lst))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    for i in range(q):
        l, r = lr[i]
        lr[i] = [l, r, i]
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    def f(t):
        l, r, j = lr[t]
        if x[r] is None:
            x[r] = sum(r)
        if x[l - 1] is None:
            x[l - 1] = sum(l-1)
        tmp = x[r] - x[l - 1]
        ans[j] = tmp
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        x = defaultdict(lambda:None)
        while t < q and lr[t][1] <= i:
            f(t)
            t += 1
    for ai in ans:
        print(ai) 
    return


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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[1]:


from collections import deque


# In[2]:


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


# In[ ]:

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

def main():
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lr=[list(map(int,input().split())) for i in range(q)]

    class SegTree:
        # init_valはseg木にしたいlist、ide_eleは単位元
        # """
        # 単位元の説明
        # 最小値のセグ木 → 10**9　(最小値の更新に影響しないため)
        # 　　和のセグ木 → 0　(上の単位元の説明を参照)
        # 　　積のセグ木 → 1　(上の単位元の説明を参照)
        # 　　gcdのセグ木 → 0　(gcdを更新しない値は0)
        # """
        # funcは行いたい操作を代入
        # 区間の最小値を求めたいならmin
        # 区間の最大値を求めたいならmax
        # """
        def __init__(self, init_val, ide_ele):
            self.ide_ele=ide_ele
            self.num=2**(len(init_val)-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num
            # self.func=func

            #set_val
            for i in range(len(init_val)):
                self.seg[i+self.num-1]=init_val[i]
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

        # 書け
        def segfunc(self, x, y):
            return x | y
        
        def update(self, k, x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])

        def query(self, p, q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res
    cc=[]
    for i in range(n):
        cc.append(set([c[i]]))
    # print(cc) 
    seg=SegTree(cc,set())
    # print(seg.seg)
    for i in range(q):
        l,r=lr[i]
        print(len(seg.query(l-1,r)))

main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
C=list(map(int,input().split()))
LR=[]
for i in range(Q):
  l,r=map(int,input().split())
  LR.append([l,r])

colors=[[] for _ in range(N)]
for i in range(N):
  colors[C[i]-1].append(i)
  
import bisect

for i in range(Q):
  ans=0
  l,r=LR[i][0]-1,LR[i][1]-1
  for j in range(N):
    if bisect.bisect_left(colors[j],l)!=bisect.bisect_right(colors[j],r):
      ans+=1
      #print(j)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
list_c = [int(a) for a in input().split()]
P = [input().split() for i in range(Q)]

for i in range(Q):
    l = int(P[i][0])
    r = int(P[i][1])
    list_c_new = list_c[l-1:r]
    set_list = set(list_c_new)
    print(len(set_list))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
c = [int(i) for i in 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())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]
def calc_num(query):
    l, r = query
    return str(len(set(c[l - 1:r])))
str = "\n".join(list(map(calc_num, query)))
print(str)

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = [-1]*(N+1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append(r*10**15+l*10**8+i)
queries.sort()
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):
    SUM = queries[j]
    r = SUM // 10**15
    SUM %= 10**15
    l = SUM // 10**8
    SUM %= 10**8
    i =SUM
    while curR < r:
        curR += 1
        last = lastAppeared[c[curR]]
        if last != -1:
            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()))
s = set(c)
sl = len(s)
for i in range(Q):
    a = 0
    e = []
    l, r = map(int, input().split())
    for j in range(l-1, r):
        if j == l - 1:
            a = 1
            e.append(c[j])
        elif a == sl:
          break;
        else:
            if (c[j] in e):
                continue
            else:
                a = a + 1
                e.append(c[j])
    print (a)

Submission status: Time Limit Exceeded

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

for i in range(Q):
  st,end = map(int,input().split())
  print(len(set(cs[st-1:end])))

Submission status: Time Limit Exceeded

Solution code:
class segmentTreeOR():
    initValue = 0
    dat = []
    lenTreeList = -1
    depthTreeList = 0
    lenOriginalList = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenOriginalList = len(l)
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        self.dat = [set([self.initValue])] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenTreeList - 1 + i] = set([l[i]])
        self.build()

    def build(self):
        for i in range(self.lenTreeList - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] | self.dat[2 * i + 2]

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = set([a])
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] | self.dat[nodeId * 2 + 2]

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return set([])
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft | resRight

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

n, q = map(int, input().split())
dat = list(map(int, input().split()))
st = segmentTreeOR()
st.load(dat)
for i in range(q):
    l, r = map(int, input().split())
    x = st.query(l-1, r-1+1)
    print(len(x))

Submission status: Time Limit Exceeded

Solution code:
import math

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

M = int(math.sqrt(N))

cs = []
for i in range(0, N, M):
    cs.append(set(c[i:min(i+M, N)]))

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

    li = l // M
    ri = r // M

    if li == ri:
        ans = len(set(c[l-1:r]))
    else:
        s = set(c[l-1:(li+1)*M])
        for j in range(li+1, ri):
            s.update(cs[j])
        s.update(c[ri*M:r])
        ans = len(s)

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = input().split()

# 回答
lr = list(list(map(int, input().split())) for _ in range(q))
[print(len(set(balls[lr[i][0]-1:lr[i][1]]))) for i in range(q)]

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
input_line = input().split(' ')
jewel = [int(n) for n in input().split(' ')]
for i in range(int(input_line[1])):
    q = [int(n) for n in input().split(' ')]
    l = jewel[q[0] - 1:q[1]]
    l2 = [x for x in set(l) if l.count(x) >= 1]
    print(len(l2))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LIR(n):
    return [LI() for i in range(n)]

def solve():
    def add(i,x):
        while i < len(bit):
            bit[i] += x
            i += i&-i
    def sum_(i):
        res = 0
        while i > 0:
            res += bit[i]
            i -= i&-i
        return res
    n,Q = LI()
    c = LI()
    c = [0]+c
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    bit = [0]*(n+2)
    i = 1
    p = [None]*(n+1)
    ans = [0]*Q
    s = 0
    for ind,(l, r) in q:
        l -= 1
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,1)
            else:
                s += 1
            p[ci] = i
            i += 1
        ans[ind] = s-l+sum_(l)
    for i in ans:
        print(i)
    return

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

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 i in range(q):
    print(len(set(c[l[i]-1:r[i]])))

Submission status: Time Limit Exceeded

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