Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
3
1

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

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

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

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3



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


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    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())
clst = list(map(int, input().split()))
lr_1 = [list(map(int, input().split())) for _ in range(q)]
lr = lr_1.copy()
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = {}
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans[str(l) + "-" + str(r)] = (bit.sum(r) - bit.sum(l - 1))
        pos += 1
        if pos == q:
            break
    if pos == q:
        break

for l, r in lr_1:
    print(ans[str(l) + "-" + str(r)])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

memo=[np.zeros(N,dtype=int)]
tmp=np.zeros(N,dtype=int)
for i in range(N):
    tmp[C[i]-1]+=1
    memo.append(np.array(tmp))

for _ in range(Q):
    l,r=map(int,input().split())
    kinds=memo[r]-memo[l-1]
    kinds=list(kinds)
    print(N-kinds.count(0))

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
A=list(map(int,input().split()))
from collections import Counter
for i in range(q):
    a,b=map(int,input().split())
    print(len(Counter(A[a-1:b]).keys()))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import heapq
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
from math import ceil
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from decimal import Decimal #floatの高精度ver, 渡すのはstr型で
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#ソート、"a"+"b"、再帰ならPython3の方がいい
#######ここから天ぷら########
class BIT:
    def __init__(self,n):
        self.n=n
        self.data= [0]*(n+1) #これがBIT
        self.el= [0]*(n+1) #これが元データ
    def sum(self,i):  #iまでの和
        s=0
        while i>0:
            s+=self.data[i]
            i-= i&(-i)
        return s
    def add(self,i,x):  #iにxを足す(x<0)
        self.el[i]+=x
        while i<= self.n:
            self.data[i]+= x
            i+= i&-i
    def get(self,i,j=None):  #iからjまでの和、iだけなら普通の要素iを取得(いる？)
        if j is None:
            return self.el[i]
        return self.sum(j)-self.sum(i)
    

n,q=map(int,input().split())
C=list(map(int,input().split()))
C=[i-1 for i in C]  #球の純粋配置
Q=[]
for i in range(q):
    l,r=map(int,input().split())
    l-=1;r-=1
    Q.append([i,l,r])
Q=sorted(Q, key=lambda x:x[2]) 
ANS=[-1]*q

B=BIT(n)
YOI=[-1]*n #色iの良い球の位置
for i in range(Q[0][2],-1,-1):
    if YOI[C[i]]==-1:
        YOI[C[i]]=i
        B.add(i+1,1)

# 
ANS[Q[0][0]]= B.sum(Q[0][2]+1)- B.sum(Q[0][1])
left=Q[0][1]; right=Q[0][2]
#print(B.data)
# right=-1
for l in Q:
    newleft,newright=l[1],l[2]
    for i in range(newright,right,-1):
        if YOI[C[i]]==-1: #新種の色
            YOI[C[i]]=i
            B.add(i+1, 1)
        elif YOI[C[i]]>i:
            continue
        else:
            B.add(YOI[C[i]]+1, -1)
            YOI[C[i]]=i
            B.add(i+1, 1)
    ANS[l[0]]= B.sum(newright+1)- B.sum(newleft)
    right=newright
    #print(B.data)
for i in ANS:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = [ int(x) for x in input().split() ]
buf, idx = [{}], {}
for x in input().split():
  idx[x] = idx.get(x, 0) + 1
  buf.append(idx.copy())
for _ in range(q):
  i, j = [ int(x) for x in input().split() ]
  idx = buf[i - 1]
  print(len([ k for k,v in buf[j].items() if idx.get(k, 0) < v ]))

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))
for _ in range(q):
  l,r = map(int,input().split())
  print(len(set(c[(l-1):r])))

Submission status: Time Limit Exceeded

Solution code:
n, q = [ int(x) for x in input().split() ]
buf, idx = [{}], {}
for x in input().split():
  idx[x] = idx.get(x, 0) + 1
  buf.append(idx.copy())
