Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
3
1

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

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

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

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3



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


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
class segtree:
    ## define what you want to do ,(min, max)
    

    def __init__(self,n):
        self.n = n
        self.tree = [[]]*(2*n)
        
    def build(self, list):
        for i,x in enumerate(list,self.n):
            d = set()
            d.add(x)
            self.tree[i] = d
            
        for i in range(self.n-1,0,-1):
            self.tree[i] = self.tree[i<<1]|self.tree[i<<1 | 1]

    ## take the value of [l,r) 
    def get(self,l,r):
        l += self.n
        r += self.n
        res = set()

        while l < r:
            if l & 1:
                res |= self.tree[l]
                l += 1
            if r & 1:
                res |= self.tree[r-1]
            l >>= 1
            r >>= 1
        return len(res)

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

seg = segtree(n)
seg.build(c)

for i in range(q):
    l,r = map(int,input().split())
    print(seg.get(l-1,r))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split(" "))
c=tuple(map(int,input().split(" ")))
for i in range(q):
    start,finish=map(int,input().split(" "))
    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:
N, Q = map(int, input().split())
c=list(map(int, input().split()))

#kinds = len(np.unique(c))
#idx = []

#for k in kinds:
#    idx.append([i for i, x in enumerate(l_dup) if x == k])
for i in range(Q):
    L, R = map(int, input().split())
    #print(len(np.unique(c[L-1:R])))
    print(len(set(c[L-1:R])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
 
seg_unit = 0
 
 
def seg_f(x, y):
    return x | y
 
 
def build(seg, raw_data):
    N = len(seg) // 2
    seg[N:] = raw_data
    for i in range(N - 1, 0, -1):
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def set_val(seg, i, x):
    N = len(seg) // 2
    i += N
    seg[i] = x
    while i > 1:
        i >>= 1
        seg[i] = seg_f(seg[i << 1], seg[i << 1 | 1])
 
 
def fold(seg, l, r):
    vl = vr = 0
    N = len(seg) // 2
    l, r = l + N, r + N
    while l < r:
        if l & 1:
            vl = seg_f(vl, seg[l])
            l += 1
        if r & 1:
            r -= 1
            vr = seg_f(seg[r], vr)
        l, r = l >> 1, r >> 1
    return seg_f(vl, vr)
 
def main(N, S, query):
    seg = np.zeros(N + N, np.int64)
    build(seg, 1 << S)
    for _ in range(query):
        a, b = map(int,input().split())
        a -= 1
        x = fold(seg, a, b)
        print(bin(x).count('1'))

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i8 = numba.int64
    cc = CC('my_module')
 
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
 
    seg_f = cc_export(seg_f, (i8, i8))
    build = cc_export(build, (i8[:], i8[:]))
    set_val = cc_export(set_val, (i8[:], i8, i8))
    fold = cc_export(fold, (i8[:], i8, i8))
    cc.compile()
 
from my_module import seg_f, build, set_val, fold
 
N, Q = map(int,input().split())
S = np.array(list(map(int,input().split())), np.int64)
 
main(N, S, Q)

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] * 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 in_place_answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    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 queries[qc][1] == i:
            sqqc = queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():

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

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

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


main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
Query = [tuple(map(int, input().split())) for _ in range(Q)]
Ans = []
D = dict()

Ans.append(D.copy())
for c in C:
    if c in D:
        D[c] += 1
    else:
        D[c] = 1
    Ans.append(D.copy())

for l, r in Query:
    l -= 1
    ans = Ans[r].items() - Ans[l].items()
    print(len(ans))

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:
# Python3 code to find number of  
# distinct numbers in a subarray 
MAX = 500001
  
# 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 
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[]
for i in range(q):
  c,d=map(int,input().split())

  queries.append(Query(c-1,d-1,i))
queries.sort(key = lambda x: x.r) 
answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

m = []
r = [0] * n
for cc in c:
    cc = cc-1
    rr = r.copy()
    rr[cc] = rr[cc]+1
    m.append(rr)
    r = rr

m = np.array(m)

for _ in range(q):
    l, r = map(int, input().split())
    if l == 1:
        print(np.count_nonzero(m[r - 1]))
    else:
        print(np.count_nonzero(m[r - 1] - m[l - 2]))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = [int(_) for _ in input().split()]
# print(set(c))
# print(len(set(c)))
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:
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(map(lambda x,y: x==y,table[r],table[l-1]))
    print(n-sum(ans))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    sq = int(N ** 0.5)

    Qu = [[] for _ in range(N // sq + 1)]
    for i in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r
        Qu[l // sq].append((r, l, i))
    ans = [0] * Q
    d = [0] * (N + 1)
    c = 0
    rp, lp = -1, -1
    for qr in Qu:
        qr.sort()
        for r, l, i in qr:
            if rp == -1:
                rp, lp = l, l
            for j in range(rp, r):
                d[C[j]] += 1
                if d[C[j]] == 1:
                    c += 1
            for j in range(r, rp):
                d[C[j]] -= 1
                if d[C[j]] == 0:
                    c -= 1
            for j in range(l, lp):
                d[C[j]] += 1
                if d[C[j]] == 1:
                    c += 1
            for j in range(lp, l):
                d[C[j]] -= 1
                if d[C[j]] == 0:
                    c -= 1
            lp, rp = l, r
            ans[i] = c
    print('\n'.join(str(i) for i in ans))

main()

Submission status: Time Limit Exceeded

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


def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1] = 2**(init_val[i]-1)   
    #built
    for i in range(num-2,-1,-1):
        seg[i] = seg[2*i+1] | seg[2*i+2]


def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = seg[k*2+1] | seg[k*2+2]


def query(p,q): # pからq-1までの最大値
    if q<=p:
        return 0
    p += num-1
    q += num-2
    res = 0
    while q-p>1:
        if p&1 == 0:
            res = res | seg[p]
        if q&1 == 1:
            res = res | seg[q]
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = res | seg[p]
    else:
        res = res | seg[p] | seg[q]
    return popcount(res)


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

#num:n以上の最小の2のべき乗
num = 2**(n-1).bit_length()
INF = 2**31-1
seg = [0]*(2*num)

init(a)
for i in range(q):
    l, r = map(int,input().split())
    print(query(l-1,r))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

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

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1


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

C=[None]
for c in list(map(int,input().split())):
    C.append(c)

pos=[list(map(lambda x:int(x),input().split())) for i in range(Q)]
pos = sorted([[l,r,i] for i,(l,r) in enumerate(pos)],key=lambda x:x[1])


last_appeared=[0]*(N+1) #last_appeared[i]: iが最後に現れた場所(1-origin)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
#for (l,r),i in pos:
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r]]=cur_r #lastの更新
        cur_r+=1

    ans[i]=B.sum(r)-B.sum(l-1)


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

Submission status: Time Limit Exceeded

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


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

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

    # クエリは0-indexedで[l, r)
    class SparseTable():
        def __init__(self, A):
            # A: 処理したい数列
            self.N = len(A)
            self.K = self.N.bit_length() - 1
            self.table = [set()] * (self.N * (self.K + 1))
            for i, a in enumerate(A):
                self.table[i] = a
            for k in range(1, self.K + 1):
                for i in range(self.N):
                    j = i + (1 << (k - 1))
                    if j <= self.N - 1:
                        self.table[i + k * self.N] = STfunc(self.table[i + (k - 1) * self.N],
                                                            self.table[j + (k - 1) * self.N])

        def query(self, l, r):
            # [l, r)の最小値を求める
            k = (r - l).bit_length() - 1
            return STfunc(self.table[l + k * self.N], self.table[r - (1 << k) + k * self.N])

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

    ST = SparseTable(C)
    for _ in range(Q):
        l, r = map(int, input().split())
        #print(ST.query(l-1, r))
        print(len(ST.query(l-1, r)))


if __name__ == '__main__':
    main()

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 
n,q=map(int,input().split())
a=list(map(int,input().split()))
queries=[]
for i in range(q):
  c,d=map(int,input().split())

  queries.append(Query(c-1,d-1,i))
queries.sort(key = lambda x: x.r) 
answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

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

def buildTree(tree,a,n):
	for i in range(n):
		tree[i+n] = 1 << (a[i]-1) 
	for i in range(n-1,0,-1):
		tree[i] = tree[2*i] | tree[2*i+1]

def query(tree,left,right,n):
	left += n
	right += n
	ans = 0
	while(left < right):
		if(left&1):
			ans = ans | tree[left]
			left += 1
		if(right&1):
			right -= 1
			ans |= tree[right]
		left //= 2
		right //= 2
	return ans

N,Q = list(map(int,input().split()))
C = list(map(int,input().split()))
tree = [0]*(2*N)
buildTree(tree,C,N)

for q in range(Q):
	lo,hi = list(map(int,input().split()))
	r = query(tree,lo-1,hi,N)
	print(bin(r).count('1'))

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] * 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 in_place_answer_queries(n, q, cs, queries):
    ft = FenwickTree(n + 1)
    last_visit = [-1] * MAX_VAL
    queries.sort(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 queries[qc][1] == i:
            sqqc = queries[qc]
            ans[sqqc[2]] = ft.sum_range(sqqc[0], sqqc[1] + 1)
            qc += 1
    return ans


def main():
    n, q = (int(z) for z in input().split())
    cs = [int(c) for c in input().split()]
    queries = [None] * q
    for i in range(q):
        le, ri = (int(z) - 1 for z in input().split())
        queries[i] = (le, ri, i)
    ans = in_place_answer_queries(n, q, cs, queries)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, raw_input().split())
