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


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 = [-1]*(N+1)
ans = [0]*(Q)

for l, r, k in m:
    if right!=r:
        for i in range(right, r):
            if pos[c[i]] != -1:
                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)

Submission status: Time Limit Exceeded

Solution code:
from operator import or_
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(lambda x:{int(x)}, input().split())
    tree = SegTree(N, set(), or_)
    tree.set_list(c)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(len(tree.get(l-1, r)))
    

solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import or_


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(lambda x:{int(x)}, input().split())
    tree = SegTree(N, set(), or_)
    tree.set_list(c)
    for _ in range(Q):
        l, r = map(int, input().split())
        print(len(tree.get(l-1, r)))
    

solve()

Submission status: Time Limit Exceeded

Solution code:
from operator import or_


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


N, Q = map(int, input().split())
*c, = map(lambda x:{x}, input().split())
tree = SegTree(N, set(), or_)
tree.set_list(c)
for _ in range(Q):
    l, r = map(int, input().split())
    print(len(tree.get(l-1, r)))

Submission status: Time Limit Exceeded

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

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

from collections import defaultdict

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

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

class RangeAddBIT:
    def __init__(self, n):
        self.n = n
        self.bit1 = BIT(n)
        self.bit2 = BIT(n)

    def init(self, init_val):
        self.bit2.init(init_val)

    def add(self, l, r, x):
        # add x to [l, r)
        # l, r: 0-indexed
        self.bit1.add(l, x)
        self.bit1.add(r, -x)
        self.bit2.add(l, -x*l)
        self.bit2.add(r, x*r)

    def sum(self, l, r):
        # return sum of [l, r)
        # l, r: 0-indexed
        return self._sum(r) - self._sum(l)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        return self.bit1._sum(i)*i + self.bit2._sum(i)

def main():

    n, q = map(int, input().split())
    C = list(map(int, input().split()))
    LI = [[] for _ in range(n)]
    for i in range(q):
        l, r = map(int, input().split())
        l, r = l-1, r-1
        LI[r].append((l, i))

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

    bit = RangeAddBIT(n)
    preidx = defaultdict(lambda: -1)
    ans = [-1]*q
    for r in range(n):
        p = preidx[C[r]]
        bit.add(p+1, r+1, 1)
        preidx[C[r]] = r
        for l, i in LI[r]:
            ans[i] = bit.sum(l, l+1)
    print(*ans, sep='\n')

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# Binary Index Tree (2-dimension)
class BIT2:
    # H*W, 0-based
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    #O(logH*logW)
    #[0.i)x[0.j)
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    # O(logH*logW)
    def add(self, i, j, weight):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + weight
                k|=(k+1)
            i|=(i+1)
    # [x0, x1) x [y0, y1)
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
n,m=map(int,input().split())
colors=list(map(int,input().split()))
from collections import defaultdict
bit=BIT2(n,n)
d=defaultdict(lambda:-1)
for i,v in enumerate(colors):
    if d[v]!=-1:
        bit.add(d[v],i,1)
    d[v]=i
for i in inputs():
    l,r=map(int,i.split())
    print(r+1-l-bit.range_sum(l-1,r,l-1,r))

Submission status: Time Limit Exceeded

Solution code:
# Binary Index Tree (2-dimension)
class BIT2:
    # H*W, 0-based
    def __init__(self, h, w):
        self.w,self.h=w,h
        self.data = [{}for i in range(h+1)]
    #O(logH*logW)
    #[0.i)x[0.j)
    def sum(self, i, j):
        s = 0
        i -= 1
        data = self.data
        while i >= 0:
            el = data[i]
            k = j - 1 
            while k >= 0:
                s += el.get(k, 0)
                k =( k & (k+1)) - 1

            i = (i&(i+1))-1
        return s

    # O(logH*logW)
    def add(self, i, j, weight):
        w = self.w; h = self.h
        data = self.data
        while i < h:
            el = data[i]
            k = j
            while k < w:
                el[k] = el.get(k, 0) + weight
                k|=(k+1)
            i|=(i+1)
    # [x0, x1) x [y0, y1)
    def range_sum(self, x0, x1, y0, y1):
        return self.sum(x1, y1) - self.sum(x1, y0) - self.sum(x0, y1) + self.sum(x0, y0)
