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:
#region bcf
# code section by Barry Fam
#
# pylint: disable= reimported
#region rangedata.py
#region hyperlist.py
import itertools

# def hyperlist(*dim, default_factory=None):
def hyperlist(*dim, **kwarg):
    default_factory = kwarg.pop("default_factory", None)

    ranges = [range(n) for n in dim]

    h = [None]*dim[0]
    for dd in range(1, len(dim)):
        for u in itertools.product(*ranges[:dd]):
            hyperlist_setitem(h, u, [None]*dim[dd])

    if default_factory:
        for u in itertools.product(*ranges):
            hyperlist_setitem(h, u, default_factory())

    return h

def hyperlist_setitem(h, u, a):
    ptr = h
    for i in u[:-1]: ptr = ptr[i]
    ptr[u[-1]] = a

def hyperlist_getitem(h, u):
    ptr = h
    for i in u: ptr = ptr[i]
    return ptr

#endregion hyperlist.py
###############################################################################
import operator
import collections
import itertools
import functools
import math as m
try: m.prod
except AttributeError:
    def _prod(iterable, start=1):
        for x in iterable: start *= x
        return start
    m.prod = _prod


class RangeOperators:
    '''
    Data class to define the behavior of a range data structure

    new() := factory for zero values, e.g. int()

    query(a, b) := the binary query function of the tree. e.g. operator.add() for a cumulative sum
    q_inverse(a, b) := the inverse of the query function, if it exists. required for a Fenwick tree

    update(t, x) := define how the tree will be updated: return the new value of t if updated with x
    u_distributive(t, x, w) := return the new value of t if its w leaves are updated by x. required for lazy propagation
    u_commutative: bool := True if the update operation is commutative. e.g. add() is; but "set to" is not
    '''

    __slots__ = [
        "new",
        "query",
        "q_inverse",
        "update",
        "u_distributive",
        "u_commutative",
    ]

    _defaults = dict(
        new= int,
        query= operator.add,
        q_inverse= operator.sub,
        update= operator.add,
        u_distributive= lambda t, x, w: t + x*w,
        u_commutative= True,
    )

    def __init__(self, **kwarg):
        d = kwarg or self._defaults
        for k, v in d.items():
            setattr(self, k, v)

MAXQUERY = RangeOperators(
    new= int,
    query= max,
    q_inverse= None,
    update= operator.add,
    u_distributive= lambda t, x, w: t + x,
    u_commutative= True,
)

MINQUERY = RangeOperators(
    new= int,
    query= min,
    q_inverse= None,
    update= operator.add,
    u_distributive= lambda t, x, w: t + x,
    u_commutative= True,
)

SETUPDATE = RangeOperators(
    new= int,
    query= operator.add,
    q_inverse= operator.sub,
    update= lambda t, x: x,
    u_distributive= lambda t, x, w: x*w,
    u_commutative= False,
)


