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:
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():
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

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


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


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

    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)))
    seg=SegTree(N,0,lambda a,b: a+b)
    Rn=[-1]*N#各色ごとに最右がどこか保持する
    
    """
    事前処理 + クエリの高速処理
    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=Rn[c]#その色の古いやつ
            if old!=-1:#あれば削除
                seg.update(old,0)
            #最新を追加
            Rn[c]=j
            seg.update(j,1)
        now=r
        ans[i]=seg.query(l,r+1)
        
    for i in range(Q):
        print(ans[i])
main()

Submission status: Time Limit Exceeded

Solution code:
# abc000_x.py
# https://atcoder.jp/contests/abc000

global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # X = int(lines[0])
    N, Q = list(map(int, lines[0].split()))
    values_c = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    valueses = list()
    for i in range(Q):
        valueses.append(list(map(int, lines[i+2].split())))

    results = list()

    for values in valueses:
        st, ed = values
        tmps = values_c[st-1:ed]
        cnt = len(set(tmps))
        results.append(cnt)

    return results


# 引数を取得
def get_input_lines():
    line = input()
    N, Q = list(map(int, line.split()))
    lines = list()
    lines.append(line)
    for _ in range(Q+1):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['4 3', '1 2 1 3', '1 3', '2 4', '3 3']
        lines_export = [2, 3, 1]
    if pattern == 2:
        lines_input = ['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']
        lines_export = [1, 2, 2, 1, 2, 2, 6, 3, 3, 3]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines()
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)
    log(lines_result)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexedTree:
    def __init__(self, size=10**7):
        self.size = size
        self.data = [0]*(size+1)

    def add(self, index, x):
        while index <= self.size:
            self.data[index] += x
            index += index & -index

    def sum(self, index):
        res = 0
        while index >= 1:
            res += self.data[index]
            index -= index & -index
        return res
    
    def get(self, left, right):
        return self.sum(right) - self.sum(left-1)

    def __getitem__(self, index):
        return self.sum(index) - self.sum(index-1)

    # def __setitem__(self, index, x):
    #     before = self.__getitem__(index)
    #     self.add(index, -before)
    #     self.add(index, x)

def main():
    from sys import setrecursionlimit, stdin, stderr
    from os import environ
    from collections import defaultdict, deque, Counter
    from math import ceil, floor
    from itertools import accumulate, combinations, combinations_with_replacement
    setrecursionlimit(10**6)
    dbg = (lambda *something: stderr.write("\033[92m{}\033[0m".format(str(something)+'\n'))) if 'TERM_PROGRAM' in environ else lambda *x: 0
    input = lambda: stdin.readline().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    P = 10**9+7
    INF = 10**18+10

    N,Q = LMIIS()
    # 1-indexedにするためリストの先頭に0を追加
    C = [0] + LMIIS()
    queries = []

    # 順番と一緒にクエリを保存
    for i in range(Q):
        queries.append((i,LMIIS()))
    
    # rについてクエリをソート
    queries.sort(key=lambda x: x[1][1])

    # 玉の種類 -> 良い玉の場所
    good_ball_places = [0] * (N+1)

    # 場所 -> 良い玉が存在するなら1,しないなら0
    good_ball_exists = BinaryIndexedTree()

    #　玉の更新範囲は[0:k]
    k = 1
    # クエリの回答
    out = [0] * Q
    for j,(l,r) in queries:
        for i in range(k,r+1):
            # 位置iの玉の色
            color = C[i]
            # 色colorの良い玉の前の位置
            before = good_ball_places[color]
            # 色colorが既出なら、良い玉の場所をリセット
            if before != 0:
                good_ball_exists.add(before,-1)
            
            # 色colorの良い玉の位置はi
            good_ball_places[color] = i
            # 位置iに良い玉が存在
            good_ball_exists.add(i,1)
        out[j] = good_ball_exists.get(l,r)
    print('\n'.join(map(str,out)))


        








    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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]) 
    
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])
    
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 = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
count = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r + 1
    ans[index] = query(l, r+1)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[2])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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]) 
    
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])
    
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 = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    pre_r = r
    ans[index] = query(l,r+1)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque, defaultdict
n, q = map(int ,input().split())
c = list(map(int, input().split()))
data = []
for i in range(q):
    data.append([i] + list(map(int, input().split())))
data.sort(key=lambda x : x[1])
ans = [0 for i in range(q)]
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val):
    #set_val
    for i in range(len(init_val)):
        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]) 
    
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])
    
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 = 2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
good_ball = dict()
pre_r = 0
for i in range(q):
    index, l, r = data[i]
    l, r = l-1, r-1
    for j in range(pre_r, r+1):
        if c[j] in good_ball : 
            update(good_ball[c[j]], 0)           
        update(j, 1)
        good_ball[c[j]] = j
    ans[index] = query(l,r+1)
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    # a - 1の場所にwを追加する
    def add(self, a, w):
        x = a
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    def get(self, a):
        ret, x = 0, a - 1
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    # 区間[l, r - 2]についての合計を求める
    def cum(self, l, r):
        return self.get(r) - self.get(l)

    def lowerbound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x + 1

# BITは前から置いていく
# そのためのクエリソート
N, Q = getNM()
C = getList()
que = [getList() for i in range(Q)]

# que[r]に[l(始点), i(queでのインデックス)]をappend
que_d = defaultdict(list)
for i in range(Q):
    que_d[que[i][1]].append([que[i][0], i])
ans = [0] * Q
# 色iのうち最も右側にあるものはどこにあるか
dic = defaultdict(lambda: -float('inf'))
bit = BIT(N)

for i in range(N):
    # 既に場所が登録されているならそれを削除する
    if dic[C[i]] >= 1:
        bit.add(dic[C[i]], -1)
    # 新しい「良い球」の場所を登録
    # 1-indexで!!
    dic[C[i]] = i + 1
    bit.add(dic[C[i]], 1)

    # queryに答える
    if len(que_d[i + 1]) > 0:
        for l, j in que_d[i + 1]:
            # cum(l, r):区間[l, r - 2]についての合計を求める
            ans[j] = bit.cum(l, i + 2)

for i in ans:
    print(i)

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


def solve(n, q, c_list, lr_list):
    lri_list = [[lr_list[i][0], lr_list[i][1], i] for i in range(q)]
    # sort by r
    lri_list_s = sorted(lri_list, key=lambda x: x[1])
    # dictionary
    color_dict = dict()
    # bit
    bit = BIT(n)

    res = [0] * q

    r_temp = 0
    for l, r, i in lri_list_s:
        while r > r_temp:
            r_temp += 1
            c = c_list[r_temp - 1]
            if c in color_dict.keys():
                bit.add(color_dict[c], -1)
            color_dict[c] = r_temp
            bit.add(r_temp, 1)
        # print(r, [bit.get(i) for i in range(n + 1)])
        res[i] = bit.get(l - 1, r)
    # print(res)
    return res


def main():
    n, q = map(int, input().split())
    c_list = list(map(int, input().split()))
    lr_list = [list(map(int, input().split())) for _ in range(q)]
    res = solve(n, q, c_list, lr_list)
    for r in res:
        print(r)


def test():
    assert solve(4, 3, [1, 2, 1, 3], [[1, 3], [2, 4], [3, 3]]) == [2, 3, 1]
    assert solve(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]
    ]) == [1, 2, 2, 1, 2, 2, 6, 3, 3, 3]


if __name__ == "__main__":
    test()
    main()

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())
  a = c[l-1:r]
  print(len(set(a)))

Submission status: Time Limit Exceeded

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

N, Q = map(int, input().rstrip().split())
C = list(map(int, input().rstrip().split()))
for _ in range(Q):
    l, r = map(int, input().rstrip().split())
    s = set(C[l - 1: r])
    print(len(s))

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())
    s = set(C[l - 1: r])
    print(len(s))

Submission status: Time Limit Exceeded

Solution code:
import sys
from numpy import*
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('\n'.join(map(str,main(n,q,c,int_(z)).tolist())))

Submission status: Time Limit Exceeded

Solution code:
SHIFT = 1 << 20


def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = []
    for j in range(Q):
        le, ri = (int(i) for i in input().split())
        Query.append(ri << 40 | le << 20 | j)
    Query.sort()

    # Query復元
    for i in range(Q):
        j = Query[i] % (SHIFT)
        Query[i] >>= 20
        le = Query[i] % (SHIFT)
        Query[i] >>= 20
        ri = Query[i]
        Query[i] = (le, ri, j)

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i

    lastappend = [-1] * (N + 1)
    bit = [0] * (N + 1)
    idx = 0  # Queryのindex
    ans = []

    for i, a in enumerate(C, start=1):
        if lastappend[a] != -1:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while idx < Q and i == Query[idx][1]:
            (le, ri, j) = Query[idx]
            ans.append((j, sum(bit, ri) - sum(bit, le-1)))
            idx += 1

    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0] * (N + 1)

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

    def add(tree, i, x):
        while i <= N:
            tree[i] += x
            i += i & -i
    bit = [0] * (N + 1)
    idx = 0
    ans = []

    for i, a in enumerate(C, start=1):
        if lastappend[a] != 0:
            add(bit, lastappend[a], -1)
        lastappend[a] = i
        add(bit, i, 1)
        while idx < Q and i == Query[idx][0][1]:
            (le, ri), j = Query[idx]
            ans.append((j, sum(bit, ri) - sum(bit, le-1)))
            idx += 1
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    def add(self, i, x):
        tmp = i + 1
        while tmp <= self.size:
            self.array[tmp] += x
            tmp += tmp & -tmp


def main():
    n, q = map(int, input().split())
    *C, = map(lambda x: int(x) - 1, input().split())
    P = [0] * n
    N = [None] * n
    for i in range(n)[::-1]:
        if P[C[i]]:
            N[i] = P[C[i]]
        P[C[i]] = i
    F = [0] * n
    B = BIT(n)
    for i in range(n):
        if F[C[i]] == 0:
            B.add(i, 1)
            F[C[i]] = 1
    XY = [tuple(map(int, input().split())) for j in range(q)]
    ids = list(range(q))
    ids.sort(key=lambda j: XY[j][0])
    a = 0
    lst = [0] * q
    for j in ids:
        x, y = XY[j]
        for i in range(a, x - 1):
            if N[i]:
                B.add(N[i], 1)
        a = x - 1
        lst[j] = B.sum(y) - B.sum(x - 1)
    print(*lst, sep="\n")


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, Q = (int(i) for i in input().split())
    C = [int(i) for i in input().split()]
    Query = [([int(i) for i in input().split()], j) for j in range(Q)]
    Query.sort(key=lambda p: p[0][1])
    lastappend = [0] * (N + 1)

    def sum(tree, i):
        s = 0
        while i > 0:
            s += tree[i]
            i -= i & -i
        return s

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

    for i, a in enumerate(C, start=1):
        if i <= Query[0][0][1]:
            lastappend[a] = i
    for la in lastappend[1:]:
        if la != 0:
            add(bit, la, 1)
    pre = Query[0][0][1]
    ans = []
    for (le, ri), j in Query:
        if pre < N and pre < ri:
            for i in range(pre+1, ri+1):
                pre_i = lastappend[C[i-1]]
                if pre_i != 0:
                    add(bit, pre_i, -1)
                lastappend[C[i-1]] = i
                add(bit, i, 1)
            pre = ri
        ans.append((j, sum(bit, ri) - sum(bit, le-1)))
    ans.sort()
    for _, a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class BIT():
    def __init__(self, n):
        """
        1-index
        sum -> i番目までの和
        add -> i番目にxを足す
        :param n:
        """
        self.n = n
        self.data = [0]*(n+1)
        self.each = [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.each[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def __str__(self):
        return str(self.each)



def main():
    N, Q = NMI()
    C = [0]+NLI()
    d_querys = [[i]+NLI() for i in range(Q)]
    querys = defaultdict(list)
    for qi, ql, qr in d_querys:
        querys[qr].append((qi, ql))

    ans = [0] * Q
    last_index = [-1] * (N+1)
    index_dict = defaultdict(list)
    tree = BIT(N)

    for i, color in enumerate(C):
        if color == 0: continue
        idx = last_index[color]
        if idx != -1:
            index_dict[i].append((idx, i))
        last_index[color] = i
        tree.add(i, 1)

    for i in range(1, N+1):
        for idx, _ in index_dict[i]:
            tree.add(idx, -1)
        for qi, ql in querys[i]:
            ans[qi] = tree.sum(i) - tree.sum(ql-1)

    for a in ans:
        print(a)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class BIT():
    def __init__(self, n):
        """
        1-index
        sum -> i番目までの和
        add -> i番目にxを足す
        :param n:
        """
        self.n = n
        self.data = [0]*(n+1)
        self.each = [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.each[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def __str__(self):
        return str(self.each)



def main():
    N, Q = NMI()
    C = [0]+NLI()
    querys = [[i]+NLI() for i in range(Q)]
    querys.sort(key=lambda x: x[2])
    ans = [0] * Q
    last_index = [-1] * (N+1)
    tree = BIT(N)
    idx = 1
    for query in querys:
        qi, ql, qr = query
        while idx <= N and idx <= qr:
            color = C[idx]
            if last_index[color] != -1:
                tree.add(last_index[color], -1)

            tree.add(idx, 1)
            last_index[color] = idx
            idx += 1

        ans[qi] = tree.sum(qr) - tree.sum(ql-1)

    for a in ans:
        print(a)




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


class BIT():
    def __init__(self, n):
        """
        1-index
        sum -> i番目までの和
        add -> i番目にxを足す
        :param n:
        """
        self.n = n
        self.data = [0]*(n+1)
        self.each = [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.each[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i

    def __str__(self):
        return str(self.each)



def main():
    N, Q = NMI()
    C = [0]+NLI()
    querys = [[i]+NLI() for i in range(Q)]
    querys.sort(key=lambda x: x[2])
    ans = [0] * Q
    last_index = [-1] * (N+1)
    tree = BIT(N)
    idx = 1
    for query in querys:
        qi, ql, qr = query
        while idx <= N and idx <= qr:
            color = C[idx]
            if last_index[color] != -1:
                tree.add(last_index[color], -1)

            tree.add(idx, 1)
            last_index[color] = idx
            idx += 1

        ans[qi] = tree.sum(qr) - tree.sum(ql-1)

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N, Q = map(int, input().split())
c = list(map(int, input().split()))
prev = [-1]*N
ys = defaultdict(list)

for i in range(N):
    if prev[c[i]-1]!=-1:
        ys[prev[c[i]-1]].append(i)
    
    prev[c[i]-1] = i

rs = defaultdict(list)

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

bit = BIT(N)
ans = [-1]*Q

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in rs[x]:
        ans[i] = r-x+1-bit.acc(r+1)

for ans_i in ans:
    print(ans_i)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = []

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E.append((D_i, i, -1))
        D[C[i]] = i
    x = len(E)
    E += [0] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        E[x + i] = (l - 1, r - 1, i)

    E.sort(key=lambda tup: tup[0], reverse=True)

    # Binary Indexed Tree (Fenwick Tree)
    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)

    ANS = [0] * Q
    d = BIT(N)
    for e in E:
        if e[2] == -1:
            d.add(e[1], 1)
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - d.sum(e[1])

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

if __name__ == '__main__':
    main()