Problem:


Score : 600 points

Problem Statement

We have N colored balls arranged in a row from left to right; the color of the i-th ball from the left is c_i.

You are given Q queries. The i-th query is as follows: how many different colors do the l_i-th through r_i-th balls from the left have?

Constraints

1\leq N,Q \leq 5 \times 10^5

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N Q
c_1 c_2 \cdots c_N
l_1 r_1
l_2 r_2
:
l_Q r_Q

Output

Print Q lines. The i-th line should contain the response to the i-th query.

Sample Input 1

4 3
1 2 1 3
1 3
2 4
3 3

Sample Output 1

2
3
1

The 1-st, 2-nd, and 3-rd balls from the left have the colors 1, 2, and 1 - two different colors.

The 2-st, 3-rd, and 4-th balls from the left have the colors 2, 1, and 3 - three different colors.

The 3-rd ball from the left has the color 1 - just one color.

Sample Input 2

10 10
2 5 6 5 2 1 7 9 7 2
5 5
2 4
6 7
2 2
7 8
7 9
1 8
6 9
8 10
6 8

Sample Output 2

1
2
2
1
2
2
6
3
3
3



Sample input:
4 3
1 2 1 3
1 3
2 4
3 3


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# SegTreeの関数
def segfunc(x, y):
    return x | y
# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = set()

