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 BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:

class BIT: # 1Indexed
    def __init__(self,size):
        self.array = [0]*size
        self.size  = size
    def add(self,ind,value):
        while ind <= self.size:
            self.array[ind-1] += value
            ind += ind & -ind
    def sum(self,x):
        out = 0
        while x > 0:
            out += self.array[x-1]
            x -= x & -x
        return out

################### ABC174F ###################

def main(N,Q,c,q):
    bit = BIT(N)
    rbi= {}
    ans = [0]*Q
    q.sort(key= lambda x:x[1])
    R = 0
    for l,r,ind in q:
        for i in range(R,r):
            if c[i] in rbi:
                bit.add(rbi[c[i]],-1)
            rbi[c[i]] = i+1
            bit.add(rbi[c[i]],1)
        ans[ind] = bit.sum(r)-bit.sum(l-1)
    return ans
                


if __name__ == "__main__":
    N,Q = map(int,input().split())
    c = list(map(int,input().split()))
    q = list( list(map(int,input().split()))+[i] for i in range(Q))
    ans = main(N,Q,c,q)
    for i in ans:
        print(i)

Submission status: Time Limit Exceeded

Solution code:
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

def bitsum(i):
    s = 0
    while i>0:
        s += bit[i]
        i -= i & -i
    return s

def bitadd(i,x):
    while i<=n:
        bit[i] += x
        i += i & -i

m = 500001
n,q = inm()
a = inl()
a[0:0] = [0]
if n==-10 and q==10:
    3/0
rli = []
for i in range(q):
    l,r = inm()
    rli.append((r,l,i))
rli.sort()
ans = [0]*q

bit = [0]*m
last = [-1 for i in range(m)]
for j in range(rli[0][0],0,-1):
    if last[a[j]]<0:
        last[a[j]] = j
        bitadd(j,1)
for i in range(q):
    if i>0:
        for j in range(rli[i-1][0]+1,rli[i][0]+1):
            if last[a[j]]>0:
                bitadd(last[a[j]],-1)
            last[a[j]] = j
            bitadd(j,1)
    ans[rli[i][2]] = bitsum(rli[i][0])-bitsum(rli[i][1]-1)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from sys import stdin

n,q=map(int,stdin.readline().split())
l=list(map(int,stdin.readline().split()))
res=[]
for i in range(q):
  a,b=map(int,stdin.readline().split())
  for i in range(a-1,b):
    res.append(l[i])
  print(len(Counter(res).keys()))
  res.clear()

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)]


def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############
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 = [self.e] * (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)
  
N,Q = IL()

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]

Qs = sorted(Qs,key = lambda x:x[2])

ans = [None for i in range(Q)]

GB = DD(lambda :-1)
ST = SegmentTree(N,lambda x,y:x+y,0)

nr = 0
for i,l,r in Qs:
  while nr < r:
    x = A[nr]
    if GB[x] == -1:
      GB[x] = nr
      ST.update(nr,1)
    else:
      ST.update(GB[x],-1)
      ST.update(nr,1)
      GB[x] = nr
    nr += 1
  ans[i] = ST.get(l,r)
      
print(*ans,sep="\n")

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"

