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:
def main():
    n,q=map(int,input().split())
    lst=[0]*n
    clst=tuple(map(int,input().split()))
    work={}
    for i in range(n):
        if clst[i] in work:
            work[clst[i]]+=1
        else :
            work[clst[i]]=1
        lst[i]=work.copy()
    
    for _ in range(q):
        l,r=map(int,input().split())
        rwork=lst[r-1]
        if l==1 :
            print(len(rwork))
            continue
        lwork=lst[l-2]
        sm=len(rwork)
        for x in rwork:
            if x not in lwork : continue
            if rwork[x]==lwork[x]:
                sm-=1
        print(sm)

main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
 
MAX = 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 answeringQueries(arr, n, queries, q): 
 
  bit = [0] * (n + 1) 

  last_visit = [-1] * MAX
  ans = [0] * q 

  query_counter = 0
  for i in range(n): 

    if last_visit[arr[i]] != -1: 
      update(last_visit[arr[i]] + 1, -1, bit, n) 

    last_visit[arr[i]] = i 
    update(i + 1, 1, bit, n) 

    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

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




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

Submission status: Time Limit Exceeded

Solution code:
import collections

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

#x=list()
#for i in range(n):
#    x[i] = len(collections.Counter(c[0:i]))

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

Submission status: Time Limit Exceeded

Solution code:
class SegTree:  # 0-index !!!
    """
    fx: モノイドXでの二項演算
    ex: モノイドXでの単位元
    init(seq, fx, ex): 配列seqで初期化 O(N)
    update(i, x): i番目の値をxに更新 O(logN)
    query(l, r): 区間[l,r)をfxしたものを返す O(logN)
    get(i): i番目の値を返す
    show(): 配列を返す
    """

    def __init__(self, seq, fx, ex):
        self.n = len(seq)
        self.fx = fx
        self.ex = ex
        self.size = 1<<(self.n - 1).bit_length()
        self.tree = [ex] * (self.size * 2)
        # build
        for i, x in enumerate(seq, start=self.size):
            self.tree[i] = x
        for i in reversed(range(1, self.size)):
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def set(self, i, x):  # O(log(n))
        i += self.size
        self.tree[i] = x
        while i:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, i, x):
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.fx(self.tree[2 * i], self.tree[2 * i + 1])

    def query(self, l, r):  # l = r の場合はたぶんバグるので注意
        tmp_l = self.ex
        tmp_r = self.ex
        l += self.size
        r += self.size
        while l < r:
            if l & 1:
                tmp_l = self.fx(tmp_l, self.tree[l])
                l += 1
            if r & 1:
                tmp_r = self.fx(self.tree[r - 1], tmp_r)  # 交換法則を仮定しない(順序大事に)
            l >>= 1
            r >>= 1
        return self.fx(tmp_l, tmp_r)

    def get(self, i):
        return self.tree[self.size + i]

    def show(self):
        return self.tree[self.size: self.size + self.n]

# ---------------------- #

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

n, q = (int(x) for x in input().split())
C = list(int(x) for x in input().split())
seq = [set() for _ in range(n)]
for i in range(n):
    seq[i].add(C[i])
queries = [tuple(int(x) for x in input().split()) for _ in range(q)]
seg = SegTree(seq, fx=set_func, ex=set())
for l, r in queries:
    l -= 1
    ans = len(seg.query(l, r))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from io import BytesIO, IOBase
# region fastio
 
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)
input = lambda: sys.stdin.readline().rstrip("\r\n")
 
# endregion
from math import ceil,log,floor 
  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 
MAX = 500005 
r =ceil(log(MAX,2))
S  = pow(2,r+2)-1
segment=[[] for i in range(S)]
  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 
