Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
3
1

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

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

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

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3



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


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys

    def MI():
        return map(int, sys.stdin.readline().rstrip().split())

    def LI():
        return list(map(int, sys.stdin.readline().rstrip().split()))  # 空白あり

    N, Q = MI()
    c = [{i} for i in LI()]

    unit = set()

    class SegTree:  # モノイドに対して適用可能、Nが2冪でなくても良い
        def __init__(self, N, unit):
            self.N = N
            self.unit = unit
            self.tree = [self.unit] * (2 * self.N)

        def build(self, init_value):  # 初期値を[N,2N)に格納
            for i in range(self.N):
                self.tree[i + self.N] = init_value[i]
            for i in range(self.N - 1, 0, -1):
                self.tree[i] = self.tree[i << 1] | self.tree[i << 1 | 1]

        def fold(self, L, R):  # [L,R)の区間取得
            L += self.N
            R += self.N
            vL = self.unit
            vR = self.unit
            while L < R:
                if L & 1:
                    vL = vL | self.tree[L]
                    L += 1
                if R & 1:
                    R -= 1
                    vR = self.tree[R] | vR
                L >>= 1
                R >>= 1
            return len(vL | vR)

    seg = SegTree(N, unit)
    seg.build(c)

    for i in range(Q):
        l, r = MI()
        print(seg.fold(l - 1, r))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,Q = map(int, input().split())
c = input().split()
c = [int(i) for i in c]
l = list()
r = list()
for i in range(Q):
    L,R = map(int,input().split())
    l.append(L)
    r.append(R)
color = list()
for i in range(N):
    if not (c[i] in color):
        color.append(c[i])
for i in range(Q):
    cc = list()
    for ii in c[l[i]-1:r[i]]:
        
        if not (ii in cc):
            cc.append(ii)
        if len(cc) == len(color):
            break
    print(len(cc))

Submission status: Time Limit Exceeded

Solution code:
def exp():
    n,q=map(int,input().split(" "))
    c=tuple(map(int,input().split(" ")))
    for i in range(q):
        start,finish=map(int,input().split(" "))
        arr=[]
        ans=0
        for i in range(start-1,finish):
            if c[i] not in arr:
                arr.append(c[i])
                ans+=1
        print(ans)
exp()

Submission status: Time Limit Exceeded

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,Q = IL()
A = IL()

class SegmentTree:
  def __init__(self, n, op, e):
    self.n = n
    self.op = op
    self.e = e
    self.size = 2 ** ((n - 1).bit_length())
    self.node = [set() for i in range(2 * self.size)]
 
  def build(self, array):
    for i in range(self.n):
      self.node[self.size + i] = array[i]
    for i in range(self.size - 1, 0, -1):
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def update(self, i, val):
    i += self.size
    self.node[i] |= val
    while i > 1:
      i >>= 1
      self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])
 
  def get(self, l, r):
    l, r = l + self.size, r + self.size
    res_l, res_r = self.e, self.e
    while l < r:
      if l & 1:
        res_l = self.op(res_l, self.node[l])
        l += 1
      if r & 1:
        r -= 1
        res_r = self.op(self.node[r], res_r) 
      l, r = l >> 1, r >> 1
    return self.op(res_l, res_r)
  
ST = SegmentTree(N,lambda x,y:x|y,set())
for i in range(N):
  x = A[i]
  ST.update(i,{x})