import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
n,m=map(int,input().split())
colors=list(map(int,input().split()))
from collections import defaultdict
bit=BIT2(n,n)
d=defaultdict(lambda:-1)
for i,v in enumerate(colors):
    if d[v]!=-1:
        bit.add(d[v],i,1)
    d[v]=i
for i in inputs():
    l,r=map(int,i.split())
    print(r+1-l-bit.range_sum(l-1,r,l-1,r))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import Counter


def main():
    N,Q = list(map(int, sys.stdin.readline().split()))
    c_list = list(map(int, sys.stdin.readline().split()))
    lr_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(Q) ]


    cnt_dic = Counter()
    cum_sum = [Counter()]

    for c in c_list:
        cnt_dic[c] += 1
        cum_sum.append( Counter(cnt_dic) )


    for l,r in lr_list:
        current = cum_sum[r] - cum_sum[l-1]
        num = len( [ k for k,v in current.items() if v != 0 ] )
        print(num)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
BIT = [0] * ((1 << 19) + 1)
def add(i, x):
    while i <= (1 << 19):
        BIT[i] += x
        i += i & (-i)
def query(i):
    res = 0
    while i > 0:
        res += BIT[i]
        i -= i & (-i)
    return res
n, q = map(int, input().split())
c = list(map(int, input().split()))
Q = [[] for i in range(n)]
for i in range(q):
    l, r = map(int, input().split())
    Q[r - 1].append([l - 1, i])
l = [-1] * n
a = [-1] * q
add(1, n)
for i in range(n):
    add(l[c[i] - 1] + 2, -1)
    add(i + 2, 1)
    l[c[i] - 1] = i
    for j in Q[i]:
        a[j[1]] = query(1 << 19) - query(j[0] + 1)
print(*a, sep="\n")

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

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 = [inpl()+[_] for _ in range(q)]
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:
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:
    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)

n,q = inpl()
c = inpl()
queries = [inpl()+[_] for _ in range(q)]
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(n+1)[::-1]:
    while sec_ind < sec_ln and sec[sec_ind][0] >= i:
        x = sec[sec_ind][1]
        bit.add(x,1)
        sec_ind += 1
    
    while que_ind < q and queries[que_ind][0] >= i:
        _,x,ind = queries[que_ind]
        res[ind] = x-_+1 - bit.get(1,x)
        que_ind += 1
print(*res)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time

def main():
    input=stdin.readline
    n,q=map(int,input().split())
    c=list(map(int,input().split()))
    lri=[]
    # O(n)
    for i in range(q):
        l,r=map(int, input().split())
        l-=1
        r-=1
        lri.append((l,r,i))
    size=n+1
    seg=[0]*size
    def add(idx,val):
        idx+=1
        while idx<size:
            seg[idx]+=val
            idx+=idx&(-idx)
    def sum(idx):
        idx+=1
        res=0
        while idx>0:
            res+=seg[idx]
            idx-=idx&(-idx)
        return res
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]-1]!=-1:
            rr[bfr[c[i]-1]]=i
        bfr[c[i]-1]=i
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time

def main():
    input=stdin.readline
    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        lri.append((l,r,i))
    size=n+1
    seg=[0]*size
    def add(idx,val):
        idx+=1
        while idx<size:
            seg[idx]+=val
            idx+=idx&(-idx)
    def sum(idx):
        idx+=1
        res=0
        while idx>0:
            res+=seg[idx]
            idx-=idx&(-idx)
        return res
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time


def main():
    input=stdin.readline
    class Bit:
        def __init__(self,size):
            self.size=size+1
            self.seg=[0]*self.size
        def add(self,idx,val):
            idx+=1
            while idx<self.size:
                self.seg[idx]+=val
                idx+=idx&(-idx)
        def sum(self,idx):
            idx+=1
            res=0
            while idx>0:
                res+=self.seg[idx]
                idx-=idx&(-idx)
            return res

    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    heapify(lri)
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        heappush(lri,(-l,r,i))
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    bit=Bit(n)
    
    ans=[-1]*q
    # O(logn)
    lft,rgt,idx=heappop(lri)
    lft=-1*lft
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            bit.add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(bit.sum(rgt))
            if lri:
                lft,rgt,idx=heappop(lri)
                lft=-1*lft
            else:
                break
    for i in ans:
        print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time


