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
input = sys.stdin.readline

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

def seg_function(x,y): # Segment treeで扱うfunction
    return x|y

seg_el=1<<(N.bit_length()) # Segment treeの台の要素数
SEG=[set()]*(2*seg_el) # 1-indexedなので、要素数2*seg_el.Segment treeの初期値で初期化

for i in range(N): # Aを対応する箇所へupdate
    SEG[i+seg_el]={C[i]}

for i in range(seg_el-1,0,-1): # 親の部分もupdate
    SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el): # A[n]をxへ更新（反映）
    i=n+seg_el
    SEG[i]=x
    i>>=1 # 子ノードへ
    
    while i!=0:
        SEG[i]=seg_function(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r): # 区間[l,r)に関するseg_functionを調べる
    L=l+seg_el
    R=r+seg_el
    ANS=set()

    while L<R:
        if L & 1:
            ANS=seg_function(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=seg_function(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

for i in range(Q):
    x,y=map(int,input().split())
    print(len(getvalues(x-1,y)))

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:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst) # self.v is set to be 1-indexed for simplicity
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N elements (tree[0] is not used)
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N]
    
    # update a_i to be x 
    def update(self, i, x):
        v, op = self.v, self.op
        i += self.N
        v[i] = x
        while i > 0:
            i >>= 1 # move to parent
            v[i] = op(v[i << 1], v[(i << 1)|1])
    
    # returns answer for the query interval [l, r)
    def fold(self, l, r):
        N, e, v, op = self.N, self.e, self.v, self.op
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: # self.v[left] is the right child
                L = op(L, v[left])
                left += 1
            if right & 1: # self.v[right-1] is the left child
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

def wa(set1, set2):
    return set1 | set2

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

lst = []
for i in range(n):
    lst.append(set([c[i]]))

st = SegmentTree(lst, wa, set([]))
ans = []
for i in range(q):
    li, ri = map(int, input().split())
    li -= 1
    ans.append(len(st.fold(li, ri)))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c =[]
l = []
ans = []
c1 = []
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])
    c1.append (len(set(ans)))
    ans.clear()

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

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

import copy

def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = defaultdict(int)
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		A, B = copy.deepcopy(a), copy.deepcopy(b)

		if len(A) >= len(B):
			for i in B:
				A[i] = 1
			return A
		else:
			for i in A:
				B[i] = 1
			return B

	# セグメント木の中身をリストAで初期化
	def initialize(self, A):
		for i in range(self.N):
			d = defaultdict(int)
			d[A[i]] = 1
			self.data[self.N0 - 1 + i] = d
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return len(m)


