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:

class SegmentTree:
    """
    演算子は要素とセットでモノイドを形成するようなものでなければならない。
    すなわち、結合律が成り立ち単位元が存在する必要がある。

    equalityはsetを高速化するために使う。めんどい場合はNoneにしてもOK
    """
    @classmethod
    def all_identity(cls, operator, equality, identity, size):
        return cls(operator, equality, identity, [identity]*(2 << (size-1).bit_length()))

    @classmethod
    def from_initial_data(cls, operator, equality, identity, data):
        size = 1 << (len(data)-1).bit_length()
        temp = [identity]*(2*size)
        temp[size:size+len(data)] = data
        data = temp

        for i in reversed(range(size)):
            data[i] = operator(data[2*i],data[2*i+1])
        return cls(operator, equality, identity, data)

    # これ使わずファクトリーメソッド使いましょうね
    def __init__(self, operator, equality, identity, data):
        if equality is None:
            equality = lambda a,b: False
        self.op = operator
        self.eq = equality
        self.id = identity
        self.data = data
        self.size = len(data)//2

    def _interval(self, a, b):
        a += self.size
        b += self.size
        ra = self.id
        rb = self.id

        data = self.data
        op = self.op
        while a < b:
            if a & 1:
                ra = op(ra,data[a])
                a += 1
            if b & 1:
                b -= 1
                rb = op(data[b],rb)
            a >>= 1
            b >>= 1
        return op(ra,rb)

    def __getitem__(self, i):
        if isinstance(i, slice):
            return self._interval(
                                    0 if i.start is None else i.start,
                                    self.size if i.stop is None else i.stop)
        elif isinstance(i, int):
            return self.data[i+self.size]

    def __setitem__(self, i, v):
        i += self.size
        data = self.data
        op = self.op
        eq = self.eq
        while i and not eq(data[i],v):
            data[i] = v
            v = op(data[i^1],v) if i & 1 else op(v,data[i^1])
            i >>= 1

    def __iter__(self):
        return self.data[self.size:]

from operator import or_

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

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

data = [{c} for c in C]

seg = SegmentTree.from_initial_data(or_, None, set(), data)

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

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

N ,Q = map(int, input().split())
c = list(map(int, input().split()))
for num in range(Q):
  l,r = map(int, input().split())
  test = c[l-1:r]
  t = collections.Counter(test)
  print(len(t))

Submission status: Time Limit Exceeded

Solution code:
import bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

N,Q = LI()
c = LI()
lr = [LI() for _ in range(Q)]
#A,B = zip(*AB)
# c = np.array(_c)

# setしてlength
c.insert(0, 0)
for pair in lr:
    print(len(set(c[pair[0]:pair[1]+1])))

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(collections.Counter(colors[l - 1: r])))

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, target, no_effect=set()):
        target_size = len(target)
        leaves_size = 1
        while leaves_size < target_size:
            leaves_size *= 2
        self.tree_size = leaves_size * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.no_effect = no_effect
        self.initialize_tree(target, no_effect)

    @classmethod
    def initialize_func(cls, value):
        return {value}

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree(self, target: list, no_effect=0):
        initial_leaf = self.tree_size // 2
        leaves = range(initial_leaf, initial_leaf+len(target))
        for value, leaf in zip(target, leaves):
            self.tree[leaf] = self.initialize_func(value)

        for parent in range(initial_leaf-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_value, index):
        leaf = self.tree_size//2 + index
        new_data = self.initialize_func(new_value)
        if self.tree[leaf] == new_data:
            return
        self.tree[leaf] = new_data

        parent = (leaf-1) // 2
        while parent >= 0:
            new_data = self.merge_child_data(parent)
            if self.tree[parent] == new_data:
                break
            self.tree[parent] = new_data
            parent = (parent-1) // 2

    def resolve_query(self, from_, to):
        result = self.no_effect
        left, right = from_ + self.tree_size // 2, to + self.tree_size // 2
        while left <= right:
            result = self.merge_func(result, self.tree[left])
            result = self.merge_func(result, self.tree[right])
            left //= 2
            right = right//2 - 1

        return len(result)


def main():
    n, q = map(int, input().split())
    C = list(map(int, input().split()))

    seg_tree = SegmentTree(C)
    for _ in range(q):
        l, r = map(int, input().split())
        res = seg_tree.resolve_query(l-1, r-1)
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()
A = IL()

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [self.e] * (2 * self.size)
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] |= val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = SegmentTree(N,lambda x,y:x|y,0)
for i in range(N):
  x = A[i]
  ST.update(i,1<<x)

for _ in range(Q):
  L,R = IL()
  print(count_bit(ST.get(L-1,R)))

Submission status: Time Limit Exceeded

Solution code:
param_n, param_q = map(int, input().split())
param_str = str(input())
list_str = param_str.split(' ')
for i in range(param_q):
    param_a, param_b = map(int, input().split())
    list_str_tmp = list_str[param_a-1:param_b]
    param_ans = len(list(set(list_str_tmp)))
    print(param_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):
    start,finish=map(int,input().split())
    arr=[]
    for i in range(start-1,finish):
        if c[i] not in arr:
            arr.append(c[i])
    print(len(arr))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