for _ in range(Q):
  L,R = IL()
  print(len(ST.get(L-1,R)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,q=map(int, input().split())
c=np.array(list(map(int,input().split())))
for _ in range(q):
    l,r  = map(int, input().split())
    print(np.unique(c[l-1:r]).size)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            a = i + self.end_leaves
            while a >= 0:
                a = (a - 1) // 2
                self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        for i in range(25):
            if y - x > 1:
                if x % 2 == 1:
                    tl = tl | self.tree[x]
                    x += 1
                if y % 2 == 0:
                    tr = self.tree[y] | tr
                    y -= 1
                x >>= 1
                y >>= 1
            elif y - x == 0:
                return len(tl|tr|self.tree[x])
            else:
                return len(tl|tr|self.tree[x]|self.tree[y])
            
N,Q,*f = map(int, open(0).read().split())
c = f[:N]
lr = [f[N+i*2:N+i*2+2] for i in range(Q)]
if N == 1:
    for i in range(Q):
        print(1)
else:
    st = SegmentTree(c)
    for l,r in lr:
        print(st.query(l-1,r-1))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    n, q = map(int, input().split())
    s = list(map(int, input().split()))
    cnt = []
    rcnt = []
    for i in range(1, n + 1):
        x = len(set(s[:i]))
        cnt.append(x)
    for i in range(n - 1, -1, -1):
        x = len(set(s[i:]))
        rcnt.append(x)
    rcnt = rcnt[::-1]
    for _ in range(q):
        l, r = map(int, input().split())
        if r == l:
            print(1)
            continue
        l, r = l - 1, r - 1
        y = cnt[l - 1] if l >= 1 else 0
        z = rcnt[r] if r < n - 1 else 0
        print(min(r - l + 1, max(cnt[r] - y, rcnt[l - 1] - z)))

solve()

Submission status: Time Limit Exceeded

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

for i in range(q):
  a, b = map(int, input().split())
  print(len(set(strList[a-1:b])))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


INF = float("inf")
MOD = 10**9 + 7

class SegmentTree(object):
    # セグメント木

    def __init__(self, N):
        """サイズNの配列を元にしたセグメント木
        """
        # 単位元
        self.idelem = set()
        # 比較関数
        self.func = lambda x, y: (x | y)

        self.N0 = 1
        while self.N0 < N:
            self.N0 <<= 1
        self.tree = [self.idelem]*(2*self.N0)

    def update(self, k, x):
        """k番目の値をxに更新
        """
        k += self.N0-1
        self.tree[k] = x
        while k > 1:
            k = (k-1)//2
            self.tree[k] = self.func(self.tree[2*k+1], self.tree[2*k+2])

    def query(self, l, r):
        """区間[l, r)の最小値
        """
        l += self.N0-1
        r += self.N0-1
        s = self.idelem
        while l < r:
            if r % 2 == 0:
                r -= 1
                s = self.func(s, self.tree[r])

            if l % 2 == 0:
                s = self.func(s, self.tree[l])
                l += 1
            l //= 2
            r //= 2
        return s


def main():
    N, Q = MAP()
    c = LIST()
    lr = ZIP(Q)

    segs = SegmentTree(N)
    for i in range(N):
        segs.update(i, set([c[i]]))

    for l, r in lr:
        a = segs.query(l-1, r)
        print(len(a))

    return


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

N, Q = map(int, input().split())
C = list(map(int, input().split()))
X = [list(map(int, input().split())) for _ in range(Q)]

ctr = []
tmp = [0] * (max(C) + 1)
ctr.append(tmp[:])
for i in range(N):
    tmp[C[i]] += 1
    ctr.append(tmp[:])

for l, r in X:
    print(sum(u - v > 0 for u, v in zip(ctr[r], ctr[l - 1])))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n):
    res = [None] * n
    for i in range(n):
        res[i] = II()
    return res
def LIR(n):
    res = [None] * n
    for i in range(n):
        res[i] = LI_()
    return res
def FR(n):
    res = [None] * n
    for i in range(n):
        res[i] = IF()
    return res
mod = 1000000007
inf = float('INF')
#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    for i in range(q):
        l, r = lr[i]
        lr[i] = [l,r,i]
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = defaultdict(lambda:-1)
    bit = [0] * (n + 1)
    def add(i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= n:
            bit[x - 1] += w
            x += x & -x
        return
    def sum(i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += bit[x - 1]
            x -= x & -x
        return res
    t = 0
    for i in range(n):
        ci = c[i]
        l = dp[ci]
        add(i, 1)
        dp[ci] = i
        if l != -1:
            add(l, -1)
        while t < q and lr[t][1] <= i:
            l, r, j = lr[t]
            tmp = sum(r) - sum(l - 1)
            ans[j] = tmp
            t += 1
    for ai in ans:
        print(ai) 
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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


class BIT:
    def __init__(self, a):
        self.n = len(a)
        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.a[i] + x
            i += i & (-i)

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


def inmin(x):
    return int(x)-1


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split())), 0] for i in range(q)]
    que.sort(key=lambda x: x[1][1])

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    que.sort()
    for i in que:
        print(i[-1])

Submission status: Time Limit Exceeded

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