def main():
    input=stdin.readline
    class Bit:
        def __init__(self,size):
            self.size=size+1
            self.seg=[0]*self.size
        def add(self,idx,val):
            idx+=1
            while idx<self.size:
                self.seg[idx]+=val
                idx+=idx&(-idx)
        def sum(self,idx):
            idx+=1
            res=0
            while idx>0:
                res+=self.seg[idx]
                idx-=idx&(-idx)
            return res

    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        lri.append((l,r,i))
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    bit=Bit(n)
    
    ans=[-1]*q
    # O(logn)
    lri.sort()
    lridx=len(lri)-1
    lft,rgt,idx=lri[lridx]
    lridx-=1
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            bit.add(rr.get(lt),1)
        # O(>n)
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(bit.sum(rgt))
            if lridx<0:
                break
            lft,rgt,idx=lri[lridx]
            lridx-=1
    for i in ans:
        print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from collections import defaultdict
from collections import deque
from heapq import heapify
from heapq import heappop
from heapq import heappush
from pprint import pprint
from sys import setrecursionlimit
from sys import stdin
from time import time
input=stdin.readline

def main():
    class Bit:
        def __init__(self,size):
            self.size=size+1
            self.seg=[0]*self.size
        def add(self,idx,val):
            idx+=1
            while idx<self.size:
                self.seg[idx]+=val
                idx+=idx&(-idx)
        def sum(self,idx):
            idx+=1
            res=0
            while idx>0:
                res+=self.seg[idx]
                idx-=idx&(-idx)
            return res

    n,q=[int(x) for x in input().split()]
    c=[int(x)-1 for x in input().split()]
    lri=[]
    # O(n)
    for i in range(q):
        l,r=[int(x)-1 for x in input().split()]
        lri.append((l,r,i))
    
    rr=defaultdict()
    bfr=[-1]*n
    # O(n)
    for i in range(n):
        if bfr[c[i]]!=-1:
            rr[bfr[c[i]]]=i
        bfr[c[i]]=i
    
    bit=Bit(n)
    
    ans=[-1]*q
    # O(logn)
    lri.sort(reverse=True)
    lri=deque(lri)
    lft,rgt,idx=lri.popleft()
    # O(n)
    for lt in range(n-1,-1,-1):
        # O(logn)
        if rr.get(lt) is not None:
            bit.add(rr.get(lt),1)
        # O(
        while lft==lt:
            # O(logn)
            ans[idx]=rgt-lft+1-(bit.sum(rgt))
            if len(lri)==0:
                break
            lft,rgt,idx=lri.popleft()
    for i in ans:
        print(i)
main()

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from pprint import pprint
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

class Bit:
    def __init__(self,size):
        self.size=size+1
        self.seg=[0]*self.size
    def add(self,idx,val):
        idx+=1
        while idx<self.size:
            self.seg[idx]+=val
            idx+=idx&(-idx)
    def sum(self,idx):
        idx+=1
        res=0
        while idx>0:
            res+=self.seg[idx]
            idx-=idx&(-idx)
        return res

n,q=[int(x) for x in input().split()]
c=[int(x)-1 for x in input().split()]
lri=[]
# O(n)
for i in range(q):
    l,r=[int(x)-1 for x in input().split()]
    lri.append((l,r,i))

rr=defaultdict()
bfr=[-1]*n
# O(n)
for i in range(n):
    if bfr[c[i]]!=-1:
        rr[bfr[c[i]]]=i
    bfr[c[i]]=i

bit=Bit(n)