#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	Seg = SegmentTree(N)
	Seg.initialize(c)
	# print(Seg.data)
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		ans = Seg.query(l, r)
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    sys.setrecursionlimit(10 ** 7)

    def I():
        return int(sys.stdin.readline().rstrip())

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

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

    def LI2():
        return list(map(int, sys.stdin.readline().rstrip()))  # 空白なし

    def S():
        return sys.stdin.readline().rstrip()

    def LS():
        return list(sys.stdin.readline().rstrip().split())  # 空白あり

    def LS2():
        return list(sys.stdin.readline().rstrip())  # 空白なし

    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 set_val(self, i, x):  # i番目(0-index)の値をxに変更
            i += self.N
            self.tree[i] = x
            while i > 1:
                i >>= 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:
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] = 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 reduce(self.f, 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 = self.f(
            reduce(self.f, self.ls[l:(l_bucket * self.b)], self.ide),
            ret)
        ret = self.f(
            reduce(self.f, self.ls[(r_bucket * self.b):r], self.ide),
            ret)
        return ret


class SegmentTree:
    def __init__(self, ls: list, segfunc, identity_element):
        '''
        セグ木
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.func = segfunc
        self.n_origin = len(ls)
        self.num = 2 ** (self.n_origin - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num - 1)  # −1はぴったりに作るためだけど気にしないでいい
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def __getitem__(self, idx):  # オリジナル要素にアクセスするためのもの
        if isinstance(idx, slice):
            start = idx.start if idx.start else 0
            stop = idx.stop if idx.stop else self.n_origin
            l = start + self.num - 1
            r = l + stop - start
            return self.tree[l:r:idx.step]
        elif isinstance(idx, int):
            i = idx + self.num - 1
            return self.tree[i]

    def update(self, i, x):
        '''
        i番目の要素をxに変更する(木の中間ノードも更新する) O(logN)
        '''
        i += self.num - 1
        self.tree[i] = x
        while i:  # 木を更新
            i = (i - 1) // 2
            self.tree[i] = self.func(self.tree[i * 2 + 1],
                                     self.tree[i * 2 + 2])

    def query(self, l, r):
        '''区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど'''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        res_right = []
        res_left = []
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if l & 1:
                res_left.append(self.tree[l - 1])
                l += 1
            if r & 1:
                r -= 1
                res_right.append(self.tree[r - 1])
            l >>= 1
            r >>= 1
        res = self.ide
        # 左右の順序を保って結合
        for x in res_left:
            res = self.func(x, res)
        for x in reversed(res_right):
            res = self.func(res, x)
        return res


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


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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1
qs = []
for i in range(Q):
  l, r = map(int, input().split())
  qs.append((l, r, i))
qs.sort(key = lambda x: x[1])
last = [0] * (N + 1)
fwk = BIT(N)
for i in range(qs[0][1]): last[a[i]] = max(last[a[i]], i + 1)
for x in last:
  if x: fwk.add(x, 1)
#print(last)
res = [0] * Q
rlast = qs[0][1]
for l, r, i in qs:
  #print(l, r)
  if rlast == r:
    res[i] = fwk.get(l - 1, r)
  else:
    for x in range(rlast, r):
      if last[a[x]]: fwk.add(last[a[x]], -1)
      fwk.add(x + 1, 1)
      last[a[x]] = x + 1
    rlast = r
    res[i] = fwk.get(l - 1, r)
for r in res: print(r)

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 = [set({}) for _ in range(2 * self.len)]

    def update(self, i, x):  # 0-indexed
        i += self.len
        while i > 0:
            self.array[i].add(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 = set({})

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


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

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

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

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
    for ind,(l, r) in q:
        while i <= r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                add(j,-1)
            add(i,1)
            p[ci] = i
            i += 1
        ans[ind] = sum_(r)-sum_(l-1)
    for i in ans:
        print(i)
    return

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

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def segfunc(self, x, y):
        return x | y

    def __init__(self, n, init_val):
        self.num = 2**(n-1).bit_length()
        self.seg = [set() for _ in range(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 query(self, p, q):#p <= x < q
        if q<=p:
            return set()
        p += self.num-1
        q += self.num-2
        res = set()
        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 = map(int, input().split())
    color = list(map(int, input().split()))
    qry = [list(map(int, input().split())) for _ in range(q)]
    tmp = [set() for _ in range(n)]
    for i in range(n):
        tmp[i].add(color[i])
    seg = SegTree(n, tmp)
    for l, r in qry:
        print(len(seg.query(l-1, r)))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
A = list(map(int, input().split()))
MAX_A = 5 * 10 ** 5
query = []
for q in range(Q):
    l, r = map(int, input().split())
    query.append((l, r, q))


# 一番後ろの1を削りながら0までやるイメージ
# 1-indexed
# 閉区間
# 区間[s, t]の和 => BIT.add(t) - BIT.add(s - 1)

class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += (i & -i)

    def reset(self):
        self.bit = [0] * (self.size + 1)


BIT = BinaryIndexedTree(N)
X = [-1] * (MAX_A + 1)
for i, a in enumerate(A, start=1):
    X[a] = i
for x in X:
    if x == -1:
        continue
    BIT.add(x, 1)

ans = [-1] * Q
query.sort(key=lambda x: x[1])

for l, r, i in query:
    BIT.add(X[A[r - 1]], -1)
    X[A[r - 1]] = r
    BIT.add(r, 1)
    ans[i] = BIT.sum(r) - BIT.sum(l - 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
class SegT():
    def __init__(self, size, origin):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [set() for _ in range(self.size * 2 - 1)]
        for i in range(size):
            self.data[i+self.size-1] = origin[i]
        for i in range(self.size-2,-1,-1):
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
 
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = {x}
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return set()
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

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

segt = SegT(N, [{c} for c in C])

for i in range(Q):
    l, r = map(int, input().split())
    x = segt.get(int(l)-1,int(r))
    print(len(x))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
def main():
  readline = stdin.readline
  N, Q = map(int, readline().split())
  C = tuple(map(int, readline().split()))
  for _ in range(Q):
    x, y = map(int, readline().split())
    S = set(C[x - 1:y])
    print(len(S))
if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys, heapq
input = sys.stdin.readline
n, q = map(int, input().split())
c = [int(x) - 1 for x in input().split()]


que = []
for i in range(q):
    l, r = map(int, input().split())
    heapq.heappush(que, (r-1, l-1, i))


lastAppeared = [-1 for _ in range(n)]
memo = [0 for _ in range(n)]
ans = [None for _ in range(q)]
for i in range(n):
    if lastAppeared[c[i]] != -1:
        memo[lastAppeared[c[i]]] -= 1
    lastAppeared[c[i]] = i
    memo[i] += 1

    while que and que[0][0] == i:
        r, l, x = heapq.heappop(que)
        ans[x] = sum(memo[l:r+1])

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,q = IL()
    c = list(IL())
    for i in range(q):
        l,r = IL()
        print(len(set(c[l-1:r])))
    exit()

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

Submission status: Time Limit Exceeded

Solution code:
MAX = 5*10**5+1
# structure to store queries 
class Query:
    def __init__(self, l, r, idx):
        self.l=l
        self.r=r
        self.idx=idx

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

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

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

	# initialising bit array 
	bit = [0] * (n + 1) 

	# holds the rightmost index of 
	# any number as numbers of a[i] 
	# are less than or equal to 10^6 
	last_visit = [-1] * MAX

	# answer for each query 
	ans = [0] * q 

	query_counter = 0
	for i in range(n): 

		# If last visit is not -1 update -1 at the 
		# idx equal to last_visit[arr[i]] 
		if last_visit[arr[i]] != -1: 
			update(last_visit[arr[i]] + 1, -1, bit, n) 

		# Setting last_visit[arr[i]] as i and 
		# updating the bit array accordingly 
		last_visit[arr[i]] = i 
		update(i + 1, 1, bit, n) 

		# If i is equal to r of any query store answer 
		# for that query in ans[] 
		while query_counter < q and queries[query_counter].r == i: 
			ans[queries[query_counter].idx] = query(queries[query_counter].r + 1, bit, n) - query(queries[query_counter].l, bit, n) 
			query_counter += 1

	# print answer for each query 
	for i in range(q): 
		print(ans[i]) 

# Driver Code
n,q=[int(i) for i in input().split()]
a = [int(i) for i in input().split()]
n = len(a)
queries=[]
for i in range(q):
    l,r=[int(i)-1 for i in input().split()]
    queries.append(Query(l, r, i))

queries.sort(key = lambda x: x.r) 
answeringQueries(a, n, queries, q)

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]
    sstone = set(sstone)
    print(len(sstone))

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

class SegTree:
    def __init__(self,a):  # idenityは適切に変更
        self.func = set
        self.ide = set()
        self.n = 2**(len(a)-1).bit_length()
        self.tree = [self.ide]*(2*self.n-1)
        
        # 初期配列セット
        for k,x in enumerate(a):
            self.tree[k+self.n-1] = set([x])
        for i in range(self.n):
            self.tree[self.n-i-2] = self.tree[(self.n-i-2)*2+1] | self.tree[(self.n-i-2)*2+2]
            
    def query(self,p,q):  # [p,q)の範囲で求める（p~q-1）
        p += self.n
        q += self.n
        ans = self.ide
        while p<q:
            if p&1:
                ans = ans | self.tree[p-1]
                p+=1
            if q&1:
                ans = ans | self.tree[q-2]
            p >>= 1
            q >>= 1
        return ans

n,q = readints()

c = readints()

seg = SegTree(c)

ans = []
for i in range(q):
    l,r = readints()
    ans.append(len(seg.query(l-1,r)))
printrows(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
def input(): return sys.stdin.readline().rstrip("\r\n")

mex = 1000001

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


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


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


def ansQuery(arr, n, queries, q):
	bits = [0] * (n + 1)
	l_v = [-1] * mex
	ans = [0] * q
	q_cnt = 0
	for i in range(n):
		if l_v[arr[i]] != -1:
			update(l_v[arr[i]] + 1, -1, bits, n)

		l_v[arr[i]] = i
		update(i + 1, 1, bits, n)

		while q_cnt < q and queries[q_cnt].r == i:
		    ans[queries[q_cnt].idx] = query(queries[q_cnt].r + 1, bits, n) - query(queries[q_cnt].l, bits, n)
		    q_cnt += 1

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


n,q = list(map(int,input().split()))
arr = list(map(int,input().split()))
queries = []
for i in range(q):
    l,r = list(map(int,input().split()))
    l,r = l-1,r-1
    queries.append(Query(l,r,i))
    q = len(queries)
queries.sort(key=lambda x: x.r)
ansQuery(arr, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
import collections

N,Q = (int(x) for x in input().split())
c = list(map(int,input().split()))
lr = [map(int, input().split()) for _ in range(Q)]
l, r = [list(i) for i in zip(*lr)]

for i in range(Q):
    a = c[l[i]-1:r[i]]
    b = collections.Counter(a)
    print(len(b))

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


intervals = [set() for _ in range(int(n ** .5))]
interval_length = (n + len(intervals) - 1) // len(intervals)

for i in range(n):
    intervals[i // interval_length].add(c[i])


ans = []
for _ in range(q):
    l, r = inp(), inp()
    l -= 1
    r -= 1
    start_interval = l // interval_length
    end_interval = r // interval_length
    total_set = set()

    while l // interval_length == start_interval and l <= r:
        total_set.add(c[l])
        l += 1
    while r // interval_length == end_interval and l <= r:
        total_set.add(c[r])
        r -= 1
    for interval_idx in range(start_interval + 1, end_interval):
        total_set |= intervals[interval_idx]

    ans.append(len(total_set))

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