Problem:


Score : 600 points

Problem Statement

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

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

Constraints

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

1\leq c_i \leq N

1\leq l_i \leq r_i \leq N

All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

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

Sample Output 1

2
3
1

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

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

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

Sample Input 2

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

Sample Output 2

1
2
2
1
2
2
6
3
3
3



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


Sample output:
2
3
1

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n,q=map(int,input().split())
c=list(map(int,input().split()))
l=[list(map(int,input().split())) for i in range(q)]
for i in range(q):
  l[i]=[i,l[i][0],l[i][1]]
l2=sorted(l,key=itemgetter(2))

L=[-1 for i in range(max(c))]

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

  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
 
  def lower_bound(self,x):
    sum_=0
    pos=0
    for i in range(self.depth,-1,-1):
      k=pos+(1<<i)
      if k<=self.size and sum_+self.tree[k]<x:
        sum_+=self.tree[k]
        pos+=1<<i
    return pos+1,sum_

BIT=Bit(n+1)

ans=[]
ct=0
for i in range(q):
  while ct<=l2[i][2]:
    if L[c[ct-1]-1]!=-1:
      BIT.add(L[c[ct-1]-1],-1)
    L[c[ct-1]-1]=ct+1
    BIT.add(ct+1,1)
    ct+=1
  ans.append([l2[i][0],BIT.sum(l2[i][2]+1)-BIT.sum(l2[i][1])])

ans.sort()
for i in range(q):
  print(ans[i][1])

Submission status: Time Limit Exceeded

Solution code:
n,q=map(int,input().split())
c=list(map(int,input().split()))
xy = [map(int, input().split()) for _ in range(q)]
l, r = [list(i) for i in zip(*xy)]

for i in range(q):
    li=l[i]
    ri=r[i]
    rllist=c[(li-1):ri]
    rlset=set(rllist)
    ans=len(rlset)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int, input().split())
c = list(map(int, input().split()))
lr=[list(map(int,input().split())) for i in range(q)]

# min->inf, max->-inf, add->0, mul->1
ide_ele = set()

def segfunc(x, y):
    return x | y
class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        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):
        # param k: index(0-index)
        # param 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) 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

al = [{c[i]} for i in range(n)]
seg = SegTree(al, segfunc, ide_ele)

for l,r in lr:
    print(len(seg.query(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
import sys
rl = sys.stdin.readline
class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,a,idx):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx
    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)
def main():

    n,q = map(int,rl().split())
    C = list(map(int,rl().split()))
    ft = FenwickTree(n)
    qry = []
    for i in range(q):
        l,r = map(int,rl().split())
        qry.append((r-1,l-1,i))
    qry.sort()
    idxs=[-1]*n
    ans = [0]*q
    prev=0
    #print(0,0,idxs)
    for r,l,idx in qry:
        for i in range(prev,r+1):
            c = C[i]-1
            if idxs[c]!=-1:
                ft.add(-1,idxs[c])
            idxs[c]=i
            ft.add(1,i)
    #        print(c,i,idxs)
        ans[idx]=ft.sum(l,r)
    #    print(ft._sum(r),ft._sum(l-1))
        prev=r+1

    for a in ans:
        print(a)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,a,idx):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx
    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = map(int,input().split())
C = list(map(int,input().split()))
ft = FenwickTree(n)
qry = []
for i in range(q):
    l,r = map(int,input().split())
    qry.append((r-1,l-1,i))
qry.sort()
idxs=[-1]*n
ans = [0]*q
prev=0
#print(0,0,idxs)
for r,l,idx in qry:
    for i in range(prev,r+1):
        c = C[i]-1
        if idxs[c]!=-1:
            ft.add(-1,idxs[c])
        idxs[c]=i
        ft.add(1,i)
#        print(c,i,idxs)
    ans[idx]=ft.sum(l,r)
#    print(ft._sum(r),ft._sum(l-1))
    prev=r+1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
input = sys.stdin.buffer.readline
class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,a,idx):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx
    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = ma()
C = list(map(lambda x:int(x)-1,input().split()))
ft = FenwickTree(n)
qry = []
for i in range(q):
    l,r = map(int,input().split())
    qry.append((r-1,l-1,i))
qry.sort()
idxs=[-1]*n
ans = [0]*q
prev=0
#print(0,0,idxs)
for r,l,idx in qry:
    for i in range(prev,r+1):
        c = C[i]
        if idxs[c]!=-1:
            ft.add(-1,idxs[c])
        idxs[c]=i
        ft.add(1,i)
#        print(c,i,idxs)
    ans[idx]=ft.sum(l,r)
