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:
# -*- coding: utf-8 -*-
from operator import add


import sys
# sys.setrecursionlimit(10**6)
# buff_readline = sys.stdin.buffer.readline
buff_readline = sys.stdin.readline
readline = sys.stdin.readline

INF = 2**62-1


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))


def read_float():
    return float(buff_readline())


def read_float_n():
    return list(map(float, buff_readline().split()))


def read_str():
    return readline().strip()


def read_str_n():
    return readline().strip().split()


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

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

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

    def query(self, l, r):
        """[l, r)
        """
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret

    def __getitem__(self, key):
        return self.__tree[key + self.__size]


@mt
def slv(N, Q, C, LR):
    RLI = [(r, l, i) for i, (l, r) in enumerate(LR)]
    RLI.sort()

    st = SegmentTree([0]*N, add, 0)
    la = {}
    ans = [-1] * Q
    p = 0
    for r, l, i in RLI:
        l -= 1
        r -= 1
        for j in range(p, r+1):
            c = C[j]
            if c in la:
                st.update(la[c], st[la[c]]-1)
            la[c] = j
            st.update(j, st[j]+1)
        p = r+1
        ans[i] = st.query(l, r+1)
    return ans

def main():
    N, Q = read_int_n()
    C = read_int_n()
    LR = [read_int_n() for _ in range(Q)]
    print(*slv(N, Q, C, LR), sep='\n')

    # N = 5 * 10**5
    # Q = N
    # C = [i for i in range(1, N+1)]
    # LR = []
    # from random import randint
    # for _ in range(Q):
    #     l = randint(1, N-1)
    #     r = randint(l, N-1)
    #     LR.append([l, r])
    # print(*slv(N, Q, C, LR), sep='\n')



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  
  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)

  bt=BIT(n+1)
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      bt.add(dc[x],-1)
    bt.add(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=bt.get(l-1,r)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l, i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    def sum(self, i):
        if i == 0:
            return 0
        s = 0
        while i > 0:
            s += self._container[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    from collections import deque
    from operator import itemgetter
    n, q = map(int, readline().split())
    c = list(map(int, readline().split()))
    res = [0] * n
    query = [[None] for _ in range(q)]

    for i in range(q):
        l, r = map(int, readline().split())
        query[i] = (l, r, i)

    bt = BinaryIndexTree(n)
    query.sort()

    idx = {i: deque() for i in range(1, n + 1)}

    for i, x in enumerate(c, 1):
        idx[x].append(i)

    for num in range(1, n + 1):
        if idx[num]:
            bt.add(idx[num][0], 1)

    l_cur = 1
    for i in range(q):
        l, r, j = query[i]
        while l_cur < l:
            num = c[l_cur - 1]
            if len(idx[num]) > 1:
                bt.add(idx[num].popleft(), -1)
                bt.add(idx[num][0], 1)
            else:
                bt.add(idx[num].popleft(), -1)
            l_cur += 1
        res[j] = bt.sum(r)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.buffer.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l - 1, r - 1, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        lr[i] = (l - 1, r - 1, i)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 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
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    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:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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

Submission status: Time Limit Exceeded

Solution code:
import sys
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r):
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)

from operator import add
def resolve():
    n, q = map(int, input().split())
    C = list(map(lambda x : int(x) - 1, input().split()))

    A = [0] * n
    used = [0] * n
    for i, c in enumerate(C):
        if used[c]:
            continue
        used[c] = 1
        A[i] = 1
    tree = SegmentTree(A, add, 0)

    next = [-1] * n
    used = [-1] * n
    for i in range(n - 1, -1, -1):
        c = C[i]
        if used[c] != -1:
            next[i] = used[c]
        used[c] = i

    queries = [None] * q
    for i in range(q):
        l, r = map(int, input().split())
        queries[i] = (l - 1, r, i)
    queries.sort(reverse = 1)

    ans = [0] * q
    for l in range(n):
        while queries and queries[-1][0] == l:
            l, r, i = queries.pop()
            ans[i] = tree.sum(l, r)
        if next[l] != -1:
            tree.add(next[l], 1)

    print(*ans, sep = '\n')