cis = map(int, raw_input().split())

h = {}
for i in range(n):
	s = set()
	for j in range(i,n):
		s.add(cis[j])
		h[(i,j)] = len(s)
		if len(s) == n:
			break
	j+=1
	while(j < n):
		h[(i,j)] = n
		j+=1
for _ in range(q):
	u,v = map(int, raw_input().split())
	print h[(u-1,v-1)]

Submission status: Time Limit Exceeded

Solution code:
import collections
from sys import stdin
input=stdin.readline
n,q=map(int,input().split())
a=list(map(int,input().split()))
for i in range(q):
  x,y=map(int,input().split())
  print(len(collections.Counter(a[x-1:y])))

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class SegmentTree:
    """Segment Tree (Point Update & Range Query)
    Query
        1. update(i, val): update i-th value(0-indexed) to val
        2. query(low, high): find f(value) in [low, high)
    Complexity
        time complexity: O(log n)
        space complexity: O(n)
    """
    def __init__(self, N, f, default):
        self.N = 1 << (N-1).bit_length()
        self.default = default
        self.f = f
        self.segtree = [self.default] * ((self.N << 1) - 1)
    @classmethod
    def create_from_array(cls, arr, f, default):
        N = len(arr)
        self = cls(N, f, default)
        for i in range(N):
            self.segtree[self.N - 1 + i] = arr[i]
        for i in reversed(range(self.N - 1)):
            self.segtree[i] = self.f(
                self.segtree[(i << 1) + 1], self.segtree[(i << 1) + 2])
        return self
    def update(self, i, val):  # update
        i += self.N - 1
        self.segtree[i] = val
        while i > 0:
            i = (i - 1) >> 1
            self.segtree[i] = self.f(
                self.segtree[(i << 1)+1], self.segtree[(i << 1)+2])
    def query(self, low, high):  # query
        # query [l, r)
        low, high = low + self.N, high + self.N
        ret = self.default
        while low < high:
            if low & 1:
                ret = self.f(ret, self.segtree[low-1])
                low += 1
            if high & 1:
                high -= 1
                ret = self.f(ret, self.segtree[high-1])
            low, high = low >> 1, high >> 1
        return ret
    def get(self, k):  # get k-th value(0-indexed)
        return self.segtree[k+self.N-1]
    def all(self):  # all range query
        return self.segtree[0]

