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 typing import Union
from operator import itemgetter

Num = Union[int, float]



class FenwickTree:
    def __init__(self, size: int):
        self.size = size
        self.bit = [0] * (self.size + 1)
    
    def add(self, k: int, x: Num) -> None:
        """
        (0-index で) k 番目の要素に x をたす。
        >>> b = FenwickTree(5)
        >>> b.add(0, 10)
        >>> b.bit
        [0, 10, 10, 0, 10, 0]
        """
        if not 0 <= k < self.size:
            raise IndexError(f"FenwickTree.add(): size is {self.size}. accessed [{k}]")
        k += 1    # 1-index
        while k <= self.size:
            self.bit[k] += x
            LSB = k & (-k)
            k += LSB
    
    def _accum_sum(self, k: int) -> Num:
        """ (1-index, 内部関数) bit の 1 ~ k 番目の要素の和を求める。"""
        s = 0
        while k > 0:
            s += self.bit[k]
            LSB = k & (-k)
            k -= LSB
        return s
    
    def sum(self, l: int, r: int) -> Num:
        """
        (0-index で) [l, r) 区間の和を求める。
        >>> b = FenwickTree(5)
        >>> b.add(1, 10)
        >>> b.add(2, 20)
        >>> b.sum(1, 3)
        30
        """
        if not 0 <= l <= r <= self.size:
            raise IndexError(f"FenwickTree.sum(): size is {self.size}. got slice is [{l}:{r}]")
        # 0-index の数列における [l]...[r-1] の閉区間を計算。1-index なら [l+1]...[r]。
        return self._accum_sum(r) - self._accum_sum(l)


def mi():
    return map(int, input().split())


def mi_0():
    return map(lambda x: int(x)-1, input().split())


def solve(n, q, interval, query):
    """
    [s, t] なる点を含むリスト interval
    [l, r] (0-index) なるクエリを q 個含むリスト query。l <= s and t <= r なる点の個数は何個か？
    """
    # print(interval)
    # print(query)
    query_to_dup = dict()
    sorted_query = sorted(query, key=itemgetter(0))
    sorted_interval = sorted(interval, key=itemgetter(0))
    # print(sorted_interval)
    # print(sorted_query)
    ft = FenwickTree(n)
    # main
    for l, r in reversed(sorted_query):
        # l 以上のものを全て処理対象に入れる
        while sorted_interval and l <= sorted_interval[-1][0]:
            _, t = sorted_interval.pop()
            ft.add(t, 1)
        query_to_dup[(l, r)] = ft.sum(0, r+1)
        # print(ft.bit)
    # output
    for elm in query:
        l, r = elm
        dup = query_to_dup[elm]
        print(r - l + 1 - dup)



def main():
    n, q = mi()
    L = tuple(mi())
    prev = dict()
    intervals = []
    for i in range(n):
        if L[i] not in prev:
            prev[L[i]] = i
        else:
            intervals.append((prev[L[i]], i))
            prev[L[i]] = i
    query = [tuple(mi_0()) for _ in range(q)]
    solve(n, q, intervals, query)
    


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = max(colors)
right = [[0] * n]

for idx, c in enumerate(colors):
    if idx != 0:
        right.append(right[idx-1].copy())
    right[idx][c-1] += 1

for _ in range(Q):
    l, r = map(int, input().split())

    if l==r:
        print(1)
    elif l==1:
        ans = 0
        for r in right[r-1]:
            ans += (r!=0)
        print(ans)
    else:
        e = 0
        for l, r in zip(right[l-2], right[r-1]):
            if r - l >= 1:
                e += 1
        print(e)

Submission status: Time Limit Exceeded

Solution code:
import math

n, q = map(int, input().split())
c = [int(s) - 1 for s in input().split()]

m = math.floor(math.sqrt(q))
def sorter(t):
    i, l, r = t
    return (l//m, r)

tt = []
for i in range(q):
    l, r = map(int, input().split())
    tt.append((i, l-1, r-1))
tt.sort(key=sorter)

pl = 0
pr = 0
ans = [0]*q
d = [0]*n
d[c[0]] += 1
count = 1
for i, l, r in tt:
    while pl < l:
        d[c[pl]] -= 1
        if d[c[pl]]==0: count-=1
        pl += 1
    
    while pr < r:
        pr += 1
        d[c[pr]] += 1
        if d[c[pr]]==1: count+=1

    while r < pr:
        d[c[pr]] -= 1
        if d[c[pr]]==0: count-= 1
        pr -= 1

    ans[i] = count

for v in ans:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
def query(i):
    '''
    a[0] + a[1] + … + a[i-1] を求める
    O(logN)
    '''
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & -i
    
    return res


def update(i, x):
    '''
    a[i-1]にxを加算
    O(logN)
    '''
    while i <= n:
        BIT[i] += x
        i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))
query_ = [list(map(int, input().split())) + [i] for i in range(q)]

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

res = [0] * q
pos = [-1] * n
BIT = [0] * (n+1)
p = 0
for l, r, idx in query_:
    for i in range(p, r):
        if pos[c[i]-1] != -1:
            update(pos[c[i]-1]+1, -1)
        update(i+1, 1)
        pos[c[i]-1] = i
    
    res[idx] = query(r) - query(l-1)
    p = r

for v in res:
    print(v)

Submission status: Time Limit Exceeded

Solution code:
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

n, q = nm()
arr = nl()


for _ in range(q):
  l, r = nm()
  l -= 1; r -= 1;
  
  if l == r:
    print(1)
  else:
    print(len(set(arr[l:r+1])))

Submission status: Time Limit Exceeded

