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:
# from sys import stdin
# input = stdin.readline


class Bit:
    def __init__(self, n):
        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


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

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

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

Submission status: Time Limit Exceeded

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


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

lr = []
for i in range(Q):
    l, r = map(int, input().split())
    lr.append([l, r, i])

lr.sort(key=lambda x: x[1])
# print("lr", lr)
rightest = [-1] * (N + 1)
current_q = 0
bit = Bit(N)
ans = [0] * Q

for i in range(N):
    if rightest[c[i]] != -1:
        bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    bit.add(i + 1, 1)
    # print(bit.tree)

    while current_q < Q and lr[current_q][1] == i + 1:
        ans[lr[current_q][2]] = bit.sum(lr[current_q][1]) - bit.sum(lr[current_q][0] - 1)
        current_q += 1

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def query(bit, start, stop):
    return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)


readline = stdin.readline

N, Q = map(int, readline().split())
c = list(map(int, readline().split()))

lr = [None] * Q
for i in range(Q):
    l, r = map(int, readline().split())
    lr[i] = (r - 1, l - 1, i)
lr.sort()

result = [None] * Q

bit = [0] * N
mr = {}
k = 0
for i in range(N):
    if c[i] in mr:
        bit_add(bit, mr[c[i]], -1)
    bit_add(bit, i, 1)
    mr[c[i]] = i
    while k < Q and lr[k][0] == i:
        result[lr[k][2]] = query(bit, lr[k][1], lr[k][0] + 1)
        k += 1

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

Submission status: Time Limit Exceeded

Solution code:
from operator import add
from sys import stdin


class SegmentTree:
    _op = None
    _e = None
    _size = None
    _offset = None
    _data = None

    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        op = self._op
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def add(self, index, value):
        self.update(index, self._data[self._offset + index] + value)

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result


readline = stdin.readline

N, Q = map(int, readline().split())
c = list(map(int, readline().split()))

lr = [None] * Q
for i in range(Q):
    l, r = map(int, readline().split())
    lr[i] = (r - 1, l - 1, i)
lr.sort()

result = [None] * Q

st = SegmentTree(N, add, 0)
mr = {}
k = 0
for i in range(N):
    if c[i] in mr:
        st.add(mr[c[i]], -1)
    st.add(i, 1)
    mr[c[i]] = i
    while k < Q and lr[k][0] == i:
        result[lr[k][2]] = st.query(lr[k][1], lr[k][0] + 1)
        k += 1

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

Submission status: Time Limit Exceeded

Solution code:
# Date [ 2020-09-06 11:56:02 ]
# Problem [ f.py ]
# Author Koki_tkg

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

class BinaryIndexedTree:
    def __init__(self, n):
        '''1-index'''
        self.size = n + 1
        self.data = [0] * self.size
        self.element = [0] * self.size
        self.depth = 1 << n.bit_length() - 1
    
    def build(self, array):
        for i, x in enumerate(array):
            self.add(i, x)

    def add(self, i, v):
        self.element[i] += v; i += 1 # 1-index
        while i < self.size:
            self.data[i] += v
            i += i & -i
    
    def _sum(self, i):
        ret = 0
        while i > 0:
            ret += self.data[i]
            i -= i & -i
        return ret
    
    def get_sum(self, l, r=None):
        '''get sum [l, r)'''
        if r == None: return self.element[l]
        return self._sum(r) - self._sum(l-1)

    def lower_bound(self, v):
        if v <= 0: return 0
        k = self.depth; i = 0
        while k > 0:
            if i+k < self.size and self.data[i+k] < v:
                v -= self.data[i+k]
                i += k
            k >>= 1
        return i+1

def Main():
    n, q = read_ints()
    c = read_int_list()
    query = [(read_ints()) for _ in range(q)]
    
    que = defaultdict(list)
    for i, (l, r) in enumerate(query):
        que[r].append([l, i])

    ans = [0] * q    
    last = [-1] * (n + 1)
    bit = BinaryIndexedTree(n)
    
    for i, x in enumerate(c):
        if last[x] > 0:
            bit.add(last[x]-1, -1)
        last[x] = i + 1
        bit.add(last[x]-1, 1)
        
        if len(que[i + 1]) > 0:
            for l, j in que[i + 1]:
                ans[j] = bit.get_sum(l, i+1)
    
    print(*ans, sep='\n')

if __name__ == '__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)
    
  X.extend(res) 
  X = sorted(X)

  # 平面走査
  bit = BIT(N)
  ans=[0]*Q
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans[idx] = r-l+1-bit.query(l-1,r)
      
  print(*ans)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())
  q = [tuple(map(int,input().split())) for _ in range(Q)]

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((tmp_dict[C[i]]<<40) | (Q<<20) | i)
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  #assert time() - start < 0.1

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = q[i]
    # (元のクエリの順番、l, r)
    X.append(((l-1)<<40) | (i<<20) | r-1)

  #assert time() - start < 0.1
    
  X.extend(res) 
  X = sorted(X)
  
  #assert time() - start < 0.1

  # 平面走査
  bit = BIT(N)
  ans=[]
  mask = (1<<20) - 1
  for l in reversed(X):
    r = l & mask
    l >>= 20
    idx = l & mask
    l >>= 20
    if idx == Q:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  #assert time() - start < 0.2

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  #assert time() - start < 0.8
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  assert time() - start < 0.5

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
from time import time
start = time()

# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i
    
  assert time() - start < 0.5

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  assert time() - start < 1.0
    
  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))
  
  assert time() - start < 1.5

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の解法

class BIT:
    '''
    https://atcoder.jp/contests/abc174/submissions/15616960
    0-indexed
    '''
    def __init__(self, N):
        self.size = N
        self.tree = [0] * (N + 1)
        self.depth = N.bit_length()
 
    def _bitsum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i ^= i & -i
        return ret
 
    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)
 
    def bitadd(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
 
    def lower_bound(self, x):
        sum_ = 0
        pos = 0
        v = 1 << self.depth
        for i in range(self.depth, -1, -1):
            k = pos + v
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += v
            v >>= 1
        return pos + 1, sum_
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))

  # 平面走査
  bit = BIT(500005)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.bitadd(r,1)
    else:
      ans.append((idx,r-l+1-bit.bitsum(l,r+1)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
def main():
  N,Q=map(int,input().split())
  *C,=map(int,input().split())

  # 重複度を数える。
  res=[]
  tmp_dict={}
  for i in range(N):
    if tmp_dict.get(C[i]) != None:
      #(クエリの種類、l, r）
      res.append((-1,tmp_dict[C[i]],i))
      del tmp_dict[C[i]]
    tmp_dict[C[i]] = i

  # クエリと合わせてソート。
  X = []
  for i in range(Q):
    l,r = map(int,input().split())
    # (元のクエリの順番、l, r)
    X.append((i,l-1,r-1))

  X.extend(res) 
  X = sorted(X,key=lambda x:(x[1],-x[0]))

  # 平面走査
  bit = BIT(N)
  ans=[]
  for idx,l,r in reversed(X):
    if idx == -1:
      bit.add(r,1)
    else:
      ans.append((idx,r-l+1-bit.query(l-1,r)))

  # 元の順番にソートし直して出力
  print(*list(zip(*sorted(ans)))[1])
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
N,Q=map(int,input().split())
*C,=map(int,input().split())

# 重複度を数える。
res=[]
tmp_dict={}
for i in range(N):
  if tmp_dict.get(C[i]) != None:
    #(クエリの種類、l, r）
    res.append((-1,tmp_dict[C[i]],i))
    del tmp_dict[C[i]]
  tmp_dict[C[i]] = i
  
# クエリと合わせてソート。
X = []
for i in range(Q):
  l,r = map(int,input().split())
  # (元のクエリの順番、l, r)
  X.append((i,l-1,r-1))

X.extend(res) 
X = sorted(X,key=lambda x:(x[1],-x[0]))

# 平面走査
bit = BIT(N)
ans=[]
for idx,l,r in reversed(X):
  if idx == -1:
    bit.add(r,1)
  else:
    ans.append((idx,r-l+1-bit.query(l-1,r)))

# 元の順番にソートし直して出力
print(*list(zip(*sorted(ans)))[1])

Submission status: Time Limit Exceeded

Solution code:
# 解説放送の解法

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
      
N,Q=map(int,input().split())
*C,=map(int,input().split())

# 重複度を数える。
res=[]
tmp_dict={}
for i in range(N):
  if tmp_dict.get(C[i]) != None:
    #(クエリの種類、l, r, 意味なし）
    res.append((0,tmp_dict[C[i]],i,0))
    del tmp_dict[C[i]]
  tmp_dict[C[i]] = i
  
# クエリと合わせてソート。
X = []
for i in range(Q):
  l,r = map(int,input().split())
  # (クエリの種類、l, r, 元のクエリの順番)
  X.append((1,l-1,r-1,i))

X.extend(res) 
X = sorted(X,key=lambda x:(x[1],-x[0]),reverse=True)

# 平面走査
bit = BIT(N)
ans=[]
for q,l,r,idx in X:
  if q == 0:
    bit.add(r,1)
  else:
    ans.append((idx,r-l+1-bit.query(l-1,r)))

# 元の順番にソートし直して出力
print(*list(zip(*sorted(ans)))[1])

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N,Q=map(int,input().split())
*C,=map(set,input().split())
seg = SegTree(N,set.union,set())
seg.build(C)
for i in range(Q):
  l,r = map(int,input().split())
  print(len(seg.fold(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
    """ segment tree with point modification and range product. """
    # # https://yukicoder.me/submissions/452850
    def __init__(self, N, data_f = min, data_unit=1<<30):
        self.N = N
        self.data_f = data_f
        self.data_unit = data_unit
        self.data = [self.data_unit] * (N + N)

    def build(self, raw_data):
        data = self.data
        f = self.data_f
        N = self.N
        data[N:] = raw_data[:]
        for i in range(N - 1, 0, -1):
            data[i] = f(data[i << 1], data[i << 1 | 1])

    def set_val(self, i, x):
        data = self.data
        f = self.data_f
        i += self.N
        data[i] = x
        while i > 1:
            data[i >> 1] = f(data[i], data[i ^ 1])
            i >>= 1

    def fold(self, L, R):
        """ compute for [L, R) """
        vL = vR = self.data_unit
        data = self.data
        f = self.data_f
        L += self.N
        R += self.N
        while L < R:
            if L & 1:
                vL = f(vL, data[L])
                L += 1
            if R & 1:
                R -= 1
                vR = f(data[R], vR)
            L >>= 1
            R >>= 1
        return f(vL, vR)
      
N,Q=map(int,input().split())
*C,=map(int,input().split())
seg = SegTree(N,set.union,set())
seg.build([set([C[i]]) for i in range(N)])
for i in range(Q):
  l,r = map(int,input().split())
  print(len(seg.fold(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
c=list(map(int,input().split()))
q=[]
last=[0 for _ in range(N+1)]
bit=[0 for _ in range(N+1)]
ans=[0 for _ in range(Q)]
for i in range(Q):
    l,r=map(int,input().split())
    q.append((l,r,i))
q.sort(key=lambda x:x[1],reverse=True)
right=0
for i in range(Q):
    l,r,j=q.pop()
    for i in range(right,r):
        C=c[i]
        if last[C]==0:
            last[C]=i+1
            bit[i+1]=1
        else:
            now=last[C]
            last[C]=i+1
            bit[now]=0
            bit[i+1]=1
    point=sum(bit[l:r+1])
    ans[j]=point
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
c = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(q)]
from collections import Counter
for i,j in lr:
    print(len(Counter(c[i-1:j]).most_common()))

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    while i <= self.n:
      self.data[i] += x
      i += i & -i

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = [None]*Q
for i in range(Q):
  l,r = map(int, input().split())
  Qs[i] = [i,l,r]
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  b = r + 1
  ans[i] = bt.sum(r) - bt.sum(l-1)
    
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
  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
    while i <= self.n:
      self.data[i] += x
      i += i & -i

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  if b < r + 1:
    st = set()
    for j in range(b,r+1):
      if not Cs[j] in st and Cs[j] in dic:
        bt.add(dic[Cs[j]],-1)
      st.add(Cs[j])
      dic[Cs[j]] = j
    for s in st:
      bt.add(dic[s], 1)
    b = r + 1
  ans[i] = bt.sum(r) - bt.sum(l-1)
    
for a in ans:
  print(a)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
  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
    while i <= self.n:
      self.data[i] += x
      i += i & -i

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  ans[i] = bt.sum(r) - bt.sum(l-1)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  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
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  st = set()
  for j in range(b,r+1):
    if not Cs[j] in st and Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    st.add(Cs[j])
    dic[Cs[j]] = j
  for s in st:
    bt.add(dic[s], 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  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
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  for j in range(b,r+1):
    if Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    dic[Cs[j]] = j
    bt.add(j, 1)
  ans[i] = bt.get(l-1,r)
  b = r + 1
  
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0]*(n+1)
    self.el = [0]*(n+1)
  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
  def get(self, i, j=None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)

N, Q = map(int, input().split())
Cs = [0] + list(map(int, input().split()))

Qs = []
for i in range(Q):
  l,r = map(int, input().split())
  Qs.append((i,l,r))
  
Qs.sort(key=lambda x:x[2])

ans = [-1]*Q
dic = {}
b = 1
bt = BIT(N)

for i,l,r in Qs:
  for j in range(b,r+1):
    if Cs[j] in dic:
      bt.add(dic[Cs[j]],-1)
    dic[Cs[j]] = j
    bt.add(j, 1)
  ans[i] = bt.get(l-1,r)
  
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
 
class Bit:
    def __init__(self, n):
        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
 
n,q = list(map(int,input().split()))
ball = list(map(int,input().split()))
 
h = Bit(n+1)

L = {}
jump = {}
on = set()

for i,b in enumerate(ball):
  if b not in L:
    h.add(i+1,1)
    on.add(i+1)
  if b in L:
    jump[L[b]]=i+1
  L[b] = i+1

Q = []
 
for _ in range(q):
  l,r = list(map(int,input().split()))
  Q.append((l,r))
  
LOO = list(Q)
Q.sort(key=lambda x:x[0])

c = 1
ans = {}

for l,r in Q:
  for i in range(c,l):
    if i in on:
      on.remove(i)
      h.add(i,-1)
      if i in jump:
        dest = jump[i]
        h.add(dest,1)
        on.add(dest)

  tmp = h.sum(r)- h.sum(l-1)
  ans[(l,r)] = tmp
  c = l

p = []
for q in LOO:
  p.append(ans[q])
  
print(*p, sep="\n")