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:
class SegmentTree:
    def __init__(self,siz,v = 0):
        self.n = 1
        self.v = v
        while self.n < siz: self.n *= 2
        self.node = [self.v]*(2*self.n-1)

    def merge(self,x,y): return x|y

    def update(self,i,x):
        i += self.n-1
        self.node[i] = {x}
        while i > 0:
            i = (i-1)//2
            self.node[i] = self.merge(self.node[i*2+1],self.node[i*2+2])
    
    def query(self,a,b):
        vl = vr = self.v
        a += self.n-1
        b += self.n-1
        while a < b:
            if a & 1 == 0: vl = self.merge(vl,self.node[a])
            if b & 1 == 0: vr = self.merge(vr,self.node[b-1])
            a //= 2
            b = (b-1)//2
        return self.merge(vl,vr)

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- 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, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(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([1 << c for c in C], or_, 0)

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

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:
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=[set([c]) for c in cc]
sp=SparseTable(aa)
for _ in range(q):
    l,r=MI()
    print(len(sp.val(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

def popcnt1(n):
	return bin(n).count("1")

class SegmentTree(object):
	#N:処理する区間の長さ
	def __init__(self, N):
		self.N = N
		self.N0 = 2 ** (N - 1).bit_length()
		self.initVal = 0
		self.data = [self.initVal] * (2 * self.N0)

	# 区間クエリの種類
	def calc(self, a, b):
		return a | b

	# セグメント木の中身をリストAで初期化
	def initialize(self, A):
		for i in range(self.N):
			self.data[self.N0 - 1 + i] = 1 << A[i]
		for i in range(self.N0 - 2, -1, -1):
			self.data[i] = self.calc(self.data[2 * i + 1], self.data[2 * i + 2])

	#区間[l, r]の演算値
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = self.initVal
		while L < R:
			if R & 1:
				R -= 1
				m = self.calc(m, self.data[R - 1])
			if L & 1:
				m = self.calc(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return popcnt1(m)


#処理内容
def main():
	N, Q = getlist()
	c = getlist()
	Seg = SegmentTree(N)
	Seg.initialize(c)
	for i in range(Q):
		l, r = getlist()
		l -= 1; r -= 1
		ans = Seg.query(l, r)
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
class Bit:
  def __init__(self,n):
    self.bl = n.bit_length()
    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

import sys
input = sys.stdin.readline
from collections import defaultdict
n,q = map(int,input().split())
a = list(map(int,input().split()))
lr = [tuple(map(int,input().split()))+(i,) for i in range(q)]
ans = [0]*q
lr.sort(key = lambda x:x[1])
bit = Bit(n+2)
dc = defaultdict(int)
cnt = 0
for L,R,p in lr:
  L -= 1
  for i in range(cnt,R):
    if dc[a[i]]:
      l = dc[a[i]]-1
      r = i
      bit.add(l+2,1)
      bit.add(r+2,-1)
    else:
      bit.add(1,1)
      bit.add(i+2,-1)
    dc[a[i]] = i+1
  ans[p] = bit.sum(L+1)
  cnt = R
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split(' '))
c_s= list(map(int, input().split()))
for i in range(q):
	ans=0
	l, r= list(map(int, input().split(' ')))
	test= set([])
	for i in c_s[l-1:r]:
		if i not in test:
			test.add(i)
			ans+=1
	print(ans)

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 Seg_sum():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 0
        self.func = lambda a,b : a+b

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

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 = Seg_sum([0]*(n+1))
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
for r,l,i in lr2:
    while(c_ind <= r):
        st.update(c_ind,1)
        bef = before[c[c_ind]]
        if(bef!=-1):
            st.update(bef,0)
        before[c[c_ind]] = c_ind
        c_ind += 1

    ans[i] = st.query(l,r+1)
    # print(r,l,i)
    # print(st.x)

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()))
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:
# -*- 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=list(map(int1,input().split()))
lr=[]
for i in range(Q):
    l,r=map(int1,input().split())
    lr.append((l,r,i))
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
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 lr and lr[-1][1]==i:
        l,r,j=lr.pop()
        ans[j]=b.sum(l,r+1)
for x in ans:
    print(x)

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
C = list(map(int,input().split()))
class BinaryIndexedTree:
    def __init__(self, n, default=0):
        "nの長さのBITをdefaultを初期値として構築する"
        self.s = [default]*(n+1)
        self.n = n
    # idxは0-indexted

    def add(self, idx, val):
        "idx(0-indexted)の値にvalを加える"
        idx += 1
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            if idx == 0:
                print("xx")
                exit()
            idx += idx & (-idx)
        return

    def get(self, idx):
        "idx(0-indexted)以下の要素の和を求める"
        idx += 1
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            if idx == 0:
                print("xx")
                exit()
            idx -= idx & (-idx)
        return res

BIT = BinaryIndexedTree(n)
RL = []
for i in range(q):
    l,r = map(int,input().split())
    r -= 1
    l -= 1
    RL.append((r,l,i))
RL.sort()
last = [-1]*n
now = -1
ans = [0]*q
for i in range(q):
    r,l,j = RL[i]
    while now < r:
        now += 1
        c = C[now]
        c -= 1
        if last[c] == -1:
            BIT.add(now, 1)
        else:
            BIT.add(last[c], -1)
            BIT.add(now, 1)
        last[c] = now
    ans[j] = BIT.get(r) - BIT.get(l-1)
print("\n".join(str(i) for i in ans))

Submission status: Time Limit Exceeded

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

def main():
    n, q = map(int, input().split())
    C = list(map(int, input().split()))
    C = [{c} for c in C]

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

    def init(init_val):
        # set_val
        for i in range(n):
            seg[i+num-1] = init_val[i]
        # built
        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[2*k+1], seg[2*k+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%2 == 0:
                res = segfunc(res, seg[p])
            if q%2 == 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

    # identity element
    ide_ele = set()

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

    init(C)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

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


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


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

# セグメント木
class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])

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

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r-1])
            l >>= 1
            r >>= 1
        return res


