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:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
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, 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

#%%

def function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = []
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        while order_num < Q:
            if lrs[order_num][1] == i:
                answer.append([len(answer),seg.query(lrs[order_num][0],lrs[order_num][1]+1)])
                order_num += 1
            else:
                break
            
    answer = sorted(answer,key=lambda x: lrs[x[0]][2])
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_all[val][pos_now[val]],-1)
      if pos_all[val][pos_now[val]+1]!=-1:
        pos_now[val]+=1
        bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
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, 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

#%%

def function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = []
    for i, c_o in enumerate(c):
        if right_edge[c_o] == -1:
            right_edge[c_o] = i
            seg.update(i, 1)
        elif right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
            right_edge[c_o] = i
            seg.update(i, 1)
        
        while True:
            if order_num >= Q:
                break
            if lrs[order_num][1] == i:
                answer.append([len(answer),seg.query(lrs[order_num][0],lrs[order_num][1]+1)])
                order_num += 1
            else:
                break
            
    answer = sorted(answer,key=lambda x: lrs[x[0]][2])
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
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, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

N, Q = map(int, input().split())
c = list(map(int, input().split()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i].append(i)

right_edge = [-1 for _ in range(N+1)]
seg = SegTree([0 for i in range(N+1)], segfunc, ide_ele)
# =============================================================================
# print(seg.tree[1])
# print(seg.query(0,7))
# seg.update(0,100)
# print(seg.tree)
# =============================================================================

lrs = sorted(lrs, key = lambda x:x[1])
order_num = 0
answer = []
for i, c_o in enumerate(c):
    if right_edge[c_o] == -1:
        right_edge[c_o] = i
        seg.update(i, 1)
    elif right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
    
    while True:
        if order_num >= Q:
            break
        if lrs[order_num][1] == i:
            answer.append([len(answer),seg.query(lrs[order_num][0],lrs[order_num][1]+1)])
            order_num += 1
        else:
            break
        
answer = sorted(answer,key=lambda x: lrs[x[0]][2])

for i in range(len(answer)):
    print(answer[i][1])

Submission status: Time Limit Exceeded

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

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[list(map(int,input().split()))+[i] for i in range(q)]
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_next=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    pos_now[val]=i+1
    bit.add(i+1,1)
  else:
    pos_next[val].append(i+1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_now[val],-1)
      if len(pos_next[val])!=0:
        pos_now[val]=pos_next[val][0]
        pos_next[val]=pos_next[val][1:]
        bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

Submission status: Time Limit Exceeded

Solution code:
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
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)　iとxが与えられたとき ai+=x とする (O(log n))
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)
  for ans in ANS:
    print(ans)
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#A1~Aiまでの和 O(logN)　iが与えられたとき a1~aiまでの和を計算する(O(log n))
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)　iとxが与えられたとき ai+=x とする (O(log n))
def BIT_update(BIT,idx,x,n):
  while idx<=n:
    BIT[idx]+=x
    idx+=idx&(-idx)
  return

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)
#A1 ... AnのBIT(1-indexed)
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)
    #その種類の登場が2回目　
    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)

for ans in ANS:
  print(ans)

Submission status: Time Limit Exceeded

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

l = []
r = []

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

cl = list(map(int,input().split()))

cpf = [Counter()]

for c in cl:
    cntr = cpf[-1].copy()
    cntr[c]+=1
    cpf.append(cntr)