lst=list(map(int,input().strip().split()))
i=1 
while(i<=q):
    a,b=map(int,input().split())
    a=a-1
    ans=len(list(set(lst[a:b])))
    print(ans)
    i+=1

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

queries = [[] for _ in range(n)]
rights = [[] for _ in range(n)]
for i in range(q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    queries[l[i]].append(i)

last_app = [-1] * (n+1)
for i in range(n):
    if last_app[c[i]] != -1:
        last = last_app[c[i]]
        rights[last].append(i)
    last_app[c[i]] = i



ans = [0] * q

seg = [0] * (1 << 20)

def add(x):
    x += 1 << 19
    while x:
        seg[x] += 1
        x = x // 2

def sum_of(l, r):
    l += 1 << 19
    r += 1 << 19
    ans = 0
    while l < r:
        if l % 2 == 1:
            ans += seg[l]
            l += 1
        if r % 2 == 1:
            ans += seg[r-1]
            r -= 1
        l //= 2
        r //= 2
    return ans

        
for i in range(n-1, -1, -1):
    for right in rights[i]:
        add(right)
    for q_ind in queries[i]:
        left = l[q_ind]
        right = r[q_ind]
        ans[q_ind] = (right - left) - sum_of(left, right)

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()))
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 numpy as np

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

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

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)

def numofbits(bits):
    num  = 0
    mask = 1

    while mask <= bits:
        if bits & mask != 0:
            num+=1
        mask = mask << 1

    return num

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|b
    return c

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

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

    sg = segtree(n, concat, 0)

    for i,c in enumerate(C):
        # log(sg)
        sg.update(i, 2**c)

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

main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, bisect



if(__name__ == "__main__"):

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

    Num_colors_list= [ [0]*N for _ in range(N) ]

    Queries = [ [0, 0] for _ in range(Q) ]
    for i in range(Q):
        l, r = map(int, input().strip().split() )
        Queries[i] = [l, r]

    color = colors[0]-1
    Num_colors_list[0][color] =1

    for i in range(1, N):
        color = colors[i]-1
        for j in range(N):
            Num_colors_list[i][j] =Num_colors_list[i-1][j]
        Num_colors_list[i][color] += 1
    #print(Num_colors_list)
    for q in range(Q):
        N_color_lr = 0
        query = Queries[q]

        if(query[0] == 1):
            for i in range(N):
                if(Num_colors_list[ query[1]-1 ][i]>0):
                    N_color_lr += 1
        else:
            for i in range(N):
                if(Num_colors_list[ query[1]-1 ][i]- Num_colors_list[ query[0]-2 ][i]>0):
                    N_color_lr += 1

        print(N_color_lr)

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>>9<<20|R
    B[L>>9&1] = L>>9<<20|(1<<20)-R
    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:
import sys
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


class SegmentTreeSET(object):  # 1-indexed [l,r)
    def __init__(self, size):
        self.len = 1 << size.bit_length()
        # print(self.len)
        self.array = [ 0 for _ in range(2 * self.len)]

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i] = self.array[i] | x
            i >>= 1
        # print(self.array)

    def get(self, i):  # 0-indexed
        return self.array[i + self.len]

    def get_cnt(self, l, r):  # 0-indexed
        L = l+self.len
        R = r+self.len
        ANS = 0

        while L < R:
            if L & 1:
                ANS = (ANS | self.array[L])
                L += 1

            if R & 1:
                R -= 1
                ANS = (ANS | self.array[R])
            L >>= 1
            R >>= 1

        return bin(ANS).count("1")


N, Q = na()
c_array = na()

tree = SegmentTreeSET(N)
for i, c in enumerate(c_array):
    tree.update(i, 1 << c)