class SegmentTree:
    """
    SegmentTree(n: int) -> new tree of size n
    SegmentTree(iterable) -> new tree, initialized

    Methods:

    update_point(i, value)
    update_range(start, stop, value)
    update_consecutive_points(start, stop, iterable)

    query_point(i)
    query_range(start, stop)
    """

    def __init__(self, arg, sparse=False, ops=RangeOperators(), **kwarg):
        # super().__init__(**kwarg)
        super(SegmentTree, self).__init__(**kwarg)

        try:
            init = list(arg)
            dim = len(init)
        except TypeError:
            init = None
            dim = arg

        self.dim = dim
        self.ops = ops

        self._lazy = self.ops.u_distributive is not None
        self._clean = True

        if sparse:
            self._tree = collections.defaultdict(ops.new)

            @functools.lru_cache(maxsize=dim)
            def seglen(u):
                if u >= self.dim: return 1
                return seglen(u<<1) + seglen(u<<1|1)

            self._seglen = seglen

            if self._lazy:
                self._pending = collections.defaultdict(lambda: None)

        else:
            self._tree = [ops.new() for _ in range(dim*2)]

            seglen_precomp = [1]*dim*2
            for u in reversed(range(1, dim)):
                seglen_precomp[u] = seglen_precomp[u<<1] + seglen_precomp[u<<1|1]

            self._seglen = seglen_precomp.__getitem__

            if self._lazy:
                self._pending = [None]*dim

        if init:
            self.update_consecutive_points(0, dim, init)


    # Iterators

    def _downward_path(self, i):
        """Iterate over tree indexes from root to just above raw index i"""
        u = self.dim + i
        for s in range(u.bit_length()-1, 0, -1):
            yield u >> s

    def _upward_path(self, i):
        """Iterate over tree indexes from just above raw index i to root"""
        u = self.dim + i
        while u > 1:
            u >>= 1
            yield u

    def _downward_fill(self, i, j):
        """Iterate over every tree index that is an ancestor of raw index range [i,j), from root downwards"""
        n = self.dim
        l = n+i
        r = n+j-1
        for s in range(l.bit_length()-1, 0, -1):
            for u in range(l>>s, (r>>s)+1):
                yield u

    def _upward_fill(self, i, j):
        """Iterate over every tree index that is an ancestor of raw index range [i,j), from just above leaves upwards"""
        n = self.dim
        l = n+i
        r = n+j-1
        while l > 1:
            l >>= 1
            r >>= 1
            for u in reversed(range(l, r+1)):
                yield u

    def _cover_nodes(self, i, j):
        """Iterate over the set of tree indexes whose segments optimally cover raw index range [i,j)"""
        n = self.dim
        l = n+i
        r = n+j
        while l < r:
            if l&1:
                yield l
                l += 1
            if r&1:
                r -= 1
                yield r
            l >>= 1
            r >>= 1


    # Node modification

    def _lazy_update(self, u, value):
        """Update tree index u as if its child leaves had been updated with value"""
        self._tree[u] = self.ops.u_distributive(self._tree[u], value, self._seglen(u))
        if u < self.dim:
            self._clean = False
            if self._pending[u] is None:
                self._pending[u] = value
            else:
                self._pending[u] = self.ops.update(self._pending[u], value)

    def _push1(self, u):
        """Apply any pending lazy update at tree index u to its two immediate children"""
        assert u < self.dim
        if self._clean: return

        value = self._pending[u]
        if value is not None:
            for v in (u<<1, u<<1|1):
                self._lazy_update(v, value)

            self._pending[u] = None

    def _build1(self, u):
        """Calculate the query function at tree index u from its two immediate children"""
        assert u < self.dim
        self._push1(u)
        self._tree[u] = self.ops.query(self._tree[u<<1], self._tree[u<<1|1])


    # Node-set modification

    def _push_path(self, i):
        """Push lazy updates from root to raw index i"""
        if self._clean: return
        for u in self._downward_path(i):
            self._push1(u)

    def _push_fill(self, i, j):
        """Push lazy updates from root to raw index range [i,j)"""
        if self._clean: return
        for u in self._downward_fill(i, j):
            self._push1(u)

        if j-i == self.dim: self._clean = True

    def _build_path(self, i):
        """Update tree nodes from raw index i to root"""
        for u in self._upward_path(i):
            self._build1(u)

    def _build_fill(self, i, j):
        """Update all tree ancestors of raw index range [i,j)"""
        for u in self._upward_fill(i, j):
            self._build1(u)

        if j-i == self.dim: self._clean = True


    # Interface

    def update_consecutive_points(self, start, stop, iterable):
        assert 0 <= start < stop <= self.dim

        # push if necessary
        if not self.ops.u_commutative:
            self._push_fill(start, stop-1)

        # write leaves
        for u, value in zip(range(self.dim + start, self.dim + stop), iterable):
            self._tree[u] = self.ops.update(self._tree[u], value)

        # build
        self._build_fill(start, stop-1)

    def query_range(self, start, stop):
        assert start < stop

        for i in {start, stop-1}:
            self._push_path(i)

        node_values = (self._tree[u] for u in self._cover_nodes(start, stop))
        return functools.reduce(self.ops.query, node_values)

    def update_range(self, start, stop, value):
        assert start < stop

        # if no lazy propagation, fall back to writing to leaves
        if not self._lazy:
            self.update_consecutive_points(start, stop, itertools.repeat(value))
            return

        # push if necessary
        if not self.ops.u_commutative:
            for i in {start, stop-1}:
                self._push_path(i)

        # write cover nodes
        for u in self._cover_nodes(start, stop):
            self._lazy_update(u, value)

        # build
        for i in {start, stop-1}:
            self._build_path(i)

    def query_point(self, i):
        return self.query_range(i, i+1)

    def update_point(self, i, value):
        self.update_range(i, i+1, value)