Solution code:
'''
Created on 2020/09/02

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write
  
  N,Q=map(int,pin().split())
  c=list(map(int,pin().split()))
  
  for _ in [0]*Q:
    l,r=map(int,pin().split())
    print(len(list(set(c[l-1:r]))))
  return 
main()

Submission status: Time Limit Exceeded

Solution code:
n,q = map(int,input().split())
c = list(map(int,input().split()))

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.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
 
    def bitsum(self, l, r=None): # [l, r)
        if r is None:
            return self._bitsum(l)
        else:
            return self._bitsum(r) - self._bitsum(l)
 
    def bitadd(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 = inpl()
c = inpl()
queries = []
for i in range(q):
    a,b = inpl()
    queries.append([a,b,i])
res = [-1] * q
d = [-1] * n
sec = []
for i,x in enumerate(c):
    if d[x-1] != -1:
        sec.append([d[x-1], i+1])
    d[x-1] = i+1
sec_ln = len(sec)
sec.sort(reverse = True)
queries.sort(reverse = True)
# print(queries)
bit = BIT(n)
sec_ind = que_ind = 0
for i in range(1,n+1)[::-1]:
    while sec_ind < sec_ln and sec[sec_ind][0] >= i:
        x = sec[sec_ind][1]
        bit.bitadd(x-1,1)
        sec_ind += 1
    
    while que_ind < q and queries[que_ind][0] >= i:
        _,x,ind = queries[que_ind]
        res[ind] = x-_+1 - bit.bitsum(0,x)
        que_ind += 1
print(*res)

Submission status: Time Limit Exceeded

Solution code:
def segfunc(x,y):
  return x|y
ide_ele=set()
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):
    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):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree(c,segfunc,ide_ele)
for _ in range(q):
  l,r=map(int,input().split())
  print(len(st.query(l-1,r)))

Submission status: Time Limit Exceeded

Solution code:
def segfunc(x,y):
  return set(x)|set(y)
ide_ele=set()
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):
    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):
    res=self.ide_ele
    l+=self.num
    r+=self.num
    while l<r:
      if l&1:
        res=self.segfunc(res,self.tree[l])
        l+=1
      if r&1:
        res=self.segfunc(res,self.tree[r-1])
      l>>=1
      r>>=1
    return res
n,q=map(int,input().split())
c=list(map(int,input().split()))
st=SegTree(c,segfunc,ide_ele)
for _ in range(q):
  l,r=map(int,input().split())
  print(len(st.query(l-1,r)))

Submission status: Time Limit Exceeded

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

    class FenwickTree:
        def __init__(self, size):
            self.size = size
            self.array = [0]*size
    
        def add(self, index, value):
            while index < self.size:
                self.array[index] += value
                index += index&(-index)
    
        def sum(self, index):
            answer = 0
            while index > 0:
                answer += self.array[index]
                index -= index&(-index)
            return answer
    
        def rangesum(self, start, end):
            return self.sum(end)-self.sum(start-1)


    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = FenwickTree(N+1)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for l, r, idx in m:
        for i in range(right, r):
            x = pos[c[i]]
            if x:
                tree.add(x, -1)
            pos[c[i]] = i+1
            tree.add(i+1, 1)
        ans[idx] = tree.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    for i in ans:
        print(i)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(tuple(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]] != -1:
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]]:
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


class FenwickTree:
 
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    # tree = SegTree(N+1, 0, add)
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for i in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]]:
                # tree.update(pos[c[i]], 0)
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            # tree.update(i+1, 1)
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r) #tree.get(l, r+1)
        right = r
    print(*ans, sep="\n")


solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


class FenwickTree:
 
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    tree2 = FenwickTree(N+1)
    m = [tuple(map(int, input().split())) for i in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]]:
                tree.update(pos[c[i]], 0)
                tree2.add(pos[c[i]], -1)
            pos[c[i]] = i+1
            tree.update(i+1, 1)
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r) #tree.get(l, r+1)
        right = r
    print(*ans, sep="\n")


solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    m = [tuple(map(int, input().split())) for i in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            if pos[c[i]]:
                tree.update(pos[c[i]], 0)
            pos[c[i]] = i+1
            tree.update(i+1, 1)
        ans[idx] = tree.get(l, r+1)
        right = r
    print(*ans, sep="\n")


solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    m = [tuple(map(int, input().split())) for i in range(Q)]
    idxs = sorted(range(Q), key=lambda i: m[i][1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for idx in idxs:
        l, r = m[idx]
        if right != r:
            for i in range(right, r):
                if pos[c[i]]:
                    tree.update(pos[c[i]], 0)
                pos[c[i]] = i+1
                tree.update(i+1, 1)
        ans[idx] = tree.get(l, r+1)
        right = r
    print(*ans, sep="\n")


solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import add


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for l, r, k in m:
        if right != r:
            for i in range(right, r):
                if pos[c[i]]:
                    tree.update(pos[c[i]], 0)
                pos[c[i]] = i+1
                tree.update(i+1, 1)
        ans[k] = tree.get(l, r+1)
        right = r
    print(*ans, sep="\n")


solve()

Submission status: Time Limit Exceeded

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


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree = SegTree(N+1, 0, add)
    m = [tuple(map(int, input().split()))+(i,) for i in range(Q)]
    m.sort(key=lambda x:x[1])

    right = 0
    pos = [None] * (N+1)
    ans = [None] * (Q)

    for l, r, k in m:
        if right != r:
            for i in range(right, r):
                if pos[c[i]]:
                    tree.update(pos[c[i]], 0)
                pos[c[i]] = i+1
                tree.update(i+1, 1)
        ans[k] = tree.get(l, r+1)
        right = r

    for i in ans:
        print(i)


solve()