for _ in range(Q):
    l, r = na()
    print(tree.get_cnt(l-1, r))

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int,input().split())
stone = list(map(int,input().split())) 
for i in range(Q):
    a,b = map(int,input().split())
    a -= 1
    sstone = stone[a:b]
    print(len(set(sstone)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = [*map(int, input().split())]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

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

    def update(self, k, x):
        k += self.num - 1
        self.seg[k] = x
        while k:
            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


def main():

    N, Q = in_nn()
    C = in_nl()

    t = [0] * N
    for i in range(N):
        t[i] = 1 << (C[i] - 1)

    seg = SegTree(t, segfunc=lambda a, b: a | b, ide_ele=0)
    ans = [0] * Q
    for i in range(Q):
        l, r = in_nn()
        l = l - 1
        x = seg.query(l, r)

        cnt = x & 1
        for j in range(x.bit_length()):
            x = x >> 1
            if x & 1:
                cnt += 1

        ans[i] = cnt

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
data = [int(v) for v in sys.stdin.read().split()[::-1]]

def inp():
    return data.pop()

n, q = inp(), inp()
*c, = [inp() for _ in range(n)]


def build_segment_tree(left, right, pos, tree, nums):
    if left == right:
        tree[pos] = {nums[left]}
        return tree[pos]
    mid = (left + right) // 2
    tree[pos] = (
        build_segment_tree(left, mid, pos * 2 + 1, tree, nums) |
        build_segment_tree(mid + 1, right, pos * 2 + 2, tree, nums)
    )
    return tree[pos]

def get_min(left, right, segleft, segright, pos, tree):
    if right < 0:
        return float('inf')
    left = max(left, 0)
    if left == segleft and right == segright:
        return tree[pos]
    segleftend = (segleft + segright) // 2
    res = set()
    if segleftend >= left:
        res |= get_min(left, min(segleftend, right), segleft, segleftend, pos * 2 + 1, tree)
    if segleftend + 1 <= right:
        res |= get_min(max(segleftend + 1, left), right, segleftend + 1, segright, pos * 2 + 2, tree)
    return res

tree = [None for _ in range(4 * n)]
build_segment_tree(0, n - 1, 0, tree, c)

ans = []
for _ in range(q):
    l, r = inp(), inp()
    l -= 1
    r -= 1
    ans.append(len(get_min(l, r, 0, n - 1, 0, tree)))

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int,input().split())
c_list = list(map(int,input().split()))
query_list = [list(map(int,input().split())) for i in range(q)]
for i in range(q):
    color_list = [c_list[amount] for amount in range(query_list[i][0]-1, query_list[i][1])]
    print(len(set(color_list)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)

class SegmentTree:
    #for pypy
    #treeは1-based-index,queryは0-based-index
    __slots__=["size","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            self.tree[self.size+i]=initial_value_list[i]
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.tree[2*i]|self.tree[2*i+1]

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.tree[2*k]|self.tree[2*k+1]
    def query(self, l, r):
        #res->func[l,r)
        l+=self.size-self.first_idx
        r+=self.size-self.first_idx
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=lret|self.tree[l]
                l+=1
            if r&1:
                r-=1
                rret=self.tree[r]|rret # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return lret|rret

n,q=map(int,input().split())
l=[set([int(p)])for p in input().split()]
seg=SegmentTree(l,set(),1)
for i in inputs():
    le,ri=map(int,i.split())
    print(len(seg.query(le,ri+1)))

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

queries = [[] for _ in range(n)]
rights = [[] for _ in range(n)]
for i in range(q):
    l[i], r[i] = map(int, input().split())
    l[i] -= 1
    queries[l[i]].append(i)

last_app = [-1] * (n+1)
for i in range(n):
    if last_app[c[i]] != -1:
        last = last_app[c[i]]
        rights[last].append(i)
    last_app[c[i]] = i



ans = [0] * q

seg = [0] * (1 << 19)

def add(x):
    x += 1 << 18
    while x:
        seg[x] += 1
        x = x // 2

def sum_of(l, r):
    l += 1 << 18
    r += 1 << 18
    ans = 0
    while l < r:
        if l % 2 == 1:
            ans += seg[l]
            l += 1
        if r % 2 == 1:
            ans += seg[r-1]
            r -= 1
        l //= 2
        r //= 2
    return ans

        
for i in range(n-1, -1, -1):
    for right in rights[i]:
        add(right)
    for q_ind in queries[i]:
        left = l[q_ind]
        right = r[q_ind]
        ans[q_ind] = (right - left) - sum_of(left, right)

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

Submission status: Time Limit Exceeded

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

N,Q=(int(x) for x in input().rstrip('\n').split())
cs = [int(x) for x in input().rstrip('\n').split()]
for _ in range(Q):
  l,r = (int(x) for x in input().rstrip('\n').split())
  print(len(set(cs[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
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 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
        if l==r:
            res = self.tree[l]
        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 len(res)
    
N,Q=map(int,input().split())
b = list(map(int,input().split()))
a = [set() for i in range(N)]
for i in range(N):
    a[i].add(b[i])
def segfunc_union(x, y):
    return x | y
ide_ele_set = set()
seg1 = SegTree(a, segfunc_union, ide_ele_set)
for i in range(Q):
    b,c=map(int,input().split())
    print(seg1.query(b-1,c))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
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])
        else:
            if (c[j] in e):
                continue
            else:
                a = a + 1
                e.append(c[j])
    print (a)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections
N ,Q = map(int, input().split())
c = list(map(int, input().split()))
for num in range(Q):
  l,r = map(int, input().split())
  test = c[l-1:r]
  t = collections.Counter(test)
  n = len(t.items())
  print(n)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse import csr_matrix
import numpy as np

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

X = csr_matrix((N+1,N), dtype=np.int32)
for i in range(len(C)):
  c = C[i]-1
  X[i+1] += X[i]
  X[i+1,c] += 1

for _ in range(Q):
  l,r = map(int, input().split())
  print(np.sum(X[r]>X[l-1]))