#    print(ft._sum(r),ft._sum(l-1))
    prev=r+1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys
input = sys.stdin.buffer.readline
class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,a,idx):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx
    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = ma()
C = list(map(lambda x:int(x)-1,input().split()))

ft = FenwickTree(n)
idxs=[-1]*n
for i in range(n):
    if idxs[C[i]]==-1:
        ft.add(1,i)
        idxs[C[i]]=i
qry = []
for i in range(q):
    l,r = map(int,input().split())
    qry.append((r-1,l-1,i))
qry.sort()
ans = [0]*q
prev=0
#print(0,0,idxs)
for r,l,idx in qry:
    for i in range(prev,r+1):
        c = C[i]
        ft.add(-1,idxs[c])
        idxs[c]=i
        ft.add(1,i)
#        print(c,i,idxs)
    ans[idx]=ft.sum(l,r)
#    print(ft._sum(r),ft._sum(l-1))
    prev=r+1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

if __name__ == '__main__':
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    LR = []
    for i in range(Q):
        LR.append(tuple(map(int, input().split())))
    ACC = []
    ACC.append({})
    hash = {} 
    for c in C:
        if c in hash:
            hash[c] += 1
        else:
            hash[c] = 1 
        ACC.append(deepcopy(hash))
    for l, r in LR:
        head = ACC[l-1]
        tail = ACC[r]
        head_set = set(head.keys())
        tail_set = set(tail.keys())
        only_have_tail = tail_set - head_set
        have_each = tail_set & head_set
        kind_cnt = len(only_have_tail)
        for key in have_each:
            if head[key] == tail[key]:
                pass
            else:
                kind_cnt += 1
        
        print(kind_cnt)

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
import sys

class FenwickTree():
    def __init__(self,n):
        self.n = n
        self.tree = [0]*(n+1)
    def add(self,a,idx):#値の更新
        idx+=1
        while idx<=self.n:
            self.tree[idx] +=a
            idx += idx &-idx

    def _sum(self,r):
        ret=0
        r+=1
        while r>0:
            ret+=self.tree[r]
            r-=r&-r
        return ret
    def sum(self,l,r):
        return self._sum(r)-self._sum(l-1)

n,q = ma()
C = list(map(lambda x:int(x)-1,input().split()))

ft = FenwickTree(n)
idxs=[-1]*n
for i in range(n):
    if idxs[C[i]]==-1:
        ft.add(1,i)
        idxs[C[i]]=i
qry = []
for i in range(q):
    l,r = ma()
    qry.append((l-1,r-1,i))
qry.sort(key=lambda x:x[1])
ans = [0]*q
prev=0
#print(0,0,idxs)
for l,r,idx in qry:
    for i in range(prev,r+1):
        c = C[i]
        ft.add(-1,idxs[c])
        idxs[c]=i
        ft.add(1,idxs[c])
#        print(c,i,idxs)
    ans[idx]=ft.sum(l,r)
#    print(ft._sum(r),ft._sum(l-1))
    prev=r+1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

if __name__ == '__main__':
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    LR = []
    for i in range(Q):
        LR.append(tuple(map(int, input().split())))
    ACC = []
    ACC.append({})
    hash = {} 
    for c in C:
        if c in hash:
            hash[c] += 1
        else:
            hash[c] = 1 
        ACC.append(deepcopy(hash))
    for l, r in LR:
        head = ACC[l-1]
        tail = ACC[r]
        delta = r - (l - 1)  
        kind_cnt = len(tail) - len(head)
        for h_key, h_value in head.items():
            if tail[h_key] - h_value > 0:
                kind_cnt += 1
                delta -= 1
            if delta == 0:
                break
        print(kind_cnt)

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

if __name__ == '__main__':
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    LR = []
    for i in range(Q):
        LR.append(tuple(map(int, input().split())))
    ACC = []
    ACC.append({})
    hash = {} 
    for c in C:
        if c in hash:
            hash[c] += 1
        else:
            hash[c] = 1 
        ACC.append(deepcopy(hash))
    for l, r in LR:
        head = ACC[l-1]
        tail = ACC[r]
        kind_cnt = len(tail) - len(head)
        for h_key, h_value in head.items():
            if tail[h_key] - h_value > 0:
                kind_cnt += 1
        print(kind_cnt)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


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


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


def main():
    readline = stdin.readline

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

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

    result = [None] * Q

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

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


main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin


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


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


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


def main():
    readline = stdin.readline

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

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

    result = [None] * Q

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

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

main()

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