def main():       
    def build(list):
        for i,x in enumerate(list,n):
            d = set()
            d.add(x)
            seg[i] = d
            
        for i in range(n-1,0,-1):
            seg[i] = seg[i<<1]|seg[i<<1 | 1]

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

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

    n,q = map(int,input().split())
    c = list(map(int,input().split()))
    seg = [set()]*(2*n)
    build(c)

    for i in range(q):
        l,r = map(int,input().split())
        print(get(l-1,r))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
import math
#from itertools import product, accumulate, combinations, product
#import bisect
#import numpy as np
#from copy import deepcopy
#from collections import deque

INF = 1 << 50

class segtree:
    def __init__(self, n, init_val=None, init=0):
        self.n = n
        self.init_val = init_val
        self.init = init
        self.k = math.ceil(math.log2(n))

        try:
            init_val[0]
        except:
            raise ValueError('init_val should be list')

        self.bins = [self.init] * (1 << (self.k + 1))
        for idx, i in enumerate(range(1 << self.k, 1 << (self.k + 1))):
            if len(self.init_val) > idx:
                self.bins[i] = init_val[idx]
            else:
                pass

        self.caliculate()

    def compare(self, l, r):
        ret = l.copy()
        for v in r:
            ret.add(v)
        return ret

    def caliculate(self):
        k = self.k
        while k:
            for i in range(1<<k, 1<<(k+1)):
                if not i%2:
                    self.bins[i//2] = self.compare(self.bins[i], self.bins[i+1])
                else:continue
            k -= 1

    def update(self, idx, val):
        '''idx : 0-started index'''
        k = (1<<self.k) + idx
        self.bins[k] = val
        while k>1:
            self.bins[k // 2] = self.compare(self.bins[k // 2 * 2], self.bins[k // 2 * 2 + 1])
            k = k//2


    def eval(self, l, r):
        ret = self.init
        l = (1 << self.k) + l
        r = (1 << self.k) + r
        #print(l, r)
        while True:
            #print(l, r)
            if r - l == 1:
                ret = self.compare(ret, self.bins[l])
                ret = self.compare(ret, self.bins[r])
                break
            elif l == r:
                ret = self.compare(ret, self.bins[l])
                break
            else:
                done = False
                if l % 2:
                    ret = self.compare(ret, self.bins[l])
                    l += 1
                    done = True
                if not r % 2:
                    ret = self.compare(ret, self.bins[r])
                    r -= 1
                    done = True
                if not done:
                    l = l // 2
                    r = r // 2
        #print(ret)
        return ret

    def value(self, ind):
        return self.bins[(1<<self.k) + ind]

def run():
    N, Q = map(int, sysread().split())
    C = list(map(int, sysread().split()))
    C = [set([c]) for c in C]
    SEG = segtree(n = N, init_val = C, init =set())
    for i in range(Q):
        l,r = map(int, sysread().split())
        l-=1
        r-=1
        ans = SEG.eval(l,r)
        print(len(ans))





if __name__ == "__main__":
    run()

Submission status: Time Limit Exceeded

Solution code:
[N, Q] = [int(i) for i in input().split()]
colorst = [int(i) for i in input().split()]
ans = []
for j in range(Q):
    [l, r] = [int(i) for i in input().split()]
    li = colorst[l-1: r]
    se = set(li)

    ans.append(len(se))

for i in ans:
    print(i)

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(set(c[pair[0]:pair[1]+1])))
    print(*a, sep="\n")

calc()

Submission status: Time Limit Exceeded

Solution code:
import math 

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

    return len(set.union(*to_union)) 

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)]
buildSparseTable(arr, N)

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

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
for _ 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
input = sys.stdin.readline


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):
        s = self.one
        i += 1
        while i != 0:
            s = self.func(s, self.a[i])
            i -= i & (-i)
        return s

def inmin(x):
    return int(x)-1

if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(inmin, input().split()))
    que = [[i, list(map(inmin, input().split())), 0] for i in range(q)]
    que.sort(key=lambda x: x[1][1])

    last = [-1] * n
    bit = BIT([0]*(n+10))
    j = 0
    for i in range(n):
        if last[c[i]] >= 0:
            bit.update(last[c[i]]+5, -1)
        bit.update(i+5, 1)
        last[c[i]] = i
        while j < q and que[j][1][1] == i:
            que[j][2] = bit.get(i+5) - bit.get(que[j][1][0]+4)
            j += 1
    que.sort()
    for i in que:
        print(i[-1])