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 segfunc(x,y):
    return x|y

class SegTree:
    
    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 query(self, l, r):
        
        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
        

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

seg = SegTree(c, segfunc, set())

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

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])


class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val = init_val
        # Range Minimum Query
        self.N0 = 2**(N - 1).bit_length()  # Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res = left | right
        return res

    def update(self, k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0 - 1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(
                self.data[2 * k + 1], self.data[2 * k + 2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R - 1])

            if L & 1:
                s = self._segfunc(s, self.data[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s


def inttobit(i):
    return 1 << (i - 1)


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


n, q = inpl()
s = [inttobit(i) for i in inpl()]
st = SegmentTree(0, n)
ans = []
for i in range(n):
    st.update(i, s[i])
for i in range(q):
    l, r = inpl()
    tmp = st.query(l - 1, r)
    ans.append(popcnt(tmp))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,Q = map(int, input().split()) 
A = np.array([int(x) for x in input().split()])
for i in range(Q):
  a,b = map(int, input().split()) 
  print(len(np.unique(A[(a-1):b])))

Submission status: Time Limit Exceeded

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

N,Q=(int(x) for x in input().rstrip('\n').split())
cs = [int(x) for x in input().rstrip('\n').split()]
for _ in range(Q):
  l,r = (int(x) for x in input().rstrip('\n').split())
  print(len(set(cs[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, a, func=int.__add__, one=0):
        self.n = len(a)
        self.func = func
        self.one = one
        self.a = [0] * (self.n + 1)

        for i, j in enumerate(a):
            self.update(i, j)

    def update(self, i, x):
        i += 1
        while i <= self.n:
            self.a[i] = self.func(self.a[i], x)
            i += i & (-i)

    def get(self, i):
        i += 1
        s = self.one
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s


n, q = map(int, input().split())
c = [int(i)-1 for i in input().split()]
que = [[i, [int(i)-1 for i in input().split()], 0] for i in range(q)]
que.sort(key=lambda x: x[1][1])
last = [-1] * n
bit = BIT([0]*(n+100))
j = 0
for i in range(n):
    if last[c[i]] != -1:
        bit.update(last[c[i]], -1)
    bit.update(i, 1)
    last[c[i]] = i
    while j < q and que[j][1][1] == i:
        que[j][2] = bit.get(i) - bit.get(que[j][1][0]-1)
        j += 1
que.sort()
for i in que:
    print(i[-1])

Submission status: Time Limit Exceeded

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

lr = []
for i in range(q):
    l, r = map(int, input().split())
    if cSetLen <= len(set(c[l - 1 : r // 16])):
        print(cSetLen)
    elif cSetLen <= len(set(c[l - 1 : r // 8])):
        print(cSetLen)
    elif cSetLen <= len(set(c[l - 1 : r // 4])):
        print(cSetLen)
    elif cSetLen <= len(set(c[l - 1 : r // 2])):
        print(cSetLen)
    else:
        print(len(set(c[l - 1 : r])))

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:
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([1]*(n+1))
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
for r,l,i in lr2:
    while(c_ind <= r):
        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('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self,n):
        self.size = n
        self.tree = [0]*(n+1)
 
    def add(self,index,x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self,index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self,value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i+step <= self.size and s + self.tree[i+step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N,Q = LI()
c = LI()
l,r = LIR(Q,2)

x = []
for i in range(Q):
    x.append((i,l[i],r[i]))
x.sort(key=lambda x: (x[2],x[1]))

bit = BIT(N)

ans = [0]*Q
last = [-1]*(N+1)
right = -1 # 確認し終わった右端
for i in range(Q):
    for j in range(right+1,x[i][2]):
        bit.add(j+1,1)
        if last[c[j]] != -1:
            bit.add(last[c[j]]+1,-1)
        last[c[j]] = j
    right = x[i][2]-1
    ans[x[i][0]] = bit.sum(x[i][2]) -  bit.sum(x[i][1]-1)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

for i in range(q):
    color_map = [0]*(n+1)
    l,r = map(int,input().split())
    count = 0
    for i in range(l-1,r):
        if color_map[c[i]] == 0:
            count += 1
            color_map[c[i]] = 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
num=[]
for i in range(q):
    l,r=map(int,input().split())
    num.append([l,r,i])
num.sort(key=lambda x: x[1])
la=[-1]*max(c)
bit=[0]*n
ans=[0]*q
num1=0
for i in range(q):
    for j in range(num1,num[i][1]):
        num2=c[j]
        if la[num2-1]==-1:
            la[num2-1]=j
            bit[j]=1
        else:
            bit[la[num2-1]]=0
            la[num2-1]=j
            bit[j]=1
    ans[num[i][2]]=sum(bit[num[i][0]-1:num[i][1]])
    num1=num[i][1]-1
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
I = lambda : list(map(int,input().split()))
from collections import Counter as cc

n,q=I()

l=I()
qq=[]
for i in range(q):
	qq.append([I(),i])
qq.sort()
an=[0]*q
le,r=qq[0][0]
p=cc(l[le-1:r])
le-=1;r-=1
an[qq[0][1]]=len(p)
for i in range(1,q):
	x,y=qq[i][0]
	x-=1;y-=1
	while le<x:
		p[l[le]]-=1
		le+=1
	while r!=y:
		if y<r:
			p[l[r]]-=1
			r-=1
		else:
			r+=1
			p[l[r]]+=1
	an[qq[i][1]]=len([i for i in p if p[i]])
for i in an:
	print(i)

Submission status: Time Limit Exceeded

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

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:

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

#####ide_ele　単位元#####
ide_ele = set()
#################



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



n,q=map(int,input().split())
C=[{int(i)} for i in input().split()]
T=SegTree(C, segfunc, ide_ele)
for i in range(q):
    l,r=map(int,input().split())
    g=T.query(l-1,r)
    print(len(g))

Submission status: Time Limit Exceeded

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


class SegmentTree:
    def __init__(self, target, no_effect=0):
        target_size = len(target)
        leaves_size = 1
        while leaves_size < target_size:
            leaves_size *= 2
        self.tree_size = leaves_size * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.no_effect = no_effect
        self.initialize_tree(target, no_effect)

    @classmethod
    def initialize_func(cls, value):
        return 1 << value

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree(self, target: list, no_effect=0):
        initial_leaf = self.tree_size // 2
        leaves = range(initial_leaf, initial_leaf+len(target))
        for value, leaf in zip(target, leaves):
            self.tree[leaf] = self.initialize_func(value)

        for parent in range(initial_leaf-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_value, index):
        leaf = self.tree_size//2 + index
        new_data = self.initialize_func(new_value)
        if self.tree[leaf] == new_data:
            return
        self.tree[leaf] = new_data

        parent = (leaf-1) // 2
        while parent >= 0:
            new_data = self.merge_child_data(parent)
            if self.tree[parent] == new_data:
                break
            self.tree[parent] = new_data
            parent = (parent-1) // 2

    def resolve_query(self, from_, to):
        result = self.no_effect
        left, right = from_ + self.tree_size // 2, to + self.tree_size // 2
        while left <= right:
            result = self.merge_func(result, self.tree[left])
            result = self.merge_func(result, self.tree[right])
            left //= 2
            right = right//2 - 1

        return bin(result).count('1')


def main():
    n, q = map(int, input().split())
    C = list(map(int, input().split()))

    seg_tree = SegmentTree(C)
    for _ in range(q):
        l, r = map(int, input().split())
        res = seg_tree.resolve_query(l-1, r-1)
        print(res)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

N,Q = map(int,input().split())
list_c = [int(a) for a in input().split()]

List=[list(map(int,input().split())) for x in range(Q)]

for i in range(Q):
    l = List[i][0]
    r = List[i][1]
    list_c_new = list_c[l-1:r]
    set_list = set(list_c_new)
    print(len(set_list))

Submission status: Time Limit Exceeded

Solution code:
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
if __name__ == "__main__":
    n,q= map(int,input().split())
    a = list(map(int,input().split()))

    # queries = [Query(0,2,0),
    #            Query(1,3,1),Query(2,2,2)]

    queries = []
    for i in range(q):
        l,r = map(int,input().split())
        l-=1
        r-=1
        queries.append(Query(l,r,i))

    q = len(queries)

    queries.sort(key = lambda x: x.r)
    answeringQueries(a, n, queries, q)

# This code is contributed by
# sanjeev2552

Submission status: Time Limit Exceeded

Solution code:
import collections

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]
    LR = [[int(x) for x in input().split()] for _ in range(Q)]

    def segfunc(x, y):
        # 求めたい値を算出するためのロジックを書く
        return x | y

    def init(init_val):
        for i in range(n):
            seg[i + num - 1].add(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 set()
        p += num - 1
        q += num - 2
        res = set()
        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

    # seg tree初期値 (単位元)
    n = N
    # ide_ele = 0
    num = 2 ** (n - 1).bit_length()
    # seg = [ide_ele] * 2 * num
    seg = [set() for j in range(2 * num)]

    init(C)
    for l, r in LR:
        print(len(query(l - 1, r)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from scipy.sparse import lil_matrix
import numpy as np

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

X = lil_matrix((N+1,N), dtype=np.int32)
for i in range(len(C)):
  c = C[i]-1
  X[i+1] += X[i]
  X[i+1,c] += 1

for _ in range(Q):
  l,r = map(int, input().split())
  print(np.sum(X[r]>X[l-1]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n, q = map(int, input().split())
c = np.array(input().split(), dtype = np.int64)
cnt = 0
wk = np.array([0 for i in range(n)], dtype = np.int64)

for i in range(q):
    L, R = map(int, input().split())
    cnt = 0
    wk = np.array([0 for i in range(n)], dtype = np.int64)
    for j in range(R - L + 1):
        if c[L + j -1] not in wk:
            wk[cnt] = c[L + j -1]
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    #for pypy
    #treeは1-based-index,queryは0-based-index
    __slots__=["size","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            self.tree[self.size+i]=initial_value_list[i]
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.tree[2*i]|self.tree[2*i+1]

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.tree[2*k]|self.tree[2*k+1]
    def query(self, l, r):
        #res->func[l,r)
        l+=self.size-self.first_idx
        r+=self.size-self.first_idx
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=lret|self.tree[l]
                l+=1
            if r&1:
                r-=1
                rret=self.tree[r]|rret # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return lret|rret

n,q=map(int,input().split())
l=[set([p])for p in input().split()]
seg=SegmentTree(l,set(),1)
for i in range(q):
    le,ri=map(int,input().split())
    print(len(seg.query(le,ri+1)))

Submission status: Time Limit Exceeded

Solution code:
_, q = map(int, input().split())
ball = list(input().split())

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

Submission status: Time Limit Exceeded

Solution code:
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 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
        if l==r:
            res = self.tree[l]
        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 len(res)
    
N,Q=map(int,input().split())
b = list(map(int,input().split()))
a = [set() for i in range(N)]
for i in range(N):
    a[i].add(b[i])
def segfunc_union(x, y):
    return x | y
ide_ele_set = set()
seg1 = SegTree(a, segfunc_union, ide_ele_set)
for i in range(Q):
    b,c=map(int,input().split())
    print(seg1.query(b-1,c))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(int, input().split()))
q = [list(map(int, input().split())) for i in range(q)]

dic = dict()
for i in range(n):
    if c[i] not in dic:
        dic[c[i]] = set()
    dic[c[i]].add(i)

for query in q:
    l, r = query[0]-1, query[1]
    ans = set()
    i = l
    while i < r:
        for key, vlaue in dic.items():
            if i in vlaue:
                ans.add(key)
                break
        i += 1
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys


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

    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

    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_


def solve(n, q, ccc, queries):
    just_left = {}
    segments = []
    for i in range(n):
        c = ccc[i]
        if c in just_left:
            segments.append((i, 0, just_left[c], 0))
        just_left[c] = i

    for i, (l, r) in enumerate(queries):
        segments.append((r - 1, 1, l - 1, i))

    segments.sort()

    lng = len(segments)

    bit = BinaryIndexedTree(n + 2)
    ans = [0] * q
    for r, tp, l, i in segments:
        if tp == 0:
            bit.add(l + 2, 1)
        else:
            base = r - l + 1
            ans[i] = base - (bit.sum(r + 2) - bit.sum(l + 1))
    return ans


n, q = map(int, sys.stdin.buffer.readline().split())
ccc = list(map(int, sys.stdin.buffer.readline().split()))
mp = map(int, sys.stdin.buffer.read().split())
queries = list(zip(mp, mp))
ans = solve(n, q, ccc, queries)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    cnt = 0
    while cnt < Q:
        l, r = list(map(int, input().split()))
        print(len(set(c[(l-1):r])))
        cnt += 1

if __name__ == '__main__':
    main()

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[:],u4[:],u4[:],i8[:],i4,i4)")
    cc.compile()

from my_module import proc
def main():
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    C = np.empty(N+1, dtype=np.int32)
    C[0] = 0
    C[1:] = np.array(input().split(), dtype=np.int32)
    LR = np.array(sys.stdin.buffer.read().split(), dtype=np.uint32)
    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
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

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)
hq = []
for i,l,r in zip(range(q),it,it):
    heappush(hq, (r-1,l-1,i))

st = BIT(n+1)
ans = [0] * q
before = [-1] * (n+1)
c_ind = 0
while(hq):
    r,l,i = heappop(hq)
    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:
from operator import or_
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class SparseTable:
    def __init__(self, N, arr, op):
        self.N = N
        self.depth = N.bit_length()
        self.op = op
        self.arr = tuple(arr)
        self._build()

    def __call__(self, s, t):
        """
        [s, t)区間（0-indexed）での値を返す
        """
        i = (t - s).bit_length() - 1
        L = self.table[i][s]
        R = self.table[i][t - (1 << i)]
        return self.op(L, R)

    def _build(self):
        self.table = []
        self.table.append(self.arr)
        N = self.N
        for i in range(self.depth - 1):
            shift = 1 << i
            N -= shift
            t = tuple(self.op(self.table[-1][j], self.table[-1][j+shift])
                      for j in range(N))
            self.table.append(t)


N, Q = map(int, input().split())
C = [1 << (i-1) for i in map(int, input().split())] + [0]
sp = SparseTable(N+1, C, or_)
for _ in range(Q):
    s, t = map(int, input().split())
    b = bin(sp(s-1, t)).count("1")
    print(b)