class FenwickTree:
    """
    ft1d = FenwickTree(dim)
    ft3d = FenwickTree(dim1, dim2, dim3)
    etc.

    Methods:

    ft1d.iadd(i, update_value)
    ft3d.iadd((i,j,k), update_value)

    ft1d[i] = set_value
    fr3d[i,j,k] = set_value

    query = ft1d[i1:i2]
    query = ft3d[i1:i2, j1:j2, k1:k2]
    """

    # def __init__(self, *dim, sparse=False, **kwarg):
    def __init__(self, *dim, **kwarg):
        sparse = kwarg.pop("sparse", False)

        # super().__init__(**kwarg)
        super(FenwickTree, self).__init__(**kwarg)

        self.dim = dim
        self.d = len(dim)

        if sparse:
            self._tree = collections.defaultdict(int)
            if self.d > 1:
                self._tree_setitem = self._tree.__setitem__
                self._tree_getitem = self._tree.__getitem__
        else:
            self._tree = hyperlist(*dim, default_factory=int)
            if self.d > 1:
                self._tree_setitem = functools.partial(hyperlist_setitem, self._tree)
                self._tree_getitem = functools.partial(hyperlist_getitem, self._tree)

        if self.d == 1:
            self.iadd = self._iadd_1d
            self._getitem = self._getitem_1d
        else:
            self.iadd = self._iadd_dd
            self._getitem = self._getitem_dd

    def __setitem__(self, key, value):
        self.iadd(key, value-self[key])

    def __getitem__(self, key):
        return self._getitem(key)

    @staticmethod
    def _set_index_iter(i, n):
        """Iterate over the tree indices < n which are affected when setting raw index i"""
        if i == 0:
            yield 0
            return

        while True:
            yield i
            i += i & -i  # increment LSB
            if i >= n: return

    @staticmethod
    def _get_index_iter(i, j):
        """
        Iterate over the tree indices whose sum equals the sum over the raw range (j,i] -- note that i > j
        Each index is returned as (index, sign) where sign is +1 or -1 for inclusion-exclusion
        """
        if i < 0: return
        if j < 0:
            yield 0, +1
            j = 0

        while i > j:
            yield i, +1
            i &= i-1  # decrement LSB
        while j > i:
            yield j, -1
            j &= j-1  # decrement LSB

    def _iadd_1d(self, key, value):
        assert 0 <= key < self.dim[0]

        for i in self._set_index_iter(key, self.dim[0]):
            self._tree[i] += value

    def _iadd_dd(self, key, value):
        assert len(key) == self.d
        assert all(0 <= i < self.dim[dd] for dd, i in enumerate(key)), "index out of range"

        index_iters = [self._set_index_iter(i, self.dim[dd]) for dd, i in enumerate(key)]
        for u in itertools.product(*index_iters):
            g = self._tree_getitem(u)
            self._tree_setitem(u, g+value)

    def _getitem_1d(self, key):
        if isinstance(key, slice):
            assert key.step is None
            start, stop, _ = key.indices(self.dim[0])
            if stop < start: stop = start
            i, j = stop-1, start-1
        else:
            i, j = key, key-1

        assert -1 <= j <= i < self.dim[0], "index out of range"

        sigma = 0
        for k, sign in self._get_index_iter(i, j):
            sigma += sign * self._tree[k]

        return sigma

    def _getitem_dd(self, key):
        index_iters = []
        for dd, k in enumerate(key):
            if isinstance(k, slice):
                assert k.step is None
                start, stop, _ = k.indices(self.dim[dd])
                if stop < start: stop = start
                itr = self._get_index_iter(stop-1, start-1)
            else:
                assert 0 <= k < self.dim[dd], "index out of range"
                itr = self._get_index_iter(k, k-1)

            index_iters.append(itr)

        assert len(index_iters) == self.d, "mismatched key dimensions"

        sigma = 0
        for i_sign_pairs in itertools.product(*index_iters):
            u, signs = zip(*i_sign_pairs)
            sign = m.prod(signs)

            sigma += sign * self._tree_getitem(u)

        return sigma