def Mo(n,q,c,qi,base):
    ans = [0]*q
    ln = [-1]*(n+1)

    #BITの構成
    BIT = [0]*(n+1)
    def BIT_query(idx):
        res_sum = 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum
    def BIT_update(idx,x):
        while idx <= n:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    #Rが小さい方から見ていく,BITによる累積和の処理を含む
    pr = 0
    for ist in qi:
        i = ist%(base)
        l = (ist//(base))%(base)
        r = ist//(base)**2
        for j in range(pr,r):
            cj = c[j]
            ij = ln[cj]
            if ij != -1:
                BIT_update(ij,-1)
            ln[cj] = j+1
            BIT_update(j+1,1)
        pr = r
        ans[i] = BIT_query(r)-BIT_query(l-1)
    return ans

def main():
    n,q = map(int,ipt().split())
    c = [int(i) for i in ipt().split()]
    qi = []
    base = 10**6+1
    for i in range(q):
        l,r = map(int,ipt().split())
        qi.append(r*(base**2)+l*base+i)
    qi.sort()

    ans = Mo(n,q,c,qi,10**6+1)

    for i in ans:
        print(i)

    return None

if __name__ == '__main__':

    main()

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
res = [[-1]*n for i in range(n)]
for i in range(n):
    res[i][i] = 1
def dp(i, j):
    if res[i][j] != -1:
        return res[i][j]
    else:
        if nums[j] in nums[i:j]:
            tem = dp(i, j-1)
        else:
            tem = dp(i, j-1) + 1
    res[i][j] = tem
    return tem
for i in range(n):
    dp(i, n-1)
for i in range(k):
    i, j  = [int(i) for i in input().split()]
    print(res[i-1][j-1])

Submission status: Time Limit Exceeded

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

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

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

    query_list = [[] for _ in range(N // Bsize + 1)]
    for q in range(Q):
        l, r = map(int, input().split())
        query_list[(l-1) // Bsize].append((l - 1, r - 1, q))
    for i in range(N // Bsize + 1):
        if query_list[i]:
            query_list[i].sort(key=lambda x: x[1])
    query = []
    for ql in query_list:
        query.extend(ql)

    # [l, r)での求める値を管理するための変数たち
    # 問題によって変える
    cnt = [0] * (10**6 + 1)
    val = 0

    # 区間の伸縮操作
    # 問題によって変える
    def add(i):
        nonlocal val
        cnt[A[i]] += 1
        if cnt[A[i]] == 1:
            val += 1

    def rem(i):
        nonlocal val
        cnt[A[i]] -= 1
        if cnt[A[i]] == 0:
            val -= 1

    # init
    l, r, _ = query[0]
    for i in range(l, r + 1):
        add(i)

    # process
    ans = [0] * Q
    for l_new, r_new, q in query:
        if r < r_new:
            for i in range(r + 1, r_new + 1):
                add(i)
        elif r > r_new:
            for i in range(r, r_new, -1):
                rem(i)
        if l < l_new:
            for i in range(l, l_new):
                rem(i)
        elif l > l_new:
            for i in range(l - 1, l_new - 1, -1):
                add(i)
        l = l_new
        r = r_new
        ans[q] = val

    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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)]


def DD(arg): return defaultdict(arg)

#############
# Main Code #
#############
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 = [self.e] * (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)
  
N,Q = IL()

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]
Qs = sorted(Qs,key = lambda x:x[2])

ans = [None for i in range(Q)]

GB = DD(lambda :-1)
ST = SegmentTree(N,lambda x,y:x+y,0)

nr = 0
for i,l,r in Qs:
  while nr < r:
    x = A[nr]
    if GB[x] == -1:
      GB[x] = nr
      ST.update(nr,1)
    else:
      ST.update(GB[x],-1)
      ST.update(nr,1)
      GB[x] = nr
    nr += 1
  ans[i] = ST.get(l,r)
      
print(*ans,sep="\n")

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 #
#############
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 = [self.e] * (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)
  
N,Q = IL()
sqrtN = math.ceil(math.sqrt(N))

A = IL()
Qs = ILL(Q)
for i in range(Q):
  l,r = Qs[i][0],Qs[i][1]
  Qs[i] = [i,l-1,r]
Qs = sorted(Qs,key = lambda x:x[2])

ans = [None for i in range(Q)]

GB = DD(lambda :-1)
ST = SegmentTree(N,lambda x,y:x+y,0)

nr = 0
for i,l,r in Qs:
  while nr < r:
    x = A[nr]
    if GB[x] == -1:
      GB[x] = nr
      ST.update(nr,1)
    else:
      ST.update(GB[x],-1)
      ST.update(nr,1)
      GB[x] = nr
    nr += 1
  ans[i] = ST.get(l,r)
      
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
from operator import add, mul, sub, or_


class BIT:
    def __init__(self, n, op, ie):
        self.n = n
        self.tree = [ie]*(n+1)
        self.op = op

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] = self.op(self.tree[i], v)
            i += i & (-i)

    def query(self, i):
        v = 0
        while i:
            v = self.op(self.tree[i], v)
            i -= i & (-i)
        return v


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

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

bit = BIT(N, add, 0)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]]+1, -1)

    finds[c[i]] = i
    bit.update(finds[c[i]]+1, 1)

    for j, x in q[i]:
        ans[j] = bit.query(i+1) - bit.query(x)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for _ in range(q):
    Q.append(tuple(int(x)-1 for x in input().split()[::-1]))
  I = sorted(range(q), key=Q.__getitem__)
  #print(I, Q)
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i in I:
    r, l = Q[i]
    #print(i, r, l)
    to_update = {}
    for x in range(prev+1, r+1):
      to_update[C[x]] = x
    for c, x in to_update.items():
      if leftmost[c] >= 0:
        update(leftmost[c] + 1, -1, bit)
      leftmost[c] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
  for a in ans:
    print(a)
  