for _ in range(Q):
    l,r = map(int,input().split())
    print(len(cpf[r]-cpf[l-1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

class BIT:
    """ Binary Indexed Tree """

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort(key=itemgetter(0))
ans = [0] * Q
for event in events:
    # 色の区間が来たら、点を追加
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    # クエリが来たら、点の数を数える
    else:
        r, _, l, i = event
        total = r - l + 1
        # 区間全体 - この時の領域内の点の数
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
from numba import*
@njit('i8[:](i8,i8,i8[:],i8[:,:])',cache=True)
def main(n,q,c,z):
  a=zeros(q,int64)
  t=zeros(9**6,int64)
  b=zeros(9**6,int64)
  j=0
  for i in argsort(z[:,1]):
    l,r=z[i,0],z[i,1]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:
        t[x]+=1
        x+=x&-x
      while y<=n:
        t[y]-=1
        y+=y&-y
    while l:
      a[i]+=t[l]
      l-=l&-l
  return a
(n,q),c,*z=[int_(t.split())for t in open(0)]
print(' '.join(map(str,main(n,q,c,int_(z)).tolist())))

Submission status: Time Limit Exceeded

Solution code:
from numpy import*
from numba import*
@njit('void(i8,i8,i8[:],i8[:,:])',cache=True)
def main(n,q,c,z):
  a=zeros(q,int64)
  t=zeros(9**6,int64)
  b=zeros(9**6,int64)
  j=0
  for i in argsort(z[:,1]):
    l,r=z[i,0],z[i,1]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:
        t[x]+=1
        x+=x&-x
      while y<=n:
        t[y]-=1
        y+=y&-y
    while l:
      a[i]+=t[l]
      l-=l&-l
  for i in a:print(i)
(n,q),c,*z=[int_(t.split())for t in open(0)]
main(n,q,c,int_(z))

Submission status: Time Limit Exceeded

Solution code:
def main():
  (n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:z[x][1]):
    l,r=z[i]
    while j<r:
      d=c[j]
      j+=1
      x,y,b[d]=b[d]+1,j+1,j
      while x<=n:t[x]+=1;x+=x&-x
      while y<=n:t[y]-=1;y+=y&-y
    while l:a[i]+=t[l];l-=l&-l
  print(' '.join(map(str,a)))
main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().rstrip("\r\n")
def List(): return list(map(int, input().split()))
def Num(): return int(input())



def build(tree, a):
    n = len(a)
    for i in range(n):
        tree[n + i].add(a[i])
    for i in range(n - 1, 0, -1):
        tree[i] |= tree[2 * i + 1]
        tree[i] |= tree[2 * i]


def query(tree, a, l, r):
    n = len(a)
    l += n
    r += n
    ans = set()
    while l < r:
        if l & 1:
            ans |= set(tree[l])
            l += 1
        if r & 1:
            r -= 1
            ans |= set(tree[r])
        l //= 2
        r //= 2
    return ans


n, q = List()
a = List()
tree = [set() for _ in range(2 * n)]
build(tree, a)
# print(tree)
for _ in range(q):
    l, r = List()
    print(len(query(tree, a, l - 1, r)))

Submission status: Time Limit Exceeded

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [(r, l, i) for i, (l, r) in enumerate([[int(x) for x in input().split()] for _ in range(q)])]
    query.sort()
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i+1:
                ans[c] = r-l+1-count+bit.summarize(l-1)
                index += 1
            else:
                break
        if index == q:
            break

    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    count = 0
    for i in range(n):
        if key[i] != -1:
            count += 1
            bit.add(key[i]+1, 1)
        while True:
            if index == q:
                break
            r, l, c = query[index]
            if r == i:
                ans[c] = r-l+1-count+bit.summarize(l)
                index += 1
            else:
                break
        if index == q:
            break
    
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

rpos_list=[-1]*(max(clist)+1)
rpos_list[clist[0]]=1
ans_dic={}

BIT=[0]*(N+1)
BIT_update(1,1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0+1,r+1):
      c=clist[i-1]
      if rpos_list[c]!=-1:
        BIT_update(rpos_list[c],-1)
      BIT_update(i,1)
      rpos_list[c]=i
    r0=r
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

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):
        # [0, i) の要素の総和を返す
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s
    # 0 index を 1 index に変更  転倒数を求めるなら1を足していく
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


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

Q.sort(key=lambda x: x[1])

bit = BIT(n)
ind = [-1]*(n+1)

ans = [0]*q
now = 0
for l,r,num in Q:
    while now < r:
        x = c[now]
        if ind[x] == -1:
            ind[x] = now
            bit.add(now,1)
        else:
            bit.add(ind[x],-1)
            ind[x] = now
            bit.add(now,1)
        now += 1
    ans[num] = bit.sum(r)-bit.sum(l-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*q
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l,r))
  rllist.append((r,l))
rllist.sort()
#print(rllist)

#A1～Aiまでの和 O(logN)
def BIT_query(idx):
  res_sum = 0
  while idx > 0:
    res_sum += BIT[idx]
    idx -= idx&(-idx)
  return res_sum
#Ai += x O(logN)
def BIT_update(idx,x):
  while idx <= N:
    BIT[idx] += x
    idx += idx&(-idx)
  return

dic_rpos={clist[0]:1}
ans_dic={}

BIT=[0]*(N+1)
BIT_update(1,1)
r0=1
for r,l in rllist:
  if r0<r:
    for i in range(r0+1,r+1):
      c=clist[i-1]
      if c in dic_rpos:
        BIT_update(dic_rpos[c],-1)
      BIT_update(i,1)
      dic_rpos[c]=i
    r0=r
      
  ans=BIT_query(r)-BIT_query(l-1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
N,Q=map(int,input().split())
clist=list(map(int,input().split()))

lrlist=[]
rllist=[]
for _ in range(Q):
  l,r=map(int,input().split())
  lrlist.append((l-1,r-1))
  rllist.append((r-1,l-1))
rllist.sort()
#print(rllist)

class SegTree:
  #init(init_val, ide_ele): 配列init_valで初期化 O(N)
  def __init__(self, init_val, segfunc, ide_ele):
    #init_val: 配列の初期値
    #segfunc: 区間にしたい操作
    #ide_ele: 単位元
    #n: 要素数
    #num: n以上の最小の2のべき乗
    #tree: セグメント木(1-index)
    n = len(init_val)
    self.segfunc = segfunc
    self.ide_ele = ide_ele
    self.num = 1 << (n - 1).bit_length()
    self.tree = [ide_ele] * 2 * self.num
    # 配列の値を葉にセット
    for i in range(n):
      self.tree[self.num + i] = init_val[i]
    # 構築していく
    for i in range(self.num - 1, 0, -1):
      self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

  #update(k, x): k番目の値をxに更新 O(logN)
  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

  #query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
  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
  
def segfunc(x,y):
  return x+y #区間和
#ide_ele
ide_ele=0 #区間和
  
dic_rpos={clist[0]:0}
ans_dic={}

seg=SegTree([float("inf")]*N, segfunc, ide_ele)
seg.update(0,1)
r0=0
for r,l in rllist:
  for i in range(r0+1,r+1):
    c=clist[i]
    if c in dic_rpos:
      seg.update(dic_rpos[c],0)
    seg.update(i,1)
    dic_rpos[c]=i
  r0=r
      
  ans=seg.query(l,r+1)
  ans_dic[(l,r)]=ans
  
for l,r in lrlist:
  print(ans_dic[(l,r)])