#endregion rangedata.py
#endregion bcf
###############################################################################

import sys
def input(itr=iter(sys.stdin.readlines())):  # pylint: disable= redefined-builtin
    return next(itr).rstrip('\n\r')
###############################################################################

UNIONQUERY = RangeOperators(
    new= frozenset,
    query= frozenset.union,
    q_inverse= None,
    update= frozenset.union,
    u_distributive= None,
    u_commutative= True,
)

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

sets = [frozenset([x]) for x in c]
segtree = SegmentTree(sets, ops=UNIONQUERY)

for _ in range(Q):
    l, r = map(int, input().split())
    query = segtree.query_range(l-1, r-1+1)
    print(len(query))

Submission status: Time Limit Exceeded

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

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


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


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


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


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



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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = [0]
c += list(map(int,input().split()))
for _ in range(q):
    i,j = map(int, input().split())
    print(len(set(c[i:j+1])))

Submission status: Time Limit Exceeded

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

for query in queries:
    l, r = query
    target = set(c[l-1 : r])
    print(len(target))

Submission status: Time Limit Exceeded

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

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

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

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LR = [ tuple( map( int, input().split())) for _ in range(Q)]
    LRI = []
    for i, x in enumerate(LR):
        LRI.append((x[1], x[0], i))
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import Counter


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


def solve(N, Q, C, LR):
    Z = [Counter() for i in range(N+1)]
    for i in range(N):
        Z[i+1] = Z[i] + Counter([C[i]])
    for l, r in LR:
        z = Z[r]-Z[l-1]
        print(len(z))


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

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

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

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

    unit = set()

    class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
        def __init__(self, N, unit):
            self.N = N
            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.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 = vL | self.tree[L]
                    L += 1
                if R & 1:
                    R -= 1
                    vR = self.tree[R] | vR
                L >>= 1
                R >>= 1
            return vL | vR

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

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 998244353


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

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

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

n, q = LI()
ans = [0] * q
C = LI()
Q = []
for i in range(q):
    l, r = LI()
    Q += [(l-1, 0, i)]
    Q += [(r-1, 1, i)]

Q.sort()
Q += [(INF, 0, 0)]
D = defaultdict(lambda:-1)
DD = {}
bit = BIT(q + 1)
now = 0
q_now = 0
l_idx = [INF] * (q + 1)
for i in range(n):
    col = C[i]
    last_idx = D[col]
    D[col] = i
    bit.add(bisect_right(l_idx, last_idx), 1)
# print(bisect_right(l_idx, last_idx), "a")
    while Q[now][0] <= i:
        idx, flg, qq = Q[now]
        if flg:
            ans[qq] = bit.sum(DD[qq])
        else:
            DD[qq] = q_now
            l_idx[q_now] = idx
            q_now += 1
        now += 1
    bit.add(q_now, -1)
#    print(q_now, "b")


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    q.append(tuple(map(int, input().split())))

for query in q:
    a = set(c[query[0] - 1:query[1]])
    print(len(a))

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

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

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LR = [ tuple( map( int, input().split())) for _ in range(Q)]
    LRI = []
    for i, x in enumerate(LR):
        LRI.append((x[1], x[0], i))
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_left
from bisect import bisect

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