main()

Submission status: Time Limit Exceeded

Solution code:
# seg naive (※0から数えた時)
# input l,r output (i番目,2の何乗の要素か)の集合 rは含む
def segrange(l,r,Max=10**9):
    r+=1
    ans=[]
    tmp=1
    # 大きくしていくゾーン
    while True:
        while l%(tmp*2)==0 and tmp<N:
            tmp*=2
        if l+tmp<=r:
            ans.append((l//tmp,tmp.bit_length()-1))
            l+=tmp
        else:
            break
    # 小さくしていくゾーン
    tmp//=2
    while tmp>0:
        if l+tmp<=r:
            ans.append((l//tmp,tmp.bit_length()-1))
            l+=tmp
        tmp//=2
    return ans

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

segtree=[[set([c]) for c in C]]
for i in range(1,len(C).bit_length()):
    p2=2**i
    tmp=[set(C[j*p2:j*p2+p2]) for j in range(N//p2)]
    if N%p2!=0:
        tmp.append(set(C[p2*(N//p2):]))
    segtree.append(tmp)
for i in range(Q):
    l,r=map(int,input().split())
    ST=[segtree[j][i] for i,j in segrange(l-1,r-1,N)]
    ans=set()
    for st in ST:
        ans=set.union(ans,st)
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)

    def update(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & (-i)

    def query(self, i):
        v = 0
        while i:
            v += self.tree[i]
            i -= i & (-i)
        return v


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

q = [[] for _ in range(N+1)]
for i in range(Q):
    x, y = map(int, input().split())
    q[y-1].append([i, x-1])

bit = BIT(N)
finds = [-1]*(N+1)
ans = [0]*Q
for i in range(N):
    if finds[c[i]] != -1:
        bit.update(finds[c[i]]+1, -1)

    finds[c[i]] = i
    bit.update(finds[c[i]]+1, 1)

    for j, x in q[i]:
        ans[j] = bit.query(i+1) - bit.query(x)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline

def update(index, value, bit):
  #print('update', index, value)
  while index < len(bit):
    #print('update', index)
    bit[index] += value
    index += index & -index
  #print('done')
    
def cumsum(index, bit):
  ans = 0
  while index > 0:
    #print('cumsum', index)
    ans += bit[index]
    index -= index & -index
  #print('done', ans)
  return ans

def main():
  N, q = [int(x) for x in input().split()]
  C = [int(x)-1 for x in input().split()]
  Q = []
  for _ in range(q):
    Q.append(tuple(int(x)-1 for x in input().split()[::-1]))
  I = sorted(range(q), key=Q.__getitem__)
  #print(I, Q)
  leftmost = [-1] * N
  bit = [0] * (N+1)
  prev = -1
  ans = [0] * q
  for i in I:
    r, l = Q[i]
    #print(i, r, l)
    for x in range(prev+1, r+1):
      if leftmost[C[x]] >= 0:
        update(leftmost[C[x]] + 1, -1, bit)
      leftmost[C[x]] = x
      update(x + 1, 1, bit)
    prev = r
    #print(i, r, l)
    #print(C)
    #print([cumsum(i, bit) for i in range(1, N+1)])
    ans[i] = cumsum(r + 1, bit) - cumsum(l, bit)
  for a in ans:
    print(a)
  

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


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

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    # [1,i]の足し算
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    # [i,j]の足し算
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i-1)

for i in range(q):
    lr[i].append(i)
last=[-1]*(n+1)
bi=BIT(n)
lr.sort(lambda x: x[1])
# print(lr)
now=0
# last[c[now-1]]=now
# # bi.add(now,1)
# print(last)
# print(bi.el)

anslst=[-1]*q
for i in range(q):
    l,r,j=lr[i]
    while now!=r:
        now+=1
        if last[c[now-1]]!=-1:
            bi.add(last[c[now-1]],-1)
        last[c[now-1]]=now
        bi.add(last[c[now-1]],1)
    # print(last)
    # print(bi.el)
    # print(bi.get(l,r))
    anslst[j]=bi.get(l,r)

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

Submission status: Time Limit Exceeded

Solution code:
n, k = [int(i) for i in input().split()]
nums = [int(i) for i in input().split()]
res = [[-1]*n for i in range(n)]
for i in range(n):
    res[i][i] = 1
def dp(i, j):
    if res[i][j] != -1:
        return res[i][j]
    else:
        if nums[j] in nums[i:j]:
            tem = dp(i, j-1)
        else:
            tem = dp(i, j-1) + 1
    res[i][j] = tem
    return tem
for i in range(k):
    i, j  = [int(i) for i in input().split()]
    print(dp(i-1, j-1))

Submission status: Time Limit Exceeded

Solution code:
class Segment_Tree():
    def __init__(self,N,calc,unit,L=[]):
        """calcを演算とするN項のSegment Treeを作成

        N:要素数
        calc:演算(2変数関数,モノイド)
        unit:モノイドcalcの単位元 (xe=ex=xを満たすe)
        """
        self.calc=calc
        self.unit=unit

        X=[[unit]]
        k=1
        m=0

        N=max(N,len(L))
        while k<N:
            k*=2
            m+=1
            X.append([unit]*k)
        
        self.data=X
        self.num=k
        self.depth=m

        for k in range(len(L)):
            self.data[-1][k]=L[k]

        h=self.num
        for d in range(m-1,-1,-1):
            h//=2
            for i in range(h):
                self.data[d][i]=self.calc(self.data[d+1][2*i],self.data[d+1][2*i+1])
        
    def value(self,k):
        return self.data[-1][k]
    
    def update(self,k,x):
        """第k要素をxに変え,更新を行う.

        k:数列の要素
        x:更新後の値
        """
        
        self.data[-1][k]=x

        for d in range(self.depth-1,-1,-1):
            k=k//2
            self.data[d][k]=self.calc(self.data[d+1][2*k],self.data[d+1][2*k+1])

    def add(self,k,x):
        """第k要素にxを加え,更新する.

        k:数列の要素
        x:更新後の値
        """
        y=self.value(k)
        self.update(k,x+y)

    def sub_array(self,From,To):
        def g(k,m,l,r):
            if r<From or To<l:
                return self.unit
            elif From<=l and r<=To:
                return self.data[k][m]
            else:
                v=g(k+1,2*m,l,(l+r)//2)
                w=g(k+1,2*m+1,(l+r)//2+1,r)
                return self.calc(v,w)
        
        return g(0,0,0,self.num-1)
#-------------------------------------------------
N,Q=map(int,input().split())
C=list(map(lambda x:{x},input().split()))

T=Segment_Tree(N,lambda x,y:x|y,set(),C)

X=[0]*Q
for i in range(Q):
    L,R=map(int,input().split())
    X[i]=len(T.sub_array(L-1,R-1))
print("\n".join(map(str,X)))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)