def build(i, s, e, arr): 
  
    # If start is equal to end then 
    # append the array element 
    if (s == e): 
        segment[i].append(arr[s]) 
        return
  
    # Else divide the range into two halves 
    # (start to mid) and (mid+1 to end) 
    # first half will be the left node 
    # and the second half will be the right node 
    build(2 * i, s, (s + e) // 2, arr) 
    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 
  
    # Insert the sets of right and left 
    # node of the segment tree 
    segment[i].append(segment[2 * i]) 
  
    segment[i].append(segment[2 * i + 1]) 
  
# Query in an range a to b 
def query(node, l, r, a, b): 
    left, right, result=[],[],[] 
  
    # If the range is out of the bounds 
    # of this segment 
    if (b < l or a > r): 
        return result 
  
    # If the range lies in this segment 
    if (a <= l and r <= b): 
        return segment[node] 
  
    # Else query for the right and left 
    # leaf node of this subtree 
    # and append them into the set 
    left = query(2 * node, l, (l + r) // 2, a, b) 
    result.append(left) 
  
    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 
    result.append(right) 
  
    # Return the result 
    return result 
def answer(ans): 
    d = {} 
    for i in str(ans): 
        if i not in ['[',',',']',' ']: 
            d[i]=1
    return len(d) 
  
# Initialize the segment tree 
def init(n): 
      
    # Get the height of the segment tree 
    h = ceil(log(n, 2)) 
    h = (2 * (pow(2, h))) - 1
  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 
def getDistinct(l, r, n): 
      
    # Query for the range set 
    ans = query(1, 0, n - 1, l, r) 
  
    print(answer(str(ans))) 


N,Q=list(map(int,input().split()))
init(N)
c=list(map(int,input().split()))
build(1,0,N-1,c)
for i in range(Q):
    l,r=list(map(int,input().split()))
    getDistinct(l-1,r-1,N)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from operator import or_


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()

def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array):
        _len = len(array)
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [set()] * self.__size + \
            array + [set()] * (self.__size - _len)

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = self.__tree[i * 2] | self.__tree[i * 2 + 1]
    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = set()
        while l < r:
            if l & 1:
                ret |= self.__tree[l]
                l += 1
            if r & 1:
                r -= 1
                ret |= self.__tree[r]
            l //= 2
            r //= 2
        return ret

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


@mt
def slv(N, Q, C, LR):
    st = SegmentTree([{c} for c in C])

    for l, r in LR:
        l -= 1
        r -= 1
        v = st.query(l, r+1)
        print(len(v))

def main():
    N, Q = read_int_n()
    C = read_int_n()
    LR = [read_int_n() for _ in range(Q)]
    slv(N, Q, C, LR)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
x=lambda:list(map(int,input().split()))

n,q = x()
arr = x()

for _ in range(q):
	l,r = x()
	l-=1
	print(len(list(set(arr[l:r]))))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    sq = int(n ** .5)
    g = [0]*q
    for i in range(q):
        l, r = nm()
        gr = l // sq
        g[i] = (gr << 60) + ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    d = [0]*(n+1)
    cl = 0; cr = -1
    cur = 0
    for x in g:
        i = x & mask
        x >>= 20
        l = x & mask
        x >>= 20
        r = x & mask
        while r > cr:
            cr += 1
            if d[c[cr]] == 0:
                cur += 1
            d[c[cr]] += 1
        while l < cl:
            cl -= 1
            if d[c[cl]] == 0:
                cur += 1
            d[c[cl]] += 1
        while cr > r:
            if d[c[cr]] == 1:
                cur -= 1
            d[c[cr]] -= 1
            cr -= 1
        while l > cl:
            if d[c[cl]] == 1:
                cur -= 1
            d[c[cl]] -= 1
            cl += 1
        ans[i] = cur
    prn(ans)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s = list(map(str,input().split()))
  # print(s)
from collections import *
d=defaultdict(list)
for i,c in enumerate(s):
    d[c]+=[i]
from bisect import *
for _ in range(q):
    y,z=input().split()
    y=int(y)-1
    print(sum(bisect(l,int(z)-1)-bisect_left(l,y)>0 for l in d.values()))

Submission status: Time Limit Exceeded

Solution code:
# Python3 code to find number of
# distinct numbers in a subarray
MAX = 6 * 10**5


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


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

    answeringQueries(c, n, queries, q)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():

    N, Q = map(int, input().split())
    C = list(map(lambda x: int(x) - 1, input().split()))

    M = int(N**0.5)
    K = (N + M - 1) // M

    query = []

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

    query.sort(key = lambda x: (x[0] // M, x[1]))

    lt, rt = 0, 0
    S = [0 for _ in range(N)]
    tmp = 0
    res = [0 for _ in range(Q)]

    for l, r, i in query:
        while lt > l:
            lt -= 1
            if S[C[lt]] == 0:
                tmp += 1
            S[C[lt]] += 1
        while rt < r:
            if S[C[rt]] == 0:
                tmp += 1
            S[C[rt]] += 1
            rt += 1
        while lt < l:
            if S[C[lt]] == 1:
                tmp -= 1
            S[C[lt]] -= 1
            lt += 1
        while rt > r:
            rt -= 1
            if S[C[rt]] == 1:
                tmp -= 1
            S[C[rt]] -= 1
        res[i] = tmp

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size

    def get_sum(self,i):
        s = 0
        while i:
            s += self.tree[i]
            i -= i & -i
        return s

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

n,q = map(int,readline().split())
c = list(map(int,readline().split()))
lr = list(map(int,read().split()))
it = iter(lr)
lr2 = []
for i,l,r in zip(range(q),it,it):
    lr2.append((r-1,l-1,i))

lr2.sort()
st = BIT(n+1)
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
for r,l,i in lr2:
    while(c_ind <= r):
        st.add(c_ind+1,1)
        bef = before[c[c_ind]]
        if(bef!=-1):
            st.add(bef+1,-1)
        before[c[c_ind]] = c_ind
        c_ind += 1

    ans[i] = st.get_sum(r+1) - st.get_sum(l)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [0] * (self.size * 2 - 1)
    
    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 0
        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)
for i in range(N):
    segt.update(i, (1<<C[i]))

for i in range(Q):
    l, r = map(int, input().split())
    x = segt.get(int(l)-1,int(r))
    ans = 0
    for i in range(26):
        if x>>i&1: ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
s = list(map(str,input().split()))
  # print(s)
from collections import *
d=defaultdict(list)
for i,c in enumerate(s):
    d[c]+=[i]
from bisect import *
for _ in range(q):
    y,z=input().split()
    y=int(y)-1
    print(sum(bisect(l,int(z)-1)-bisect_left(l,y)>0 for l in d.values()))

Submission status: Time Limit Exceeded

Solution code:

import collections
from functools import lru_cache


# NOTE:
# This segment is of 1-based indexing, so provided array should be 1-indexed
class SegmentTree:
    def __init__(self, arr):
        self.N = len(arr)
        self.arr = arr
        segTreeSize = 2*self.N

        self.segTree = [set() for _ in range(segTreeSize)]

        for i in range(self.N):
            self.segTree[self.N + i] = set([self.arr[i]])

        self.buildTree()

    def buildTree(self):
        for i in range(self.N-1, 0, -1):
            self.segTree[i] = self.segTree[i << 1].union(
                self.segTree[(i << 1) | 1])

    # Range query [l, r)
    def query(self, l, r):
        ans = set()
        l += self.N
        r += self.N

        while l < r:
            if l & 1:
                ans = ans.union(self.segTree[l])
                l += 1

            if r & 1:
                r -= 1
                ans = ans.union(self.segTree[r])

            l >>= 1
            r >>= 1

        return len(ans)


def read():
    return input().strip()


def readInt():
    return int(input().strip())


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


def solve(N, Q, arr, queries):
    segTree = SegmentTree([0] + arr)
    ans = []

    for l, r in queries:
        ans.append(segTree.query(l, r+1))

    return "\n".join(map(str, ans))


[N, Q] = readList()
arr = readList()
queries = []

for _ in range(Q):
    queries.append(readList())

print(solve(N, Q, arr, queries))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SparseTable:
    def __init__(self, aa):
        w = len(aa)
        h = w.bit_length()
        table = [aa] + [[-1] * w for _ in range(h - 1)]
        tablei1 = table[0]
        for i in range(1, h):
            tablei = table[i]
            for j in range(w-(1<<i)+1):
                rj = j + (1 << (i - 1))
                tablei[j] = tablei1[j]|tablei1[rj]
            tablei1 = tablei
        self.table = table

    def val(self, l, r):
        i = (r - l).bit_length() - 1
        tablei = self.table[i]
        L = tablei[l]
        R = tablei[r - (1 << i)]
        return L|R

n,q=MI()
cc=MI()
aa=[1<<c for c in cc]
sp=SparseTable(aa)
for _ in range(q):
    l,r=MI()
    print(bin(sp.val(l-1,r)).count("1"))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    sq = 600
    g = [0]*q
    for i in range(q):
        l, r = nm()
        gr = l // sq
        g[i] = (gr << 60) + ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    d = [0]*(n+1)
    cl = 0; cr = -1
    cur = 0
    for x in g:
        i = x & mask
        x >>= 20
        l = x & mask
        x >>= 20
        r = x & mask
        while r > cr:
            cr += 1
            if d[c[cr]] == 0:
                cur += 1
            d[c[cr]] += 1
        while l < cl:
            cl -= 1
            if d[c[cl]] == 0:
                cur += 1
            d[c[cl]] += 1
        while cr > r:
            if d[c[cr]] == 1:
                cur -= 1
            d[c[cr]] -= 1
            cr -= 1
        while l > cl:
            if d[c[cl]] == 1:
                cur -= 1
            d[c[cl]] -= 1
            cl += 1
        ans[i] = cur
    prn(ans)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:

# coding: utf-8

# In[1]:


N, Q = map(int,input().split())
c = list( map(int,input().split()) )
RNG_list = []
for i in range(Q):
    RNG_list.append( list( map(int,input().split()) ) )


# In[2]:


def color_val_ith(c,l,r):
    check = c[l-1:r]
    return len( list(set(check)) )


# In[4]:


for i in range(Q):
    lr = RNG_list[i]
    print( color_val_ith(c,lr[0],lr[1]) )

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from copy import copy

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

cs = []

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

for i in range(Q):
    l, r = map(int, input().split())
    c3 = copy(cs[r-1])
    if l > 1:
        c3.subtract(cs[l-2])
        c3 = +c3
    print(len(c3))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
def main():
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[]
  for i in range(q):
    l,r=map(int,input().split())
    queries.append((r-1,l-1,i))
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[n]*n
  bitt=BinaryIndexedTree(n+1)
  j=0
  for i in range(n):
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
x=lambda:list(map(int,input().split()))

def build(s,e,index):
	if s==e:
		seg[index] = {arr[s]}
		return
	mid = (s+e)//2
	build(s,mid,2*index)
	build(mid+1,e,2*index+1)
	seg[index] = set(list(seg[2*index]) + list(seg[2*index+1]))
	return

def query(s,e,qs,qe,index):
	if qe<s or qs>e:
		return set()
	
	if s>=qs and e<=qe:
		return seg[index]
	
	mid = (s+e)//2
	left=query(s,mid,qs,qe,2*index)
	right=query(mid+1,e,qs,qe,2*index+1)
	return set(list(left)+list(right))

n,q = x()
arr = x()
seg=[-1]*(4*n+1)
build(0,n-1,1)
for _ in range(q):
	l,r = x()
	l-=1
	r-=1
	print(len(list(query(0,n-1,l,r,1))))

Submission status: Time Limit Exceeded

Solution code:
N, Q = [int(x) for x in input().split()]
colors = input().split()
for q in range(Q):
    l,r = [int(y) for y in input().split()]
    print(len(set(colors[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N,Q=map(int,input().split())
a=tuple(map(int1,input().split()))
lr=[[0,0,i] for i in range(Q)]
for i in range(Q):
    lr[i][0],lr[i][1]=map(int1,input().split())
lr.sort(key=lambda t: t[1],reverse=1)
class RangeBIT:
    def __init__(self,n):
        self.p=self.BIT(n+1)
        self.q=self.BIT(n+1)
    
    def add(self,s,t,x):
        self.p.add(s,-x*s)
        self.p.add(t,x*t)
        self.q.add(s,x)
        self.q.add(t,-x)
    
    def sum(self,s,t):
        return self.p.sum(t)+self.q.sum(t)*t-self.p.sum(s)-self.q.sum(s)*s
    
    class BIT:
        def __init__(self,n):
            self.num=n
            self.dat=[0]*(self.num+1)
        
        def add(self,i,x):
            i+=1
            while i<=self.num:
                self.dat[i]+=x
                i+=i&-i
        
        def sum(self,i):
            i+=1
            s=0
            while i>0:
                s+=self.dat[i]
                i-=i&-i
            return s

b=RangeBIT(N)
lastap=[-1]*N
ans=[-1]*Q
l,r,j=lr.pop()
for i in range(N):
    if lastap[a[i]]!=-1:
        b.add(lastap[a[i]],lastap[a[i]]+1,-1)
    b.add(i,i+1,1)
    lastap[a[i]]=i
    while r==i:
        ans[j]=b.sum(l,r+1)
        if lr:
            l,r,j=lr.pop()
        else:
            l,r,j=-1,-1,-1
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

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

import sys
input=sys.stdin.readline

class SegmentTreeSet():
  def __init__(self,n,init):
    self.offset=2**((n-1).bit_length())
    self.tree=[init]*(2*self.offset)
    self.init=init
  def update(self,pos,val):
    pos+=self.offset
    self.tree[pos]=self.tree[pos]|val
    while pos>1:
      pos=pos//2
      self.tree[pos]=self.tree[2*pos]|self.tree[2*pos+1]
  def query(self,l,r):
    l+=self.offset
    r+=self.offset
    ret=self.init
    while l<=r:
      ret=ret|self.tree[r]
      r=(r-1)//2
      ret=ret|self.tree[l]
      l=(l+1)//2
    return ret

n,q=map(int,input().split())
arr=list(map(int,input().split()))
st=SegmentTreeSet(n,set())
for i in range(n):
    tmp=set()
    tmp.add(arr[i])
    st.update(i,tmp)
for _ in range(q):
    l,r=map(int,input().split())
    l-=1
    r-=1
    print(len(st.query(l,r)))

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    class SegmentTree:
        def __init__(self, size, f=lambda x,y : x+y, default=0):
            self.size = 2**(size-1).bit_length()
            self.default = default
            self.dat = [default]*(self.size*2)
            self.f = f

        def update(self, i, x):
            i += self.size
            self.dat[i] = x
            while i > 0:
                i >>= 1
                self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

        def get(self, a, b=None):
            if b is None:
                b = a + 1
            l, r = a + self.size, b + self.size
            lres, rres = self.default, self.default
            while l < r:
                if l & 1:
                    lres = self.f(lres, self.dat[l])
                    l += 1

                if r & 1:
                    r -= 1
                    rres = self.f(self.dat[r], rres)
                l >>= 1
                r >>= 1
            res = self.f(lres, rres)
            return res
    n,Q = LI()
    c = LI()
    q = LIR(Q)
    q = [[i,q[i]] for i in range(Q)]
    q.sort(key = lambda x:x[1][1])
    s = SegmentTree(n)
    i = 0
    p = [None]*(n+1)
    ans = [0]*Q
    for ind,(l, r) in q:
        l -= 1
        while i < r:
            ci = c[i]
            j = p[ci]
            if j is not None:
                s.update(j,0)
            s.update(i,1)
            p[ci] = i
            i += 1
        ans[ind] = s.get(l,r)
    for i in ans:
        print(i)
    return

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

Submission status: Time Limit Exceeded

Solution code:
X=list(map(int, input().split())) 
c=list(map(int, input().split())) 
for i in range(X[1]):
  z=list(map(int, input().split())) 
  a=c[z[0]-1:z[1]]
  print(len(set(a)))