d = defaultdict(list)

for i,c in enumerate(C):
    d[c]+=[i]

for _ in range(Q):
    l, r = map(int,input().split())
    print(sum(bisect(L, r-1)-bisect_left(L, l-1) > 0 for L in d.values()))

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]

    dp = [ [0] * N for _ in range(N) ]
    for i in range(N):
        dp[i][i] = 1

    for left in range(N):
        Flags = [False] * N
        N_colors = 0
        for right in range(left, N):
            color = colors[right]-1

            if(Flags[color]==False):
                Flags[color] = True
                N_colors += 1
            dp[left][right] = N_colors
    for i in range(Q):
        query = Queries[i]
        left = query[0]-1
        right = query[1]-1
        print(dp[left][right] )

Submission status: Time Limit Exceeded

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

for i in range(Q):
    li = l_q[i][0]
    ri = l_q[i][1]
    list_i = l_c[li-1:ri]

    print(len(set(list_i)))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

n = 1
while n < N:
  n *= 2
  
seg = [set() for i in range(2 * n - 1)]

#segment-tree : init;
for i in range(n):
  c = C[i] if i < N else C[N-1]
  k = i + n - 1
  seg[k].add(c)
  while k > 0:
    k = (k-1) // 2
    seg[k].add(c)

#print(seg)

def query(L, R, k, l, r):
  if r <= L or R <= l:
    return set()
  if L <= l and r <= R:
    return seg[k]
  left = query(L, R, 2*k + 1, l, (l+r)//2)
  right = query(L, R, 2*k + 2, (l+r)//2, r)
  return left.union(right)

for i in range(Q):
  l, r = map(int, input().split())
  ans = query(l-1, r, 0, 0, n) #(l, r), [0], <0,n>
  #print(ans)
  print( len(ans) )

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
N, Q = map(int, input().split())
count_dic_list = [dict() for i in range(N)]

tdic = {}
for idx, s in enumerate(map(int, input().split())):
    tdic.setdefault(s, 0)
    tdic[s] += 1
    count_dic_list[idx] = copy(tdic)

for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    if l > 0:
        count = 0
        for item in count_dic_list[r].keys():
            n1 = count_dic_list[r][item]
            if item in count_dic_list[l-1].keys():
                n2 = count_dic_list[l-1][item]
            else:
                n2 = 0

            if n1 - n2 > 0:
                count += 1
    else:
        count = len(count_dic_list[r].items())
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import math 

def buildSparseTable(arr, n):
    j = 0
    v = 1 << j
    while v <= n:
        cur = set()
        for i in range(v-1):
            cur.add(arr[i])
        for i in range(v-1, n):
            cur.add(arr[i])
            lookup[i-(v-1)][j] = cur.copy()
            if arr[i-(v-1)] in cur :
                cur.remove(arr[i-(v-1)])
    
        j += 1
        v =  1 << j
    
def query(L, R):

    x = set()
    while L <= R :
        j = int(math.log2(R - L + 1))
        if L > R :
            print('something wrong')
        x = x.union(lookup[L][j])
        L += (1<<j)

    return len(x) 

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

v = int(math.log2(N+1))+1
lookup = [[None]*(v) for _ in range(N)]
buildSparseTable(arr, N)

# print('done')
for _ in range(Q) :
    l, r = map(int, input().split(" "))
    print(query(l-1, r-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_left

n, q = map(int, input().split())
c = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(q)]
INF = 10 ** 9

sm = len(set(c))

d = defaultdict(list)
for i, e in enumerate(c, 1):
    d[e].append(i)

for k in d.keys():
    d[k].append(INF)

for l, r in lr:
    ans = sm
    for v in d.values():
        i = bisect_left(v, l)
        if v[i] > r:
            ans -= 1

    print(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):
  l, r = map(int, input().split())
  print(len(set(c[l-1:r])))