resolve()

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  def segfunc(x, y):
    return x+y
  #################

  #####ide_ele#####
  ide_ele=0
  #################

  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=segfunc, ide_ele=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
  st=SegTree([0]*(n+1))
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      st.update(dc[x],0)
    st.update(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=st.query(l,r+1)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
import numpy
sys.setrecursionlimit(int(1e6))
#dprint = print
def dprint(*args):
    pass

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

while(Q > 0):
    l, r = list(map(int, input().split()))
    h = {}
    for i in range(l-1, r):
        key = c[i]
        h[key] = 1
    dprint('l, r=', l, r)
    dprint('h=', h)
    print(len(h))
    Q = Q - 1

Submission status: Time Limit Exceeded

Solution code:

import sys
input = sys.stdin.readline
def main():
  n,q=map(int,input().split())
  c=list(map(int,input().split()))
  lr=[list(map(int,input().split())) for _ in range(q)]
  lri=[[lr[i][0],lr[i][1],i] for i in range(q)]
  lri.sort(key=lambda x:x[1])
  def segfunc(x, y):
    return x+y
  #################

  #####ide_ele#####
  ide_ele=0
  #################

  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=segfunc, ide_ele=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
  st=SegTree([0]*(n+1))
  dc={}
  ans=[0]*q
  j=0
  for i in range(n):
    x=c[i]
    if x in dc:
      st.update(dc[x],0)
    st.update(i+1,1)
    dc[x]=i+1
    while j<q and i+1==lri[j][1]:
      l,r,k=lri[j]
      ans[k]=st.query(l,r+1)
      j+=1
    if j==q:break
  print(*ans,sep='\n')


if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.buffer.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
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
#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:
#!/usr/bin/env python3
from collections import defaultdict
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.buffer.readline
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def LIR(n):
    res = [None] * n
    for i in range(n):
        l, r = map(int, input().split())
        res[i] = (l - 1, r - 1, i)
    return res

#solve
def solve():
    n, q = LI()
    c = LI()
    lr = LIR(q)
    ans = [None] * q
    lr.sort(key=lambda x: x[1])
    dp = [-1] * (max(c) + 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
    def f(t):
        l, r, j = lr[t]
        xr = sum(r)
        xl = sum(l-1)
        tmp = xr - xl
        ans[j] = tmp
        
    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:
            f(t)
            t += 1
        if t == q:
            break
    for ai in ans:
        print(ai) 
    return


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

Submission status: Time Limit Exceeded

Solution code:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LR = [ tuple( map( int, input().split())) for _ in range(Q)]
    LRI = []
    for i, x in enumerate(LR):
        LRI.append((x[1], x[0], i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    # 一点更新・一点取得の加法BIT

    class BIT():
        def __init__(self, n):
            self.n = n
            self.maxbit = 2**(len(bin(n))-3)
            self.bit = [0]*(n+1)
            self.allsum = 0

        # 初期化する
        def make_bit(self, a):
            n, bit = self.n, self.bit
            for i, j in enumerate(a):
                x = i+1
                self.allsum += j
                while x < n+1:
                    bit[x] += j
                    x += x & (-x)

        # 位置iに値vを足す
        def add(self, i, v):
            x, n, bit = i+1, self.n, self.bit
            self.allsum += v
            while x < n+1:
                bit[x] += v
                x += x & (-x)

        # 位置0からiまでの和(sum(bit[:i]))を計算する
        def sum(self, i):
            ret, x, bit = 0, i, self.bit
            while x > 0:
                ret += bit[x]
                x -= x & (-x)
            return ret

        # 位置iからjまでの和(sum(bit[i:j]))を計算する
        def sum_range(self, i, j):
            return self.sum(j) - self.sum(i)

        # 和がw以上となる最小のインデックスを求める
        def lowerbound(self, w):
            if w <= 0:
                return 0
            x, k, n, bit = 0, self.maxbit, self.n, self.bit
            while k:
                if x+k <= n and bit[x+k] < w:
                    w -= bit[x+k]
                    x += k
                k //= 2
            return x

    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    lastappend = [-1]*n
    ilr = []
    for i in range(q):
        l, r = map(int, input().split())
        ilr.append((i, l-1, r-1))
    ilr.sort(key=lambda x: (x[2], x[1], x[0]))
    bit = BIT(n)
    ans = [-1]*q
    r_now = -1
    for i, l, r in ilr:
        if r > r_now:
            for j in range(r_now+1, r+1):
                last = lastappend[c[j]-1]
                if last != -1:
                    bit.add(last, -1)
                lastappend[c[j]-1] = j
                bit.add(j, 1)
            r_now = r
        ans[i] = bit.sum_range(l, r+1)
    for i in ans:
        print(i)


main()

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 = [set()] * (2 * self.num)
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = set([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
        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())
dat = list(map(int, input().split()))
st = SegTree(dat, segfunc, ide_ele)
for i in range(q):
    l, r = map(int, input().split())
    x = st.query(l-1, r+1-1)
    print(len(x))

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


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

    def sum(self, i):
        if i == 0:
            return 0
        s = 0
        while i > 0:
            s += self._container[i]
            i -= i & (-i)
        return s

    def add(self, i, x):
        if i == 0:
            return
        while i <= self.size:
            self._container[i] += x
            i += i & (-i)

    def lower_bound(self, x):
        if x == 0:
            return 0

        s = 0
        idx = 0
        for i in range(self.depth, -1, -1):
            k = idx + (1 << i)
            if k <= self.size and s + self._container[k] < x:
                s += self._container[k]
                idx += 1 << i
        return idx + 1

    def __repr__(self):
        return str(self._container)


def main():
    from collections import defaultdict, deque
    from operator import itemgetter
    n, q = map(int, readline().split())
    c = list(map(int, readline().split()))
    res = [0] * n
    query = []

    for i in range(q):
        l, r = map(int, readline().split())
        query.append([l, r, i])

    bt = BinaryIndexTree(n)
    query.sort()

    idx = defaultdict(deque)

    for i, x in enumerate(c, 1):
        idx[x].append(i)

    for num in range(1, n + 1):
        if idx[num]:
            bt.add(idx[num][0], 1)

    l_cur = 1
    for i in range(q):
        l, r, j = query[i]
        if l == l_cur:
            res[j] = bt.sum(r)
        else:
            while l_cur < l:
                num = c[l_cur - 1]
                if len(idx[num]) > 1:
                    bt.add(idx[num].popleft(), -1)
                    bt.add(idx[num][0], 1)
                else:
                    bt.add(idx[num].popleft(), -1)
                l_cur += 1
            res[j] = bt.sum(r)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
lr = [tuple(map(int, input().split())) for _ in range(Q)]

slr = sorted(lr, key=lambda x:x[1])
last = [-1] * N
bit = [0] * N
pastr = 0
dic = dict()
for l, r in slr:
    l, r = l-1, r-1
    for i in range(pastr, r+1):
        bit[last[C[i]-1]] = 0
        last[C[i]-1] = i
        bit[i] = 1
    dic[(l+1,r+1)] = sum(bit[l:r+1])
    pastr = r

for q in lr:
    print(dic[q])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
import numpy as np

n, q = map(int, input().split())
C = [int(c) for c in input().split()]
i = 0
rows = []
for c in C:
    rows.append(c)

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

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """

    def __init__(self, N, init_val=0):
        self.init_val = init_val
        self.size = N
        self.L = [init_val]*(N+1)

    def sum(self, r):
        """
        sum[,r)
        calc sum from L[0] to L[r-1]
        """
        ret = self.init_val
        while r > 0:
            ret += self.L[r]
            r -= r & (-r)

        return ret

    def range_sum(self, l, r):
        
        """
        idx周りが怪しい?
        sum[l,r)
        calc sum from L[l] to L[r-1]
        """
        return self.sum(r-1)-self.sum(l-1)

    def add(self, i, x):
        """
        L[i] += x
        """
        while i <= self.size:
            self.L[i] += x
            i += i & (-i)

    def bisect(self,k:float)->int:
        """ binary search on BIT
        get index x s.t self.sum(,)>=k

        RETURN:
            res:index of x
        """
        k+=1 #convert k into 1-index

        res=0
        N=1
        while N<self.size:
            N*=2

        i=N//2
        while i>0:
            if(res+i<self.size and self.L[res+i]<k): #move to rignt on tree
                k-=self.L[res+i]
                res+=i
            #else move to left
            i//=2
        return res+1



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


pos=sorted(pos,key=lambda x:x[1])

last_appeared=[0]*(N+1)

B = BIT(N,0)

ans=[-1]*Q

cur_r=1
for l,r,i in pos:
    while cur_r<=r:
        last = last_appeared[C[cur_r-1]]
        if last==0:#first add
            B.add(cur_r,1)
        else:
            B.add(last,-1)
            B.add(cur_r,1)

        last_appeared[C[cur_r-1]]=cur_r #lastの更新
        cur_r+=1

    assert l>=1
    ans[i]=B.sum(r)-B.sum(l-1)


print("\n".join(map(str,ans)))