for _ in range(q):
  i, j = [ int(x) for x in input().split() ]
  idx = buf[j].copy()
  for k,v in buf[i-1].items(): idx[k] -= v
  print(len([ v for v in idx.values() if v ]))

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    import sys
    input = sys.stdin.readline
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    mc=max(c)
    col=[[-1]*mc for _ in range(n)]
    bit=[[0]*n for _ in range(n)]
    col[0][c[0]-1]=0
    for i in range(1,n):
      for j in range(mc):
        if j==c[i]-1:
          col[i][j]=i
        else:
          col[i][j]=col[i-1][j]
    for i in range(n):
      for j in col[i]:
        if j>-1:
          bit[i][j]=1
    for i in range(q):
      l,r=map(int,input().split())
      print(sum(bit[r-1][l-1:r]))
    
if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# reffer to: https://qiita.com/dn6049949/items/afa12d5d079f518de368
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.data = [default for _ in range(self.size * 2)]  # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.data[i] = x
        while i > 0:
            i >>= 1
            self.data[i] = self.f(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.data[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res


def main():
    N, Q = LI()
    C = LI()
    lr = LIR1(Q)

    tree = SegmentTree(N, f=lambda x, y: x.union(y), default=set())
    for i, c in enumerate(C):
        tree.update(i, set([c]))

    for l, r in lr:
        print(len(tree.query(l, r+1)))





if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    def I(): return int(input())
    
    readline = sys.stdin.readline
    readall = sys.stdin.read
    MI = lambda: map(int, readline().split())
    LI = lambda: list(map(int, readline().split()))
    
    class BIT:
        '''
        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

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(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_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

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

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        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

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(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_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

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

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        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

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(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_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないところを-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

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

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        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

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(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_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N+3)
    dd=[N+3]*(N+1)#多くとっておく
    
    ans=[0]*Q
    pre=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            bit.add(old,-1)#もしまだ出てきていないなら，範囲外の使わないとこ炉を-1する
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

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

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    class BIT:
        '''
        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

        # [l,r)の和
        def bitsum(self, l, r=None):
            if r is None:
                return self._bitsum(l)
            else:
                return self._bitsum(r) - self._bitsum(l)

        # i番目にxを追加
        def add(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_

    
    N,Q=MI()
    C=LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r-1
        L[i]=l-1
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    dd=[-1]*(N+1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(N)
    
    ans=[0]*Q
    pre=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                bit.add(old,-1)
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.bitsum(l,r+1)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

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

    def I(): return int(input())
    def MI(): return map(int, input().split())
    def LI(): return list(map(int, input().split()))
    
    #1-index
    class BIT:
        def __init__(self, size=10**7):
            self.size = size
            self.data = [0]*(size+1)

        # index番目に+aする
        def add(self, index, x):
            while index <= self.size:
                self.data[index] += x
                index += index & -index

        # 先頭からindexまでの和
        def prefix_sum(self, index):
            res = 0
            while index >= 1:
                res += self.data[index]
                index -= index & -index
            return res

        # [l,r]の和
        def interval_sum(self, left, right):
            return self.prefix_sum(right) - self.prefix_sum(left-1)

        # index番目の値を返す
        def __getitem__(self, index):
            return self.sum(index) - self.sum(index-1)

    
    N,Q=MI()
    C=[0]+LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r
        L[i]=l
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    dd=[-1]*(N+1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(size = N+1)
    
    ans=[0]*Q
    pre=0
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                bit.add(old,-1)
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.interval_sum(l,r)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #1-index
    class BIT:
        def __init__(self, size=10**7):
            self.size = size
            self.data = [0]*(size+1)

        # index番目に+aする
        def add(self, index, x):
            while index <= self.size:
                self.data[index] += x
                index += index & -index

        # 先頭からindexまでの和
        def prefix_sum(self, index):
            res = 0
            while index >= 1:
                res += self.data[index]
                index -= index & -index
            return res

        # [l,r]の和
        def interval_sum(self, left, right):
            return self.prefix_sum(right) - self.prefix_sum(left-1)

        # index番目の値を返す
        def __getitem__(self, index):
            return self.sum(index) - self.sum(index-1)

    
    N,Q=MI()
    C=[0]+LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r
        L[i]=l
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    dd=[-1]*(N+1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(size = N+1)
    
    ans=[0]*Q
    pre=0
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                bit.add(old,-1)
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.interval_sum(l,r)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    #1-index
    class BIT:
        def __init__(self, size=10**7):
            self.size = size
            self.data = [0]*(size+1)

        # index番目に+aする
        def add(self, index, x):
            while index <= self.size:
                self.data[index] += x
                index += index & -index

        # 先頭からindexまでの和
        def prefix_sum(self, index):
            res = 0
            while index >= 1:
                res += self.data[index]
                index -= index & -index
            return res

        # [l,r]の和
        def interval_sum(self, left, right):
            return self.prefix_sum(right) - self.prefix_sum(left-1)

        # index番目の値を返す
        def __getitem__(self, index):
            return self.sum(index) - self.sum(index-1)

    
    N,Q=MI()
    C=[0]+LI()
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r=MI()
        R[i]=r
        L[i]=l
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    
    from collections import defaultdict
    dd = defaultdict(lambda :-1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかBITで管理
    """
    bit=BIT(size = N+1)
    
    ans=[0]*Q
    pre=0
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(pre+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                bit.add(old,-1)
            #最新を追加
            dd[c]=j
            bit.add(j,1)
        pre=r
        ans[i]=bit.interval_sum(l,r)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
n, q = map(int,input().split())
l = [i for i in map(int, input().split())]
for _ in range(q):
  a, b = map(int, sys.stdin.readline().split())
  pl = l[a-1:b]
  print(len(set(pl)))

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    N,Q=MI()
    C=LI()#あとで１引く
    
    RLI=[]
    
    for i in range(Q):
        l,r=MI()
        l-=1
        r-=1
        RLI.append([r,l,i])
        
    RLI.sort()
    #####segfunc######

    #評価関数（という言い方であっている？）
    def segfunc(x,y):
        return x+y


    #初期化
    def init(init_val):
        #init_valは操作する数列
        for i in range(N):
            seg[i+num-1]=init_val[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 


    #k番目の値をxに更新
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])


    #[p,q)の区間に対するクエリへの応答
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res


    #####単位元######
    ide_ele = 0


    #num:N以上の最小の2のべき乗
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    
    from collections import defaultdict
    dd = defaultdict(lambda :-1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかseg木で管理
    """
    
    ans=[0]*Q
    now=-1
    for r,l,i in RLI:
        for j in range(now+1,r+1,1):
            c=C[j]-1
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                update(old,0)
            #最新を追加
            dd[c]=j
            update(j,1)
        now=r
        ans[i]=query(l,r+1)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():

    mod=10**9+7
    N,Q=MI()
    C=LI()
    for i in range(N):
        C[i]-=1
    
    R=[0]*Q
    L=[0]*Q
    I=[0]*Q
    for i in range(Q):
        l,r,=MI()
        l-=1
        r-=1
        R[i]=r
        L[i]=l
        I[i]=i
        
    R,L,I = zip(*sorted(zip(R,L,I)))
    #####segfunc######

    #評価関数（という言い方であっている？）
    def segfunc(x,y):
        return x+y


    #初期化
    def init(init_val):
        #init_valは操作する数列
        for i in range(N):
            seg[i+num-1]=init_val[i]    
        #built
        for i in range(num-2,-1,-1) :
            seg[i]=segfunc(seg[2*i+1],seg[2*i+2]) 


    #k番目の値をxに更新
    def update(k,x):
        k += num-1
        seg[k] = x
        while k:
            k = (k-1)//2
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])


    #[p,q)の区間に対するクエリへの応答
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res


    #####単位元######
    ide_ele = 0


    #num:N以上の最小の2のべき乗
    num =2**(N-1).bit_length()
    seg=[ide_ele]*2*num
    
    from collections import defaultdict
    dd = defaultdict(lambda :-1)
    
    """
    事前処理 + クエリの高速処理
    or 
    クエリ先読み
    
    とりあえずrの昇順にクエリをソートしておく．
    結局，各色ごとに1つ前のやつがどこにあるかが問題=>各色ごとに最新の物だけを保持すれば良い．
    最終的にクエリに答えたいので，i番目が使えるかどうかseg木で管理
    """
    
    ans=[0]*Q
    now=-1
    for ii in range(Q):
        r=R[ii]
        l=L[ii]
        i=I[ii]
        for j in range(now+1,r+1,1):
            c=C[j]
            old=dd[c]#その色の古いやつ
            if old!=-1:#あれば削除
                update(old,0)
            #最新を追加
            dd[c]=j
            update(j,1)
        now=r
        ans[i]=query(l,r+1)
        
    for i in range(Q):
        print(ans[i])
main()