N, Q = MAP()
c = LIST()

segtree = SegmentTree(N+1, lambda x,y:x|y, set())
for i, x in enumerate(c):
    segtree.update(i, set([x]))

ans = [0]*Q
for i in range(Q):
    l, r = MAP()
    ans[i] = len(segtree.query(l-1, r))
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import copy
from collections import defaultdict
n, q = map(int,input().split())
c = list(map(int,input().split()))
ds = [defaultdict(int)]

for cc in c:
    d = copy.copy(ds[-1])
    d[cc] += 1
    ds += [d]
for i in range(q):
    l,r = map(int, input().split())
    ans = 0
    for k,v in ds[r].items():
        if ds[l-1][k] < v:
            ans += 1
    print(ans)

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 = [-1]*(N+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:
from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = []
for i in range(q):
    l, r = list(map(int, input().split()))
    query.append((r, l, i))

query.sort()
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for x in range(q):
    r, l, z = query[x]
    for i in range(right, r):
        if appear[c[i]] != -1:
            bit.add(appear[c[i]]+1, -1)
        appear[c[i]] = i
        bit.add(appear[c[i]]+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

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

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    """1-indexed"""

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

    def sum(self, i):
        s = 0
        while i > 0:
            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, input().split())
C = tuple(map(int, input().split()))
queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))
queries.sort(key=lambda x: x[1])

b = Bit(N)
last = [None] * (N + 1)

cur = 1
ans = [None] * Q
for l, r, i in queries:
    while cur <= r:
        if last[C[cur - 1]] is not None:
            b.add(last[C[cur - 1]], -1)
        last[C[cur - 1]] = cur
        b.add(cur, 1)
        cur += 1
    ans[i] = b.sum(r) - b.sum(l - 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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