if __name__ == '__main__':
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    LR = []
    for i in range(Q):
        LR.append(tuple(map(int, input().split())))
    ACC = []
    ACC.append({})
    hash = {} 
    for c in C:
        if c in hash:
            hash[c] += 1
        else:
            hash[c] = 1 
        ACC.append(deepcopy(hash))
    for l, r in LR:
        head = ACC[l-1]
        tail = ACC[r]
        kind_cnt = 0
        for t_key, t_value in tail.items():
            if t_key in head:
                h_value = head[t_key]
                if t_value - h_value > 0:
                    kind_cnt += 1
            else:
                kind_cnt += 1
        print(kind_cnt)

Submission status: Time Limit Exceeded

Solution code:
# region header
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
import copy
# @lru_cache(maxsize=None)
# sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9 + 7
eps = 10**-7
# endregion
# region input function


def inp():
    '''
    一つの整数
    '''
    return int(input())


def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))


def str_inp():
    '''
    文字列をリストとして読み込む
    '''
    return list(input()[:-1])

# endregion


class BinaryIndexedTree:
    def __init__(self, n):
        self.N = n
        self.bit = [0] * (n + 1)  # 1-index

    def sum(self, idx):
        """return sum(a[0]~a[idx])

        Args:
            idx (int): 1-index

        Returns:
            int: sum(a[0]+...+a[i])
        """
        res = 0
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def add(self, idx, x):
        """a[idx]+=x

        Args:
            idx (int): 1-index
            x (int): add value
        """
        while idx <= self.N:
            self.bit[idx] += x
            idx += idx & (-idx)


n, q = inpl()
c = inpl()
query = [inpl() + [i] for i in range(q)]
query.sort(key=itemgetter(1))
rightest = [-1] * (n + 1)
now_q = 0
Bit = BinaryIndexedTree(n)
ans = [0] * q

for i in range(n):
    if rightest[c[i]] != -1:
        Bit.add(rightest[c[i]] + 1, -1)
    rightest[c[i]] = i
    Bit.add(i + 1, 1)

    while now_q < q and query[now_q][1] == i + 1:
        ans[query[now_q][2]] = Bit.sum(query[now_q][1]) - Bit.sum(query[now_q][0] - 1)
        now_q += 1
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(300000)

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')

