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:
# 解説の解法はAtCoder expressみたいな二次元累積和っぽい考え方を平面走査とBIT(セグ木)で高速化
# ここではとりあえず遅延セグ木を用いてけんちょんさんの解法を投げてみる https://drken1215.hatenablog.com/entry/2019/01/01/234400


def _gidx(l, r, treesize):
    '''
    lazy propagation用idx生成器 木の下から生成される。1based-indexなので注意.(使うときは-1するとか)
    もとの配列において[l,r)を指定したときに更新すべきidxをyieldする
    treesizeは多くの場合self.num
    '''
    L, R = l + treesize, r + treesize
    lm = (L // (L & -L)) >> 1  # これで成り立つの天才か？
    rm = (R // (R & -R)) >> 1
    while L < R:
        if R <= rm:
            yield R
        if L <= lm:
            yield L
        L >>= 1
        R >>= 1
    while L:  # Rでもいいけどね
        yield L
        L >>= 1


import operator


class SegmentTreeForRSQandRAQ:  # 区間合計(ホントは何でも良い)クエリ と 区間加算クエリを扱うことにする
    def __init__(self, ls: list, segfunc=operator.add, identity_element=0, lazy_ide=0):
        '''
        セグ木 もしかしたらバグがあるかも
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.lide = lazy_ide  # lazy用単位元
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num)  # 関係ない値を-1においてアクセスを許すと都合が良い
        self.lazy = [self.lide] * (2 * self.num)  # 遅延配列
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def _lazyprop(self, *ids):
        '''
        遅延評価用の関数
        - self.tree[i] に self.lazy[i]の値を伝播させて遅延更新する
        - 子ノードにself.lazyの値を伝播させる **ここは問題ごとに書き換える必要がある**
        - self.lazy[i]をリセットする
        '''
        for i in reversed(ids):
            i -= 1  # to 0basedindex
            v = self.lazy[i]
            if v == self.lide:
                continue
            #########################################################
            # この4つの配列をどう更新するかは問題によって異なる
            self.tree[2 * i + 1] += v >> 1  # 区間加算クエリなので
            self.tree[2 * i + 2] += v >> 1
            self.lazy[2 * i + 1] += v >> 1
            self.lazy[2 * i + 2] += v >> 1
            #########################################################

            self.lazy[i] = self.lide  # 遅延配列を空に戻す

    def update(self, l, r, x):
        '''
        [l,r)番目の要素をxを適応するクエリを行う O(logN)
        '''
        # 1, 根から区間内においてlazyの値を伝播しておく(self.treeの値が有効になる)
        ids = tuple(_gidx(l, r, self.num))
        #########################################################
        # 区間加算queryのような操作の順序が入れ替え可能な場合これをする必要なないが多くの場合でしたほうがバグが少なく(若干遅くなる)
        # self._lazyprop(*ids)
        #########################################################
        # 2, 区間に対してtree,lazyの値を更新 (treeは根方向に更新するため、lazyはpropで葉方向に更新するため)
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        while l < r:
            #########################################################
            # ** 問題によって値のセットの仕方も変えるべし**
            if r & 1:
                r -= 1
                self.tree[r - 1] += x
                self.lazy[r - 1] += x
            if l & 1:
                self.tree[l - 1] += x
                self.lazy[l - 1] += x
                l += 1
            #########################################################
            x <<= 1  # 区間加算クエリでは上段では倍倍になるはずだよね
            l >>= 1
            r >>= 1
        # 3, 伝播させた区間について下からdataの値を伝播する
        for i in ids:
            i -= 1  # to 0based
            #########################################################
            # 関数の先頭でlazy propを省略した場合は、現在のノードにlazyが反映されていないことがある
            # lazyを省略するならここを慎重に書き換えなければならない
            self.tree[i] = self.func(
                self.tree[2 * i + 1], self.tree[2 * i + 2]) + self.lazy[i]
            #########################################################

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        # 1, 根からにlazyの値を伝播させる
        self._lazyprop(*_gidx(l, r, self.num))
        # 2, 区間[l,r)の最小値を求める
        l += self.num
        r += self.num
        res = self.ide
        while l < r:  # 右から寄りながら結果を結合していくイメージ
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r - 1])
            if l & 1:
                res = self.func(res, self.tree[l - 1])
                l += 1
            l >>= 1
            r >>= 1
        return res


import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def exit(*argv, **kwarg):
    print(*argv, **kwarg)
    sys.exit()


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))
# 受け渡されたすべての要素からsubだけ引く.リストを*をつけて展開しておくこと


def a_int(): return int(read())


def ints(): return list(map(int, read().split()))


def read_col(H):
    '''H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_tuple(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_matrix(H):
    '''H is number of rows'''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter, xor, add
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from functools import reduce
from math import gcd
N, Q = ints()
C = ints()
L, R = read_col(Q)
LRI = [(l - 1, r, i) for i, (l, r) in enu(zip(L, R))]
LRI.sort(key=itemgetter(1))  # 右端でソートしておく
segtree = SegmentTreeForRSQandRAQ(
    [0] * (N + 10))  # l-rまでの種類数を格納(rを広げながら更新していく)
idxprev = defaultdict(lambda: -1)  # 各色の前に出現したidx [prevの位置+1,再出現の位置+1)に区間加算する

ans = [-1] * Q
r_now = 0  # 現在の考慮する位置
for l, r, i in LRI:
    while r_now < r:
        prev = idxprev[C[r_now]]
        segtree.update(prev + 1, r_now + 1, 1)
        idxprev[C[r_now]] = r_now
        r_now += 1
    ans[i] = segtree.query(l, l + 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        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)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(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

#def function():
N, Q = map(int, input().split())
c = list(map(int, input().split()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i] = str(10**12*lrs[i][1] + 10**6* lrs[i][0] + i).zfill(18)

right_edge = [-1]*(N+1)
seg = SegTree([0]*(N+1), segfunc, ide_ele)

lrs = sorted(lrs)
order_num = 0
answer = [0]*(Q)
for i, c_o in enumerate(c):
    if right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
    right_edge[c_o] = i
    seg.update(i, 1)
    
    for j in range(N):
        if order_num >= Q:
            break
        query_now = int(lrs[order_num][:6])
        left_edge = int(lrs[order_num][6:12])
        original_posi = int(lrs[order_num][12:])
        if query_now == i:
            answer[original_posi] = [order_num,seg.query(left_edge,query_now+1)]
            order_num += 1
        else:
            break

for i in range(len(answer)):
    print(answer[i][1])
        
#if __name__ == '__main__':
#    function()

Submission status: Time Limit Exceeded

Solution code:
#参考https://qiita.com/takayg1/items/c811bd07c21923d7ec69

#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele初期値#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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番目の値をxに更新
        k: index(0-index)
        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)のsegfuncしたものを得る ※区間注意
        l: index(0-index)
        r: index(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

#def function():
N, Q = map(int, input().split())
c = list(map(int, input().split()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i] = str(10**12*lrs[i][1] + 10**6* lrs[i][0] + i).zfill(18)

right_edge = [-1]*(N+1)
seg = SegTree([0]*(N+1), segfunc, ide_ele)

lrs = sorted(lrs)
order_num = 0
answer = [0]*(Q)
for i, c_o in enumerate(c):
    if right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
    right_edge[c_o] = i
    seg.update(i, 1)
    
    for j in range(N):
        if order_num >= Q:
            break
        query_now = int(lrs[order_num][:6])
        left_edge = int(lrs[order_num][6:12])
        original_posi = int(lrs[order_num][12:])
        if query_now == i:
            answer[original_posi] = [order_num,seg.query(left_edge,query_now+1)]
            order_num += 1
        else:
            break

for i in range(len(answer)):
    print(answer[i][1])
        
#if __name__ == '__main__':
#    function()

Submission status: Time Limit Exceeded

Solution code:
#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]//700))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict,deque
n,q=map(int, input().split())
c=list(map(int, input().split()))
c=[i-1 for i in c]
lr=[]
for i in range(q):
    l,r=map(int, input().split())
    lr.append((l-1,r-1))
lrsort=sorted(lr, key=lambda x:x[0])
lrsort=sorted(lr, key=lambda x:x[1])
lrsort=deque(lrsort)
#print(lrsort)
goodpos=[-1]*n
isgood=[0]*n
d=defaultdict(int)
s=0
while lrsort:
    l,r=lrsort.popleft()
    for i in range(s,r+1):
        if goodpos[c[i]]!=-1:
            isgood[goodpos[c[i]]]=0
        goodpos[c[i]]=i
        isgood[i]=1
    s=r+1
    d[(l,r)]=sum(isgood[l:])

for l,r in lr:
    print(d[(l,r)])

Submission status: Time Limit Exceeded

Solution code:
#Mo
import sys
input=sys.stdin.readline
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
for i in range(q):
    li,ri=map(int, input().split())
    que.append((li-1,ri-1,i))

que.sort(key
    =lambda x:(x[0]//700,x[1]//700))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for i in range(q):
    l,r,j=que[i]
    while rr<r:
        if cnt[c[rr+1]]==0:
            col+=1
        cnt[c[rr+1]]+=1
        rr+=1
    while rr>r:
        if cnt[c[rr]]==1:
            col-=1
        cnt[c[rr]]-=1
        rr-=1
    while ll>l:
        if cnt[c[ll-1]]==0:
            col+=1
        cnt[c[ll-1]]+=1
        ll-=1
    while ll<l:
        if cnt[c[ll]]==1:
            col-=1
        cnt[c[ll]]-=1
        ll+=1
    ans[j]=col+1
for i in range(q):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
from math import sqrt

input = sys.stdin.buffer.readline
n, q = map(int, input().split())
C = list(map(int, input().split()))
LR = []
bucket_size = int(sqrt(n))
for i in range(q):
    l, r = map(int, input().split())
    LR.append((l // bucket_size, r, l, i))
LR.sort()
# print(LR)

num = 0
count = [0] * (n + 1)


def add_num(idx):
    global num
    c = C[idx]
    if not count[c]:
        num += 1
    count[c] += 1


def del_num(idx):
    global num
    c = C[idx]
    count[c] -= 1
    if not count[c]:
        num -= 1


# 開区間[nl,nr)で考える
nl, nr = 0, 0
ans = [0] * (q)
for i in range(q):
    _, r, l, idx = LR[i]
    l -= 1
    # print(nl, nr, l, r)
    # 区間を広げる時
    while nl > l:
        nl -= 1
        add_num(nl)
    while nr < r:
        add_num(nr)
        nr += 1
    # 区間を狭める時
    while nl < l:
        del_num(nl)
        nl += 1
    while nr > r:
        nr -= 1
        del_num(nr)
    # print("a", num, "idx", idx, "LR", (l, r))
    # print("c", count)
    ans[idx] = num


print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
from collections import defaultdict,deque
n,q=map(int, input().split())
c=list(map(int, input().split()))
c=[i-1 for i in c]
lr=[]
for i in range(q):
    l,r=map(int, input().split())
    lr.append((l-1,r-1))
lrsort=sorted(lr, key=lambda x:x[0])
lrsort=sorted(lr, key=lambda x:x[1])
lrsort=deque(lrsort)
#print(lrsort)
goodball=[-1]*n
d=defaultdict(int)
s=0
while lrsort:
    l,r=lrsort.popleft()
    for i in range(s,r+1):
        goodball[c[i]]=i
    s=r+1
    d[(l,r)]=sum([1 for g in goodball if l<=g])

for l,r in lr:
    print(d[(l,r)])

Submission status: Time Limit Exceeded

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

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

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

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

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

lr = [(i,)+tuple(map(int, input().split())) for i in range(Q)]
lr.sort(key=lambda t: t[1], reverse=True)
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    while idx<Q and lr[idx][1]-1==x:
        i, l, r = lr[idx][0], lr[idx][1]-1, lr[idx][2]-1
        ans.append((i, r-l+1-bit.acc(r+1)))
        idx += 1
    
ans.sort(key=lambda t: t[0])

for ans_i in ans:
    print(ans_i[1])

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    print(*ans)

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    print("\n".join(map(str, ans)))

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
MAX = 1000001


class Query:
    def __init__(self, l, r, idx):
        self.l = l
        self.r = r
        self.idx = idx

    # updating the bit array


def update(idx, val, bit, n):
    while idx <= n:
        bit[idx] += val
        idx += idx & -idx

    # querying the bit array


def query(idx, bit, n):
    summ = 0
    while idx:
        summ += bit[idx]
        idx -= idx & -idx
    return summ


def answeringQueries(arr, n, queries, q):
    # initialising bit array
    bit = [0] * (n + 1)

    # holds the rightmost index of  
    # any number as numbers of a[i] 
    # are less than or equal to 10^6 
    last_visit = [-1] * MAX

    # answer for each query 
    ans = [0] * q

    query_counter = 0
    for i in range(n):

        # If last visit is not -1 update -1 at the 
        # idx equal to last_visit[arr[i]] 
        if last_visit[arr[i]] != -1:
            update(last_visit[arr[i]] + 1, -1, bit, n)

            # Setting last_visit[arr[i]] as i and
        # updating the bit array accordingly 
        last_visit[arr[i]] = i
        update(i + 1, 1, bit, n)

        # If i is equal to r of any query store answer 
        # for that query in ans[] 
        while query_counter < q and queries[query_counter].r == i:
            ans[queries[query_counter].idx] = \
                query(queries[query_counter].r + 1, bit, n) - \
                query(queries[query_counter].l, bit, n)
            query_counter += 1

    # print answer for each query 
    for i in range(q):
        print(ans[i])

    # Driver Code


if __name__ == "__main__":
    N, Q = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]

    n = N
    queries = []
    for i in range(Q):
        l, r = [int(x) for x in input().split()]
        queries.append(Query(l - 1, r - 1, i))
    q = Q

    queries.sort(key=lambda x: x.r)
    answeringQueries(a, n, queries, q)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class BinaryIndexedTree:
    # 1-indexed
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
    
    def add(self, i, x):
        # Accessed by 0-indexed
        i += 1
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    def sum(self, i):
        # [0, i)
        res = 0
        while i:
            res += self.data[i]
            i -= i & -i
        return res
    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        i = 0
        k = 1 << (self.n.bit_length() - 1)
        while 0 < k:
            if i + k <= self.n and self.data[i + k] < w:
                w -= self.data[i + k]
                i += k
            k >>= 1
        return i + 1


def solve():
    N, Q = map(int, rl().split())
    c = list(map(int, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    c = [(0, ci - 1, idx + 1) for idx, ci in enumerate(c)]
    lr = [(1, left, right, idx) for idx, (left, right) in enumerate(lr)]
    query = sorted(c + lr, key=itemgetter(2, 0))
    
    bit = BinaryIndexedTree(N)
    c_to_idx = [-1] * N
    ans = [0] * Q
    for cmd, *q in query:
        if cmd == 0:
            ci, idx = q
            if c_to_idx[ci] != -1:
                bit.add(c_to_idx[ci], -1)
            c_to_idx[ci] = idx - 1
            bit.add(idx - 1, 1)
        else:
            left, right, idx = q
            ans[idx] = bit.sum(right) - bit.sum(left - 1)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import add, itemgetter

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


class SegmentTree:
    def __init__(self, init_value: list, segfunc, ide_ele):
        n = len(init_value)
        self.N0 = 1 << (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.data = [ide_ele] * (2 * self.N0)
        self.segfunc = segfunc
        
        for i, x in enumerate(init_value):
            self.data[i + self.N0 - 1] = x
        for i in range(self.N0 - 2, -1, -1):
            self.data[i] = self.segfunc(self.data[2 * i + 1], self.data[2 * i + 2])
    
    def update(self, k: int, x):
        k += self.N0 - 1
        ################################################################
        self.data[k] = x
        ################################################################
        while k:
            k = (k - 1) // 2
            self.data[k] = self.segfunc(self.data[k * 2 + 1], self.data[k * 2 + 2])
    
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ################################################################
        
        while L < R:
            if L & 1:
                res = self.segfunc(res, self.data[L - 1])
                L += 1
            if R & 1:
                R -= 1
                res = self.segfunc(res, self.data[R - 1])
            L >>= 1
            R >>= 1
        
        ################################################################
        return res


def solve():
    N, Q = map(int, rl().split())
    c = list(map(int, rl().split()))
    lr = [list(map(int, rl().split())) for _ in range(Q)]
    
    c = [(0, ci - 1, idx + 1) for idx, ci in enumerate(c)]
    lr = [(1, left, right, idx) for idx, (left, right) in enumerate(lr)]
    query = sorted(c + lr, key=itemgetter(2, 0))
    
    seg_tree = SegmentTree([0] * N, add, 0)
    c_to_idx = [-1] * N
    ans = [0] * Q
    for cmd, *q in query:
        if cmd == 0:
            ci, idx = q
            if c_to_idx[ci] != -1:
                seg_tree.update(c_to_idx[ci], 0)
            c_to_idx[ci] = idx - 1
            seg_tree.update(idx - 1, 1)
        else:
            left, right, idx = q
            ans[idx] = seg_tree.query(left - 1, right)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()