def main():
    N, Q = NMI()
    C = NLI()
    CS = [set([c]) for c in C]
    querys = [NLI() for _ in range(Q)]
    segtree = SegTree(CS, segfunc, ide_ele)

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from os import path

if(path.exists('input.txt')):
    sys.stdin = open("input.txt","r")
    sys.stdout = open("output.txt","w")

n,q = map(int,input().split())
c = list(map(int,input().split()))
for i in range(0,q):
    count = 0
    seen = {}
    l,r = map(int,input().split())
    #print(c)
    seen = c[l-1:r]
    s = {}
    for j in seen:
        s[j] = 1
    print(len(s.keys()))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
n, q = map(int, input().split())
# get a string
colors = list(map(int, input().split()))
# output
for i in range(q):
  l,r = map(int, input().split())
  print(len(set(colors[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
def proc(C, L, R, Order, N, Q):
    pl = pr = 0
    ans = 0
    A = np.zeros(N+1, dtype=np.int32)
    Ans = np.zeros(Q, dtype=np.int32)
    for idx_LR in Order:
        l = L[idx_LR]
        r = R[idx_LR]
        while pr < r:
            pr += 1
            c = C[pr]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pl > l:
            pl -= 1
            c = C[pl]
            if A[c] == 0:
                ans += 1
            A[c] += 1
        while pr > r:
            c = C[pr]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pr -= 1
        while pl < l:
            c = C[pl]
            A[c] -= 1
            if A[c] == 0:
                ans -= 1
            pl += 1
        Ans[idx_LR] = ans
    return Ans


if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    cc = CC('my_module')
    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)
    build = cc_export(proc, "i4[:](i4[:],i4[:],i4[:],i4[:],i4,i4)")
    cc.compile()

def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.array([0] + list(map(int, input().split())), dtype=np.int32)
    LR = np.array(list(map(int, sys.stdin.read().split())), dtype=np.int32)
    L = LR[::2]
    R = LR[1::2]
    B = L>>9<<20|R
    Order = np.argsort(B)
    Ans = proc(C, L, R, Order, N, Q)
    print("\n".join(map(str, Ans.tolist())))

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np
import numba
from numba import njit
from numba.types import Omitted
i4 = numba.int32
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

Bsize = 700

@njit((i8[:, :], ), cache=True)
def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int64)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int64)
    nl, nr = 0, 0
    for i in ind:
        l, r = LR[i]
        l -= 1
        # 区間 [l, r) に対する計算
        while nl > l:
            nl -= 1
            add(A[nl])
        while nr < r:
            add(A[nr])
            nr += 1
        while nl < l:
            rem(A[nl])
            nl += 1
        while nr > r:
            nr -= 1
            rem(A[nr])
        #  答を求めて ans[i] に格納する
        answers[i] = ans
    return answers

if sys.argv[-1] == 'ONLINE_JUDGE':
    import numba
    from numba.pycc import CC
    i4 = numba.int32
    i8 = numba.int64
    cc = CC('my_module')

    def cc_export(f, signature):
        cc.export(f.__name__, signature)(f)
        return numba.njit(f)

    main = cc_export(main, (i8[:], i8[:, :]))
    cc.compile()

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))

Submission status: Time Limit Exceeded

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

n,q = map(int,input().split())
C = list(map(int,input().split()))
class BinaryIndexedTree:
    def __init__(self, n, default=0):
        "nの長さのBITをdefaultを初期値として構築する"
        self.s = [default]*(n+1)
        self.n = n
    # idxは0-indexted

    def add(self, idx, val):
        "idx(0-indexted)の値にvalを加える"
        idx += 1
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx & (-idx)
        return

    def get(self, idx):
        "idx(0-indexted)以下の要素の和を求める"
        idx += 1
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx & (-idx)
        return res

BIT = BinaryIndexedTree(n)
RL = []
for i in range(q):
    l,r = map(int,input().split())
    r -= 1
    l -= 1
    RL.append((r,l,i))