class SegmentTree(object):

    def __init__(self, A, e, fn):  # O(N)
        """
        :param A: 区間クエリの対象となる配列
        :param e: 単位元 fn(a, e) = fn(e, a) = a
        :param fn: (a, b) -> x な関数 a, bは交換則を満たす
        """
        self.e = e
        self.fn = fn
        self.length = 2 ** (len(A) - 1).bit_length()
        self.tree = [e] * 2 * self.length
        for i in range(len(A)):
            self.tree[i + self.length - 1] = A[i]
        for i in reversed(range(self.length - 1)):
            self.tree[i] = self.fn(self.tree[2 * i + 1], self.tree[2 * i + 2])

    # 配列のi番目をxに更新する
    def update(self, i, x):  # O(logN)
        i += self.length - 1
        self.tree[i] = x
        while i:
            i = (i - 1) // 2
            self.tree[i] = self.fn(self.tree[i * 2 + 1], self.tree[i * 2 + 2])

    # 区間[p, q)に関するクエリに答える
    def query(self, p, q):  # O(logN)
        if q <= p:
            return self.e
        p += self.length - 1
        q += self.length - 2
        res = self.e
        while q - p > 1:
            if p & 1 == 0:
                res = self.fn(res, self.tree[p])
            if q & 1 == 1:
                res = self.fn(res, self.tree[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.fn(res, self.tree[p])
        else:
            res = self.fn(self.fn(res, self.tree[p]), self.tree[q])
        return res

    # 現在のi番目の要素を取得する
    def at(self, i):  # O(1)
        return self.tree[i + self.length - 1]



N, Q = MI()
C = list(map(lambda x : {int(x)}, input().split()))

seg = SegmentTree(C, set(), lambda a, b: a | b)

for _ in range(Q):
    l, r = MI0()
    ans = len(seg.query(l, r + 1))
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree:
    def __init__(self, data, default=0, func=max):
        """initialize the segment tree with data"""
        self._default = default
        self._func = func
        self._len = len(data)
        self._size = _size = 1 << (self._len - 1).bit_length()

        self.data = [default] * (2 * _size)
        self.data[_size:_size + self._len] = data
        for i in reversed(range(_size)):
            self.data[i] = func(self.data[i + i], self.data[i + i + 1])

    def __delitem__(self, idx):
        self[idx] = self._default

    def __getitem__(self, idx):
        return self.data[idx + self._size]

    def __setitem__(self, idx, value):
        idx += self._size
        self.data[idx] = value
        idx >>= 1
        while idx:
            self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
            idx >>= 1

    def __len__(self):
        return self._len

    def query(self, start, stop):
        """func of data[start, stop)"""
        start += self._size
        stop += self._size

        res_left = res_right = self._default
        while start < stop:
            if start & 1:
                res_left = self._func(res_left, self.data[start])
                start += 1
            if stop & 1:
                stop -= 1
                res_right = self._func(self.data[stop], res_right)
            start >>= 1
            stop >>= 1

        return self._func(res_left, res_right)

    def __repr__(self):
        return "SegmentTree({0})".format(self.data)

n,q=map(int,input().strip().split(" "))
ar=list(map(int,input().strip().split(" ")))

temp=[]
for i in ar:
    t=set()
    t.add(i)
    temp.append(t.copy())
seg=SegmentTree(temp,default=set(),func=set.union)
for _ in range(q):
    a,b=map(int,input().strip().split(" "))
    a-=1
    b-=1
    print(len(seg.query(a,b+1)))

Submission status: Time Limit Exceeded

Solution code:
# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

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

from sys import stdin
input = stdin.buffer.readline

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
class BinaryIndexedTree:
    # a = [0] * n
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

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

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    BIT = BinaryIndexedTree(n)
    for i in range(n+1):
        if len(lis[i]) > 0:
            BIT.add(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            BIT.add(now_r, -1) # delete
            if len(lis[c[now_r]]) > 0:
                BIT.add(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = BIT.cumulative_sum(r) - BIT.cumulative_sum(l)
    
    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.data[2*i] + self.data[2*i+1]
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = lres + self.data[l]
                l += 1
            if not r & 1:
                rres = self.data[r] + rres
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = lres + self.data[l] + rres
        else:
            res = lres + rres
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    st = SegmentTree(n, default=0)
    for i in range(n+1):
        if len(lis[i]) > 0:
            st.update(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])

    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            st.update(now_r, 0) # delete
            if len(lis[c[now_r]]) > 0:
                st.update(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = st.query(l, r)
    
    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))

    lis = [[] for _ in range(n + 1)]
    for i, ci in enumerate(c):
        lis[ci].append(i)

    st = SegmentTree(n, f=lambda x, y: x + y, default=0)
    for i in range(n+1):
        if len(lis[i]) > 0:
            st.update(lis[i].pop(-1), 1)

    query = [0] * q
    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        query[lap] = (l-1, r, lap)
    
    query.sort(reverse=True, key=lambda x: x[1])
    
    now_r = n
    for ind, (l, r, lap) in enumerate(query):
        while now_r > r:
            now_r -= 1
            st.update(now_r, 0) # delete
            if len(lis[c[now_r]]) > 0:
                st.update(lis[c[now_r]].pop(-1), 1) # add
        ans[lap] = st.query(l, r)
    
    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

Solution code:
# Reference: https://qiita.com/dn6049949/items/afa12d5d079f518de368

# self.data: 1-indexed
#    __1__
#  _2_   _3_
# 4   5 6   7

# f(f(a, b), c) == f(a, f(b, c))

class SegmentTree:
    # a = [default] * n
    # O(n)
    def __init__(self, n, f=max, default=-2**30):
        self.num_leaf = 2 ** (n-1).bit_length()
        self.data = [default] * (2*self.num_leaf)
        self.f = f

    # a[i] = x
    # O(log(n))
    def update(self, i, x):
        i += self.num_leaf
        self.data[i] = x
        i >>= 1
        while i > 0:
            self.data[i] = self.f(self.data[2*i], self.data[2*i+1])
            i >>= 1

    # return f(a[l:r])
    # O(log(n))
    def query(self, l, r):
        l += self.num_leaf
        r += self.num_leaf - 1
        lres, rres = self.data[0], self.data[0] # self.data[0] == default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.data[l])
                l += 1
            if not r & 1:
                rres = self.f(self.data[r], rres)
                r -= 1
            l >>= 1
            r >>= 1
        if l == r:
            res = self.f(self.f(lres, self.data[l]), rres)
        else:
            res = self.f(lres, rres)
        return res

from sys import stdin
input = lambda: stdin.readline().strip()

def main():
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    
    st = SegmentTree(n, f=lambda x, y: x | y, default=set([]))
    for i, ci in enumerate(c):
        st.update(i, {ci})
    
    ans = [0] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = len(st.query(l-1, r))
    
    for i in ans:
        print(i)

main()

Submission status: Time Limit Exceeded

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


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


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

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

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

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

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

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