ans=[-1]*q
# O(logn)
lri.sort(reverse=True)
lri=deque(lri)
lft,rgt,idx=lri.popleft()
# O(n)
for lt in range(n-1,-1,-1):
    # O(logn)
    if rr.get(lt) is not None:
        bit.add(rr.get(lt),1)
    # O(n)?
    while lft==lt:
        # O(logn)
        ans[idx]=rgt-lft+1-(bit.sum(rgt))
        if len(lri)==0:
            break
        lft,rgt,idx=lri.popleft()
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
from collections import Counter
from collections import defaultdict
from collections import deque
from pprint import pprint
from heapq import heapify
from heapq import heappop
from heapq import heappush
from time import time
setrecursionlimit(10**9)
mod=10**9+7
inf=10**18

class Bit:
    def __init__(self,size):
        self.size=size+1
        self.seg=[0]*self.size
    def add(self,idx,val):
        idx+=1
        while idx<self.size:
            self.seg[idx]+=val
            idx+=idx&(-idx)
    def sum(self,idx):
        idx+=1
        res=0
        while idx>0:
            res+=self.seg[idx]
            idx-=idx&(-idx)
        return res

n,q=[int(x) for x in input().split()]
c=[int(x)-1 for x in input().split()]
lri=[]
for i in range(q):
    l,r=[int(x)-1 for x in input().split()]
    lri.append((l,r,i))

rr=defaultdict()
bfr=[-1]*n
for i in range(n):
    if bfr[c[i]]!=-1:
        rr[bfr[c[i]]]=i
    bfr[c[i]]=i

bit=Bit(n)

ans=[-1]*q
lri.sort(reverse=True)
lri=deque(lri)
lft,rgt,idx=lri.popleft()
for lt in range(n-1,-1,-1):
    if rr.get(lt) is not None:
        bit.add(rr.get(lt),1)
    while lft==lt:
        ans[idx]=rgt-lft+1-(bit.sum(rgt))
        if len(lri)==0:
            break
        lft,rgt,idx=lri.popleft()
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#from numba import jit
[N, Q] = list(map(int, input().split()))
c = list(map(int, input().split()))

#import random
#[N, Q] = [500000, 500000]
#c = random.choices(range(1, 50000), k=N)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from numba import jit
[N, Q] = list(map(int, input().split()))
c = list(map(int, input().split()))

#import random
#[N, Q] = [500000, 500000]
#c = random.choices(range(1, 50000), k=N)

Qs = [None] * Q

Cs = [0] * (max(c)+1)
for i in range(N):
    Cs[ c[i] ] += 1

loc = np.zeros(max(c)+1, dtype=np.int32)
CCs = [np.zeros(Cs[i], dtype=np.int32) for i in range(max(c)+1)]
for i in range(len(c)):
    CCs[c[i]][ loc[c[i]] ] = i+1
    loc[c[i]] += 1

@jit(nopython=True)
def ntype(CCs, l, r):
    ret = 0
    for i in range(1, len(CCs)):
        if np.searchsorted(CCs[i], r, side='right') > np.searchsorted(CCs[i], l, side='left'):
            ret += 1
    return(ret)

for i in range(Q):
    [l, r] = list(map(int, input().split()))
    print(ntype(CCs, l, r))

Submission status: Time Limit Exceeded

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

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

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

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))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = [0]*Q
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,j in LR:
    for i in range(cur,r+1):
        c = C[i-1]
        if color[c] != 0:
            bit.add(color[c],-1)
        color[c] = i
        bit.add(i,1)
    cur = r+1
    ANS[j] = bit.sum(r)-bit.sum(l-1)
for a in ANS:
    print(a)

Submission status: Time Limit Exceeded

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

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

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

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))
bit = BIT(N)
#color[i] => 色iが最後に登場したインデックス(1-indexed)
color = [0]*(N+1)

ANS = [0]*Q
LR.sort(key=lambda x: x[1])
cur = 1
for l,r,i in LR:
    while cur <= r:
        c = C[cur-1]
        if color[c] == 0:
            color[c] = cur
            bit.add(cur,1)
        else:
            bit.add(color[c],-1)
            color[c] = cur
            bit.add(cur,1)
        cur += 1
    ANS[i] = bit.sum(r)-bit.sum(l-1)
for a in ANS:
    print(a)