RL.sort()
last = [-1]*n
now = -1
ans = [0]*q
for i in range(q):
    r,l,j = RL[i]
    while now < r:
        now += 1
        c = C[now]
        c -= 1
        if last[c] == -1:
            BIT.add(now, 1)
        else:
            BIT.add(last[c], -1)
            BIT.add(now, 1)
        last[c] = now
    ans[j] = BIT.get(r) - BIT.get(l-1)
print("\n".join(str(i) for i in ans))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():return sys.stdin.readline()[:-1]
def N(): return int(input())
def NM():return map(int,input().split())
def L():return list(NM())
n,q=NM()
c=L()
No=2
while No<=n:
    No*=2
tree=[set() for i in range(2*No)]

for i in range(No-1,No-1+n):
    tree[i].add(c[i-No+1])
for i in range(No-2,-1,-1):
    tree[i]=tree[i*2+1]|tree[i*2+2]

def query(l,r):
    L=l+No-1
    R=r+No-1
    s=set()
    while L<=R:
        if R&1:
            s|=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s|=tree[L]
        L>>=1;R>>=1
    return s
for i in range(q):
    l,r=NM()
    l-=1
    r-=1
    print(len(query(l,r)))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
alp = "abcdefghijklmnopqrstuvwxyz"

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 = map(int,ipt().split())
#    n = 5*10**5
#    q = 5*10**5
#    c = [int(i+1) for i in range(n)]
    c = [2**(int(i)-1) for i in ipt().split()]

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

    def popcnt(n):
        return bin(n).count("1")

    ST = SegTree(c,segfunc,0)

    for i in range(q):
#        l = 2; r = 5*10**5-1
        l,r = map(int,ipt().split())
        print(popcnt(ST.query(l-1,r)))

    return None

if __name__ == '__main__':
    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())
    temp=[0]
    ans=0
    for i in range(l-1,r):
        if arr[i] in temp:
            continue
        else:
            ans+=1
            temp.append(arr[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
C = list(map(int,input().split()))
class BinaryIndexedTree:
    def __init__(self, n, default=0):
        "nの長さのBITをdefaultを初期値として構築する"
        self.s = [default]*(n+1)
        self.n = n
    # idxは0-indexted

    def add(self, idx, val):
        "idx(0-indexted)の値にvalを加える"
        idx += 1
        while idx < self.n+1:
            self.s[idx] = self.s[idx] + val
            idx += idx & (-idx)
        return

    def get(self, idx):
        "idx(0-indexted)以下の要素の和を求める"
        idx += 1
        res = 0
        while idx > 0:
            res = res + self.s[idx]
            idx -= idx & (-idx)
        return res

BIT = BinaryIndexedTree(n)
RL = []
for i in range(q):
    l,r = map(int,input().split())
    r -= 1
    l -= 1
    RL.append((r,l,i))
RL.sort()
last = [-1]*n
now = -1
ans = [0]*q
for i in range(q):
    r,l,j = RL[i]
    while now < r:
        now += 1
        c = C[now]
        c -= 1
        if last[c] == -1:
            BIT.add(now, 1)
        else:
            BIT.add(last[c], -1)
            BIT.add(now, 1)
        last[c] = now
    ans[j] = BIT.get(r) - BIT.get(l-1)
print("\n".join(str(i) for i in ans))

Submission status: Time Limit Exceeded

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


class BIT:
    """一点加算、区間取得クエリをそれぞれO(logN)で答えるデータ構造"""
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n + 1)

    def build(self, array):
        """arrayを初期値とするBinaryIndexTreeを構築する O(N)"""
        for i in range(self.size):
            self.bit[i + 1] = array[i]
        for i in range(1, self.size):
            if i + (i & -i) > self.size:
                continue
            self.bit[i + (i & -i)] += self.bit[i]

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

    def add(self, i, val):
        """i番目の要素にvalを加える"""
        i += 1
        while i <= self.size:
            self.bit[i] += val
            i += i & -i

    def get_sum(self, l, r):
        """区間[l, r)の和を求める"""
        return self._sum(r) - self._sum(l)


n, q = map(int, input().split())
c = list(map(int, input().split()))
query = [list(map(int, input().split())) + [i] for i in range(q)]


bit = BIT(n)
memo = {}

ans = [0] * q
query = sorted(query, key=itemgetter(1))
ind = 0
for l, r, i in query:
    while ind < r:
        if c[ind] in memo:
            old_ind = memo[c[ind]]
        else:
            old_ind = -1
        memo[c[ind]] = ind
        bit.add(ind, 1)
        if old_ind != -1:
            bit.add(old_ind, -1)
        ind += 1
    ans[i] = bit.get_sum(l - 1, r)

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

Submission status: Time Limit Exceeded

Solution code:
def main():
  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
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[-1]*n
  bitt=BinaryIndexedTree(n)
  j=0
  for i in range(n):
    if lastAppeared[a[i]]!=-1:
      bitt.add(lastAppeared[a[i]],-1)
      bitt.add(i,1)
      lastAppeared[a[i]]=i
    else:
      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()