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 bisect,collections,copy,heapq,itertools,math,string
from collections import defaultdict as D
from functools import reduce
import numpy as np
from numba import njit
import sys
sys.setrecursionlimit(10**7)

def _S(): return sys.stdin.readline().rstrip()
def I(): return int(_S())
def LS(): return list(_S().split())
def LI(): return list(map(int,LS()))

N,Q = LI()
_c = LI()
_lr = [LI() for _ in range(Q)]
#A,B = zip(*AB)
lr = np.array(_lr)
c = np.zeros(N + 1)
c[1:] = _c
a = np.zeros(Q)

# setしてlength
# c.insert(0, 0)

# @njit(nopython=True)
a = []
def calc():
    for pair in lr:
        a.append(len(np.unique(c[pair[0]:pair[1]+1])))
        # a.append(len(collections.Counter(c[pair[0]:pair[1]+1])))
        # a.append(len(set(c[pair[0]:pair[1]+1])))
    print(*a, sep="\n")

calc()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

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



def main():
	n,q=MI()
	c=LI()
	for i in range(n):
		c[i]={c[i]}
	#####segfunc#####
	def segfunc(x, y):
		return x.union(y)

	ide_ele =set()
	S=SegTree(c,segfunc,ide_ele)

	for _ in range(q):
		ll,rr=MI()
		print(len(S.query(ll-1,rr)))


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import collections
n, q = list(map(int, input().split()))
l = list(input().replace(' ', ''))
for i in range(q):
  a, b = list(map(int, input().split()))
  print(len(collections.Counter(l[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

# 条件入力
n, q = map(int, input().split())
balls = input().split()

# 回答
for _ in range(q):
	l, r = map(int, input().split())
	print(len(set(balls[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    import collections
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lr = [tuple(map(int, input().split())) for i in range(Q)]

    s = set()
    C = [0]*N
    for i, x in enumerate(c):
        s.add(x)
        C[i] = len(s)

    for l, r in lr:
        l -= 1
        r -= 1
        if l == 0:
            print(C[r])
        else:
            print(len(collections.Counter(c[l:r+1]).keys()))


main()

Submission status: Time Limit Exceeded

Solution code:
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=map(int,input().split())
 
a=list(map(int,input().split()))
tree=[0]*(2*n)
buildTree(tree,a,n)
for _ in range(q):
    l1,r1=map(int,input().split())
    r=query(tree,l1-1,r1,n)
    print(bin(r).count('1'))

Submission status: Time Limit Exceeded

Solution code:
from functools import cmp_to_key
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
*C, = map(int, input().split())

Q = [tuple(map(int, input().split())) for _ in range(P)]
Q = [(i, l, r) for i, (l, r) in enumerate(Q)]

block = int(N**0.5)


def compare(a, b):
    _, la, ra = a
    _, lb, rb = b
    if (la-1)//block != (lb-1)//block:
        return -1 if (la-1)//block < (lb-1)//block else 1
    return -1 if ra < rb else 1


Q.sort(key=cmp_to_key(compare))

ans = [0]*P
cl = cr = 0
S = dict()
S[C[0]] = set([0])
cnt = 1
for i, l, r in Q:
    l -= 1
    r -= 1
    while cl < l:
        x = C[cl]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cl)
        cl += 1

    while l < cl:
        x = C[cl-1]
        if x in S:
            S[x].add(cl-1)
        else:
            S[x] = set([cl-1])
            cnt += 1
        cl -= 1

    while cr < r:
        x = C[cr+1]
        if x in S:
            S[x].add(cr+1)
        else:
            S[x] = set([cr+1])
            cnt += 1
        cr += 1

    while r < cr:
        x = C[cr]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cr)
        cr -= 1

    ans[i] = cnt

print('\n'.join(map(str, 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):
  if i >= N:
    seg[i + n - 1].add( C[N-1] )
    continue
  c = C[i]
  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 = map(int, input().split())
ls = list(map(int, input().split()))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
data = [int(v) for v in sys.stdin.read().split()[::-1]]

def inp():
    return data.pop()

n, q = inp(), inp()
*c, = [inp() for _ in range(n)]


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

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

queries = []
ans = []
for i in range(q):
    l, r = inp(), inp()
    l -= 1
    r -= 1
    queries.append((l, r, i))

# print(interval_length)
queries.sort(key=lambda q: (q[0] // interval_length, q[1]))

freq = [0] * (n + 2)

prev_l = 0
prev_r = -1

cnt = 0
for q_idx in range(len(queries)):
    l, r, i = queries[q_idx]
    while prev_l < l:
        freq[c[prev_l]] -= 1
        if freq[c[prev_l]] == 0:
            cnt -= 1
        prev_l += 1
    while prev_l > l:
        prev_l -= 1
        freq[c[prev_l]] += 1
        if freq[c[prev_l]] == 1:
            cnt += 1
    while prev_r < r:
        prev_r += 1
        freq[c[prev_r]] += 1
        if freq[c[prev_r]] == 1:
            cnt += 1
    while prev_r > r:
        freq[c[prev_r]] -= 1
        if freq[c[prev_r]] == 0:
            cnt -= 1
        prev_r -= 1

    # print(freq)
    ans.append((cnt, i))

ans.sort(key=lambda q: q[1])
ans = [v[0] for v in ans]
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int,input().split())
Cs = list(map(int,input().split()))
for i in range(Q):
  l, r = map(int,input().split())

  partialCs = Cs[l-1:r]
  print(len(set(partialCs)))

Submission status: Time Limit Exceeded

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


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

bit = [0 for _ in range(n+1)]
def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= (i & -i)
    return s
def add(i, x):
    while i <= n:
        bit[i] += x
        i += (i & -i)


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

    while len(que) > 0 and que[0][0] == i:
        r, l, x = heapq.heappop(que)
        ans[x] = sum(r)
        if l > 0:
            ans[x] -= sum(l-1)

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

Submission status: Time Limit Exceeded

Solution code:
n, q = (int(i) for i in input().split())
nums = [int(i) for i in input().split()]

#print(nums_info)
for _ in range(q):
    s, e = (int(i) for i in input().split())
    s -= 1
    ans = set()
    for i in range(s, e):
        ans.add(nums[i])
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

class SegmentTree():
    f = lambda self,x,y:x|y
    unit = 0
   
    def __init__(self,array):
        self.N = len(array)
        self.tree = [self.unit] * (2*self.N)
        self._build(array)
    
    def _build(self,array):
        for i,x in enumerate(array,self.N):
            self.tree[i] = x
        for i in range(self.N - 1,0,-1):
            self.tree[i] = self.f(self.tree[i << 1],self.tree[i << 1|1])
    
    def update(self,k,x):
        k += self.N
        self.tree[k] = x
        while k > 1:
            k >>= 1
            self.tree[k] = self.f(self.tree[k << 1],self.tree[k << 1|1])
    
    def query(self,l,r):
        l += self.N
        r += self.N
        vl = self.unit
        vr = self.unit
        while l < r:
            if l&1: 
                vl = self.f(vl,self.tree[l])
                l += 1
            if r&1:
                r -= 1
                vr = self.f(self.tree[r],vr)
            l >>= 1
            r >>= 1
        return self.f(vl,vr)
    
    def debug(self):
        print(self.tree)
    
    def __str__(self):
        return '\n'.join(' '.join(str(v) for v in self.tree[1<<i:1<<(i + 1)]) for i in range((2*self.N).bit_length()))

def main():
    N,Q = map(int,input().split())
    C = list(map(int,input().split()))
    for i in range(N):
        C[i] = 1<<C[i]

    st = SegmentTree(C)

    for i in range(Q):
        l,r = map(int,input().split())
        l -= 1
        ans = st.query(l,r)
        cnt = 0
        while ans > 0:
            cnt += ans&1
            ans >>= 1
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import pprint
from bisect import *
N,Q=map(int,input().split())
c=list(map(int,input().split()))
query=[list(map(int,input().split())) for _ in range(Q)]
l=[[] for _ in range(N)]
for i in range(N):
    l[c[i]-1].append(i+1)
#print(l)

for i in range(Q):
    left,right=query[i]
    cnt=0
    for j in range(N):
        if bisect_left(l[j],left)!=bisect_right(l[j],right):
            cnt=cnt+1
    print(cnt)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict
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=defaultdict(int)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
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

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


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

Submission status: Time Limit Exceeded

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

class SegTree:
    X_unit = set()

    def __init__(self, N):
        self.N = N
        self.X = [self.X_unit] * (N + N)

    def build(self, seq):
        for i, x in enumerate(seq, self.N):
            self.X[i] = {x}
        for i in range(self.N - 1, 0, -1):
            self.X[i] = self.X[i << 1] | self.X[i << 1 | 1]

    #区間積[L, R)
    def fold(self, L, R):
        L += self.N
        R += self.N
        vL = self.X_unit
        vR = self.X_unit
        while L < R:
            if L & 1:
                vL = vL | self.X[L]
                L += 1
            if R & 1:
                R -= 1
                vR = self.X[R] | vR
            L >>= 1
            R >>= 1
        return len(vL | vR)

seg = SegTree(N)
seg.build(C)

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

Submission status: Time Limit Exceeded

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

N, Q = LI()
C = LI()
LR = [LI() for _ in range(Q)]


class SegmentTree:

    def __init__(self, l):
        n = len(l)
        self.n = self.array_n(n)
        self.dat = [set() for _ in range(self.n * 2 - 1)]
        self.l = [None] * (self.n * 2 - 1)
        self.r = [None] * (self.n * 2 - 1)
        self.set_range(0, 0, self.n)
        self.set_dat(l)

    @staticmethod
    def array_n(n):
        ret = 1
        while ret < n:
            ret *= 2
        return ret

    def set_range(self, i, left, right):
        self.l[i] = left
        self.r[i] = right
        if i < self.n - 1:
            self.set_range(2 * i + 1, left, (left + right) // 2)
            self.set_range(2 * i + 2, ((left + right) // 2), right)

    def change(self, i, x):
        i += self.n - 1
        self.dat[i] |= {x}
        while i > 0:
            i = (i - 1) // 2
            self.dat[i] |= {x}

    def set_dat(self, l):
        n = len(l)
        for i in range(n):
            self.change(i, l[i])

    def cost_recur(self, i, l, r):
        left, right = self.l[i], self.r[i]
        if left == l and right == r:
            return self.dat[i]
        center = (left + right) // 2
        ret = set()
        if l < center:
            ret = self.cost_recur(i * 2 + 1, l, min(center, r))
        if center < r:
            ret |= self.cost_recur(i * 2 + 2, max(center, l), r)
        return ret

    def length(self, l, r):
        return len(self.cost_recur(0, l, r))



def main():
    ST = SegmentTree(C)
    for l, r in LR:
        ans = ST.length(l - 1, r)
        print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

p = [[] for _ in range(N)]
for i, c in enumerate(C):
    c = c-1
    p[c].append(i)

# print(p)

for l, r in LR:
    m = 0
    for p_i in p:
        m += (bisect_left(p_i, r) - bisect_left(p_i, l-1)) >= 1
    print(m)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, Q = mapint()
Cs = list(mapint())

#####segfunc######
def segfunc(x,y):
    return x|y

def init(init_val):
    for i in range(N):
        seg[i+num-1]=init_val[i]    
    for i in range(num-2,-1,-1) :
        seg[i]=segfunc(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] = segfunc(seg[k*2+1],seg[k*2+2])
    
def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

num =2**(N-1).bit_length()
ide_ele = set()
seg=[ide_ele]*2*num
init([set([c]) for c in Cs])
for _ in range(Q):
    l, r = mapint()
    print(len(query(l-1, r)))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, Q = LI()
c = LI()
lr = []
for i in range(Q):
    l, r = LI()
    l -= 1
    r -= 1
    lr.append((l, r))

keys = set(c)

dics = []
dic = {}
for key in keys:
    dic[key] = 0

for i in range(N):
    dic[c[i]] += 1
    dics.append(copy.deepcopy(dic))

for i in range(Q):
    l, r = lr[i]
    ans = 0
    if l > 0:
        left_dic = dics[l - 1]
        right_dic = dics[r]
        for key in keys:
            if right_dic[key] - left_dic[key] > 0:
                ans += 1
        print(ans)
    else:
        left_dic = dics[l - 1]
        right_dic = dics[r]
        for key in keys:
            if right_dic[key] > 0:
                ans += 1
        print(ans)

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 Segtree():
    def __init__(self, aa):
        self.inf = 0
        self.n = n = len(aa)
        self.tree_width = tree_width = 1 << (n - 1).bit_length()
        self.tree = [-self.inf] * (tree_width * 2 - 1)
        self.tree[tree_width-1:tree_width-1+n]=aa
        for u in range(tree_width - 2, -1, -1):
            self.tree[u] = self.tree[u * 2 + 1]+self.tree[u * 2 + 2]

    def add(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] += a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = self.tree[seg_i * 2 + 1]+self.tree[seg_i * 2 + 2]

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    # [l,r)の最大値
    def sum(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.sum(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.sum(l, r, seg_i * 2 + 2, segM, segR)
        return ret0+ret1

n,q=MI()
cc=LI()
lri=[]
mx=500005
#mx=10
for i in range(q):
    l,r=MI()
    l-=1
    lri.append((l,r,i))

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

#print(lri)
last=[-1]*mx
st=Segtree([0]*mx)
ans=[0]*q
now=0
for l,r,i in lri:
    for j in range(now,r):
        c=cc[j]
        pre=last[c]
        if pre!=-1:st.add(pre,-1)
        last[c]=j
        st.add(j,1)
    #print(l,r,st.tree,last)
    now=r
    ans[i]=st.sum(l,r)
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
lists = [list(map(int, input().split())) for i in range(Q+1)]
master = lists.pop(0)

X = [len(set(master[l[0]-1:l[1]])) for l in lists]

for x in X:
  print(x)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split(' '))
cs = input().split(' ')


for _ in range(q):
  l,r = input().split(' ')
  print(len(set(cs[int(l)-1:int(r)])))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
n,q = map(int,input().split())
ball_list = (input().split())
 
for i in range(q):
    begin,end = map(int,input().split())
    t_ball_list = ball_list[begin-1:end]
    print(len(set(t_ball_list)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

N, Q = map(int, input().split())
c = [int(i) for i in input().split()]
lr = [[int(i) for i in input().split()] for _ in range(Q)]

class SegTree:
  def __init__(self, n) :
    i = 1
    while i < n : 
      i <<= 1
    self.n = i
    self.tree = [set() for _ in range((i << 1))]

  def update(self, i, x) :
    i += self.n - 1
    self.tree[i].add(x)
    while i > 0 :
      i = (i - 1) // 2
      self.tree[i] = self.tree[i * 2 + 1] | self.tree[i * 2 + 2]

  # [l, r)
  def query(self, l, r) :
    l = l + self.n
    r = r + self.n
    s = set()
    while l < r :
      if r & 1 :
        r -= 1
        s |= self.tree[r - 1]
      if l & 1 :
        s |= self.tree[l - 1]
        l += 1
      l >>= 1
      r >>= 1
    return len(s)

ST = SegTree(N + 5)
for i in range(N) :
  ST.update(i, c[i])
 
for l, r in lr :
  print(ST.query(l - 1, r))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))


N, Q = LI()
c = LI()
lr = []
for i in range(Q):
    l, r = LI()
    l -= 1
    r -= 1
    lr.append((l, r))

keys = set(c)

dics = []
dic = {}
for key in keys:
    dic[key] = 0

for i in range(N):
    dic[c[i]] += 1
    dics.append(copy.deepcopy(dic))

for i in range(Q):
    l, r = lr[i]
    ans = 0
    if l > 0:
        left_dic = dics[l - 1]
        right_dic = dics[r]
        for key in keys:
            if right_dic[key] - left_dic[key] > 0:
                ans += 1
        print(ans)
    else:
        left_dic = dics[l - 1]
        right_dic = dics[r]
        for key in keys:
            if right_dic[key] > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from operator import add


class SegmentTree():
    """
    update, get を提供するSegmentTree

    Attributes
    ----------
    __n : int
        葉の数。2 ^ i - 1
    __dot :
        Segment function
    __e: int
        単位元
    __node: list
        Segment Tree
    """
    def __init__(self, A, dot, e):
        """
        Parameters
        ----------
        A : list
            対象の配列
        dot :
            Segment function
        e : int
            単位元
        """
        n = 2 ** (len(A) - 1).bit_length()
        self.__n = n
        self.__dot = dot
        self.__e = e
        self.__node = [e] * (2 * n)
        for i in range(len(A)):
            self.__node[i + n] = Counter({A[i]: 1})
        for i in range(n - 1, 0, -1):
            self.__node[i] = self.__dot(self.__node[2 * i], self.__node[2 * i + 1])
    
    def update(self, i, c):
        i += self.__n
        node = self.__node
        node[i] = c
        while i > 1:
            i //= 2
            node[i] = self.__dot(node[2 * i], node[2 * i + 1])

    def get(self, l, r):
        vl, vr = self.__e, self.__e
        l += self.__n
        r += self.__n
        while (l < r):
            if l & 1:
                vl = self.__dot(vl, self.__node[l])
                l += 1
            l //= 2
            if r & 1:
                r -= 1
                vr = self.__dot(vr, self.__node[r])
            r //= 2
        return self.__dot(vl, vr)


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

seg = SegmentTree(C, add, Counter())


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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys
input = sys.stdin.readline


class BIT1():
    """
    Binary Indexed Tree (1-indexed)
    """
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        # add x to idx-th element
        # idx: 1-indexed
        self.data[idx] += x
        while idx <= self.n:
            self.bit[idx] += x
            idx += (idx & (-idx))

    def sum(self, idx):
        # get sum of [1, idx]
        # idx: 1-indexed
        s = 0
        while idx:
            s += self.bit[idx]
            idx -= (idx & (-idx))
        return s


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((i, l, r))
queries.sort(key=itemgetter(2))

ans = [0] * q
# last_visit[i] = 色iの最後のindex
last_visit = [-1] * (n + 1)
query_counter = 0
bit = BIT1(n)
for i in range(n):
    if last_visit[c[i]] != -1:
        bit.add(last_visit[c[i]] + 1, -1)

    last_visit[c[i]] = i
    bit.add(i + 1, +1)

    while query_counter < q and queries[query_counter][2] == i:
        idx, l, r = queries[query_counter]
        ans[idx] = bit.sum(r + 1) - bit.sum(l)
        query_counter += 1

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    from bisect import bisect_left, bisect_right
    from collections import defaultdict
    import sys
    sys.setrecursionlimit = 10 ** 7
    input = sys.stdin.readline

    N, Q = map(int, input().split())
    *C, = (int(x) - 1 for x in input().split())  # 0-ind

    d = defaultdict(list)
    for i, c_ in enumerate(C):
        d[c_].append(i)

    ans = []
    for _ in range(Q):
        l, r = (int(x) - 1 for x in input().split())  # 0-ind
        t = 0
        for lst in d.values():
            t += (bisect_right(lst, r) - bisect_left(lst, l)) > 0
        ans.append(t)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import math 

def buildSparseTable(arr, n):
    j = 0
    v = 1 
    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 *= 2

pow_mem = []
def pm(k):
    j = 1
    for _ in range(k) :
        pow_mem.append(j)
        j *= 2

def query(L, R):
    to_union = list()
    while L <= R :
        j = int(math.log2(R - L + 1))
        if L > R :
            print('something wrong')
        to_union.append(lookup[L][j])
        L += pow_mem[j]
    x = set()
    for i in range(len(to_union))[::-1] :
        x = x.union(to_union[i])
    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)]
pm(v)
buildSparseTable(arr, N)

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