# セグメント木
class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """
    def __init__(self, init_val, segfunc, ide_ele):
        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に更新
        :param k: index(0-index)
        :param 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したものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        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 = NMI()
    C = NLI()
    CS = [{c} for c in C]
    querys = [NLI() for _ in range(Q)]
    segtree = SegTree(CS, segfunc, ide_ele)

    for l, r in querys:
        l -= 1
        r -= 1
        print(len(segtree.query(l, r+1)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
  ci = set()
  li, ri = map(int, readline().split())
  for j in range(li-1, ri):
    if C[j] not in ci:
      ci.add(C[j])
  print(len(ci))

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter


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

e = Counter()
A = [None] * (N + 1)
A[0] = e | e
for i, c in enumerate(C):
    A[i + 1] = A[i] + Counter({c: 1})

for i in range(Q):
    l, r = map(int, sys.stdin.readline().split())
    print(len(A[r] - A[l - 1]))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, N, arr=None, op=None):
        """
        INPUT
        N: 配列のサイズ
        segment tree: 1-indexedで構築
        original array: 0-indexed
                 1
           2           3
         4    5     6     7
        8 9 10 11 12 13 14 15
        ---------------------
        0 1 2  3  4  5  6  7
        """
        self.N = N
        self.op = op
        self.tree = [set()] * (2 * N + 1)
        if arr is not None:
            self._build(arr)

    def _build(self, arr):
        op = self.op
        N = self.N
        for i, a in enumerate(arr, N):
            self.tree[i] = set([a])
        for i in reversed(range(1, N)):
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, i, x):
        """
        arr[i]の値をxに変更する
        i: 0-indexed
        """
        i += self.N
        op = self.op
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = op(self.tree[i << 1], self.tree[i << 1 | 1])

    def query(self, L, R):
        """
        L,R: 0-indexed
        半開区間[L,R)の累積演算した値を返す
        """
        op = self.op
        res = set()
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                res = op(res, self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                res = op(res, self.tree[R])
            L >>= 1
            R >>= 1
        return len(res)


def union(a, b):
    return a | b


N, Q = map(int, input().split())
C = list(map(int, input().split()))
seg = SegmentTree(N, C, union)
for _ in range(Q):
    s, t = map(int, input().split())
    print(seg.query(s-1, t))

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

l = list(input().split())

for _ in range(q):
    a, b = map(int, input().split())
    s = l[a - 1:b]
    c = collections.Counter(s)
    print(len(c))

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

LEN=N
Sparse_table = [[1<<c for c in C]]

for i in range(LEN.bit_length()-1):
    j = 1<<i
    B = []
    for k in range(len(Sparse_table[-1])-j):
        B.append(Sparse_table[-1][k]|Sparse_table[-1][k+j])
    Sparse_table.append(B)

def query(l,r):
    i=(r-l).bit_length()-1 # 何番目のSparse_tableを見るか. 

    ANS=Sparse_table[i][l]|Sparse_table[i][r-(1<<i)]

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

for qu in range(Q):
    x,y=map(int,input().split())
    print(query(x-1,y))

Submission status: Time Limit Exceeded

Solution code:
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 1000001


# structure to store queries
class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx


# updating the bit array
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
if __name__ == "__main__":
    n, q = map(int, input().split())
    a = [int(k) for k in input().split()]
    queries = []
    for i in range(q):
        l, r = map(int, input().split())
        queries.append(Query(l-1, r-1, i))
    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

# This code is contributed by
# sanjeev2552

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
Z = [list(map(int, input().split())) for _ in range(Q)]

for q in range(Q):
    print(len(set(C[Z[q][0]-1:Z[q][1]])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
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)]
lr = np.array(_lr)
c = np.zeros(N + 1)
c[1:] = _c

for pair in lr:
    print(len(set(c[pair[0]:pair[1]+1])))

Submission status: Time Limit Exceeded

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class SegmentTree:
        def __init__(self, A, initialize=True, segfunc=min, ident=2000000000):
            self.N = len(A)
            self.LV = (self.N - 1).bit_length()
            self.N0 = 1 << self.LV
            self.segfunc = segfunc
            self.ident = ident
            if initialize:
                self.data = [self.ident] * self.N0 + A + [self.ident] * (self.N0 - self.N)
                for i in range(self.N0 - 1, 0, -1):
                    self.data[i] = segfunc(self.data[i * 2], self.data[i * 2 + 1])
            else:
                self.data = [self.ident] * (self.N0 * 2)

        def update(self, i, x):
            i += self.N0 - 1
            self.data[i] = x
            for _ in range(self.LV):
                i >>= 1
                self.data[i] = self.segfunc(self.data[i * 2], self.data[i * 2 + 1])

        # open interval [l, r)
        def query(self, l, r):
            l += self.N0 - 1
            r += self.N0 - 1
            ret_l = self.ident
            ret_r = self.ident
            while l < r:
                if l & 1:
                    ret_l = self.segfunc(ret_l, self.data[l])
                    l += 1
                if r & 1:
                    ret_r = self.segfunc(self.data[r - 1], ret_r)
                    r -= 1
                l >>= 1
                r >>= 1
            return self.segfunc(ret_l, ret_r)

    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    C = [{c} for c in C]

    def segfunc(A, B):
        ret = set()
        for a in A:
            ret.add(a)
        for b in B:
            ret.add(b)
        return ret

    ST = SegmentTree(C, segfunc=segfunc, ident=set())
    for _ in range(Q):
        l, r = map(int, input().split())
        #print(ST.query(l, r+1))
        print(len(ST.query(l, r+1)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]
arr=[]
for i in range(q):
    l, r = query[i]
    print(len(set(c[l-1:r])))

Submission status: Time Limit Exceeded

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

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

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

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


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math

# import copy
from bisect import bisect_left, bisect_right
# import heapq

sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline

getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)


def nck(n, k, kaijyo):
    return (npk(n, k, kaijyo) * divide(kaijyo[k])) % MOD


def npk(n, k, kaijyo):
    if k == 0 or k == n:
        return n % MOD
    return (kaijyo[n] * divide(kaijyo[n-k])) % MOD


def kaijyo(n):
    ret = [1]
    for i in range(1, n + 1):
        ret.append((ret[-1] * i)% MOD)
    return ret


class Segtree_op():
    # 単位元及び操作を設定して使うこと
    # queryでは、区間の(l, r)を指定する ex: (0, 5) => [0, 1, 2, 3, 4]
    # 特定の1点は (i, i+1)
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        return lch + rch
    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def show(self):
        idx = 1
        while (idx <= self.size):
            print(self.arr[idx - 1:idx * 2 - 1])
            idx *= 2


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

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

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

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

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





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


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

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    colors = set()
    l, r = map(int, input().split(' '))
    l -= 1
    r -= 1
    array = balls[l:r+1]
    for a in array:
        colors.add(a)
    print(len(colors))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n,q=map(int,input().split())
    clst=tuple(map(int,input().split()))
    
    for _ in range(q):
        l,r=map(int,input().split())
        print(len(set(clst[l-1:r])))

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env pypy3

MAX_VAL = 5 * 10 ** 5 + 1


class FenwickTree(object):
 
    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]
 
    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s
 
    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)
 
    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    sorted_queries = sorted(queries, key=lambda x: x[1])
    ans = [0] * q
    qc = 0
    for i in range(n):
        if last_visit[cs[i]] != -1:
            ft.add(last_visit[cs[i]], -1)
        last_visit[cs[i]] = i
        ft.add(i, 1)
        while qc < q and sorted_queries[qc][1] == i:
            sqqc = sorted_queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    for i in range(q):
        yield ans[i]


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = []
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries.append((le, ri, i))
    for a in answer_queries(n, q, cs, queries):
        print(a)


if __name__ == '__main__':
    main()

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())
  unique_set = set()
  count = 0
  
  for n in range(l - 1, r):
    color = colors[n]
    if color not in unique_set:
      count += 1
      unique_set.add(color)
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

cs = []

counter = Counter()
for ci in c:
    counter.update([ci])
    c2 = Counter(counter)
    cs.append(c2)

memo = [[-1] * (N+1) for _ in range(N+1)]

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

    if memo[l][r] != -1:
        print(memo[l][r])
    else:
        c3 = Counter(cs[r-1])
        if l > 1:
            c3.subtract(cs[l-2])
            c3 = +c3
        memo[l][r] = len(c3)
        print(memo[l][r])

Submission status: Time Limit Exceeded

Solution code:
import collections
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

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

l = list(input().split())

for _ in range(q):
    a, b = map(int, input().split())
    if a == b:
        print(1)
    else:
        s = l[a - 1:b]
        c = collections.Counter(s)
        print(len(c))

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 = []
    for color_index in range(query_list[i][0]-1, query_list[i][1]):
        if c_list[color_index] not in color_list:
            color_list.append(c_list[color_index])
    print(len(set(color_list)))
    color_list.clear()

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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

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

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

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

#https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266
def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f


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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) for _ in range(q)]
arr=[]
for i in range(q):
    l, r = query[i]
    arr.append(len(set(c[l-1:r])))
for i in range(len(arr)):
    print(arr[i])

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
x = []
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 sys, math, bisect



if(__name__ == "__main__"):

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



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

    colors_pos = [ [] for _ in range(N) ]

    for i in range(N):
        color = colors[i]-1
        colors_pos[color].append(i)

    for q in range(Q):
        N_color_lr = 0
        query = Queries[q]
        left = query[0] -1
        right = query[1] - 1

        N_types = 0
        if(left==0):
            #rightで考える
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) >0):
                    N_types += 1
        else:
            for i in range(N):
                if( bisect.bisect_right(colors_pos[i], right) - bisect.bisect_left(colors_pos[i], left) >0):
                    N_types += 1
        print(N_types)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

MAX_VAL = 5 * 10 ** 5 + 1


class FenwickTree(object):
 
    def __init__(self, num_elems):
        self.num_elems = num_elems
        self.data = [0 for _ in range(num_elems)]
 
    def sum_to(self, end):
        s = 0
        i = end - 1
        while i >= 0:
            s += self.data[i]
            i = (i & (i + 1)) - 1
        return s
 
    def sum_range(self, start, end):
        return self.sum_to(end) - self.sum_to(start)
 
    def add(self, idx, x):
        while idx < self.num_elems:
            self.data[idx] += x
            idx |= idx + 1


def answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    sorted_queries = sorted(queries, key=lambda x: x[1])
    ans = [0] * q
    qc = 0
    for i in range(n):
        if last_visit[cs[i]] != -1:
            ft.add(last_visit[cs[i]], -1)
        last_visit[cs[i]] = i
        ft.add(i, 1)
        while qc < q and sorted_queries[qc][1] == i:
            sqqc = sorted_queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    for i in range(q):
        yield ans[i]


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = []
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries.append((le, ri, i))
    for a in answer_queries(n, q, cs, queries):
        print(a)


if __name__ == '__main__':
    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):
  tmp = list(map(int,input().split()))
  lr.append(tmp)

for i in range(q):
  count = len(set(c[lr[i][0]-1:lr[i][1]]))
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
li = []
dic = {}
for i in range(n):
    try:
        dic[c[i]] += 1
    except:
        dic[c[i]] = 1
    li.append(dic.copy())
# print(li)
for i in range(q):
    l, r = map(int, input().split())
    if l == r:
        print(1)
        continue
    if l == 1:
        print(len(li[r-1]))
        continue
    print(len(li[r-1].items() - li[l-2].items()))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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(np.unique(c[L-1:R])))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, q = map(int, input().split())
    s = list(map(int, input().split()))
    for _ in range(q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        x = len(set(s[l:r + 1]))
        print(x)

solve()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=[int(j)for j in input().split()]
n+=1
data=[set() for i in range(n*2)]
def update(i,x):
    i+=n
    data[i].add(x)
    i//=2
    while i:
        data[i]=data[i*2]|data[i*2+1]
        i//=2
def query(l,r):
    l+=n
    r+=n
    s=set()
    while l<r:
        if l&1:
            s|=data[l]
            l+=1
        if r&1:
            r-=1
            s|=data[r]
        l//=2
        r//=2
    return len(s)

for i,j in enumerate(c,n):
    data[i].add(j)
for i in range(n-1,0,-1):
    data[i]=data[2*i]|data[2*i+1]
for i in range(q):
    l,r=map(int,input().split())
    print(query(l-1,r))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
N,Q = map(int,input().split())
c = [-1]+list(map(int,input().split()))
lastAppeared = defaultdict(lambda:-1)
ans = [0]*Q
queries = []
for i in range(Q):
    l,r = map(int,input().split())
    queries.append((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
        if lastAppeared[c[curR]] != -1:
            last = lastAppeared[c[curR]]
            BIT_update(last,-1)
        lastAppeared[c[curR]] = curR
        BIT_update(curR,1)
    ans[i] = BIT_query(r)-BIT_query(l-1)
for i in range(Q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:

import numpy as np
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
    table[i]=table[i-1][:]
    table[i][c]+=1

for _ in range(q):
    l,r=map(int,input().split())
    ans=list(np.array(table[r])-np.array(table[l-1]))
    print(n-ans.count(0))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,q=map(int,input().split())
c=list(map(int,input().split()))

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
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 math
import time
from collections import defaultdict, deque
from sys import stdin, stdout, setrecursionlimit
from bisect import bisect_left, bisect_right
class sparse_table:
    def __init__(self,n):
        k=math.ceil(math.log2(n))
        self.k=k
        self.st=[[0]*(k+1) for i in range(n)]
    def build(self,a,n):
        for i in range(n):
            self.st[i][0] = set([a[i]])
        for j in range(1,self.k+1):
            i=0
            while(i + (1 << j) <= n):
                self.st[i][j] = self.st[i][j-1].union(self.st[i + (1 << (j - 1))][j - 1]);
                i+=1
n,q=map(int,stdin.readline().split())
a=list(map(int,stdin.readline().split()))
s=sparse_table(n)
s.build(a,n)
for _ in range(q):
    L,R=map(int,stdin.readline().split())
    L-=1
    R-=1
    ans=set()
    for j in range(s.k,-1,-1):
        if ((1 << j) <= R - L + 1) :
            ans.update(s.st[L][j]);
            L += 1 << j;
    print(len(ans))

Submission status: Time Limit Exceeded

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