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
# 遅延セグ木がTLEしたので,BITで...


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (self.n + 1)  # bitは(1based indexっぽい感じなので)

    def init(self, ls):
        assert len(ls) <= self.n
        # lsをbitの配列に入れる
        for i, x in enumerate(ls):  # O(n log n 掛かりそう)
            self.add(i, x)

    def add(self, i, x):
        '''i番目の要素にxを足し込む'''
        i += 1  # 1 based idxに直す
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        '''[i,j)の区間の合計を取得'''
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        '''[,i)の合計を取得'''
        # 半開区間なので i+=1しなくていい
        ret = 0
        while i > 0:
            ret += self.bit[i]
            i -= (i & -i)
        return ret


class RangeAddBIT:  # range add query
    # [l,r)にxを加算する
    # [0,[l,r), i)のとき→bit.sum(i)+(rx-lx) (iによらない)
    # [0,[l,i),r)のとき→bit.sum(i)+(ix-lx)
    # [0,i),[l,r)のとき→bit.sum(i) (iによらない)
    # を加算できれば良い。bit.sum(i)が0だと見立てるとわかりやすいかも？
    # 場合分け2つ目における1項目をbit1,2項目をbit2とする
    def __init__(self, n: int):
        self.n = n
        self.bit1 = BIT(n)  # bit1.sum(i)*iで xiを達成したい部分 imos方的に使う
        self.bit2 = BIT(n)  # bit2.sum(i)で -xlを達成したい部分が手に入る。 r<iで区間加算後の和に相当する

    def add(self, l: int, r: int, x):
        '''[l,r)の要素にxを足し込む'''
        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):
        '''[l,r)の区間の合計を取得'''
        return self._sum(l) - self._sum(r)

    def _sum(self, i: int):
        '''[,i)の合計を取得'''
        return self.bit1._sum(i) * i + self.bit2._sum(i)


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 = RangeAddBIT(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.add(prev + 1, r_now + 1, 1)
        idxprev[C[r_now]] = r_now
        r_now += 1
    ans[i] = -segtree.sum(l, l + 1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def main(N,Q,C,LR):
    data=[0]*(N+1)
    def add(i,x):
        i+=1
        while i<=N:
            data[i]+=x
            i+=i&-i
    def sum(a,b):
        r=0
        i=b
        while i>0:
            r+=data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=data[i]
            i-=i&-i
        return r
    p=[-1]*N
    q=0
    a=[0]*Q
    for i in range(N):
        if p[C[i]-1]>=0:
            add(p[C[i]-1],-1)
        p[C[i]-1]=i
        add(i,1)
        while q<Q and LR[q][2]==i+1:
            a[LR[q][0]]=sum(LR[q][1]-1,LR[q][2])
            q+=1
    return a

import sys
if sys.argv[-1]=='ONLINE_JUDGE':
    from numba import*
    from numba.pycc import CC
    cc=CC('my_module')

    def cc_export(f,signature):
        cc.export(f.__name__,signature)(f)
        return njit(f)

    main=cc_export(main,(i8,i8,i8[:],i8[:,:]))
    cc.compile()
    exit()

N,Q=map(int,input().split())
import numpy as np
C=np.array(input().split(),dtype=np.int64)
LR=sorted([[i]+list(map(int,input().split())) for i in range(Q)],key=lambda x:x[2])
LR=np.array(LR)

from my_module import main
print(*main(N,Q,C,LR),sep='\n')

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())
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]//1000,x[1]))

ll=0;rr=0
cnt=[0 for _ in range(500001)]
ans=[0 for _ in range(500001)]
col=0
cnt[c[0]]=1
for l,r,j in que:
    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
print('\n'.join(map(str,ans[:q])))

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())
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]))

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
print('\n'.join(map(str,ans[:q])))

Submission status: Time Limit Exceeded

Solution code:
#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
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]))

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
print('\n'.join(map(str,ans[:q])))

Submission status: Time Limit Exceeded

Solution code:
#Mo
n,q=map(int, input().split())
*c,=map(int, input().split())
c.append(-1)
que=[]
#cdef int i,j,l,r,ll,rr
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]))

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:
#!/usr/bin/env python3
class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

n, q = map(int, input().split())
c = list(map(int, input().split()))
lr = [list(map(int, input().split())) + [i] for i in range(q)]
lr.sort(key=lambda x:x[1])
BIT = BinaryIndexedTree(n+1)
LastAppeared = [-1] * (n+1)
ans = [0] * q
R = 0
for l, r, i in lr:
    while R < r:
        if LastAppeared[c[R]] != -1:
            BIT.add(LastAppeared[c[R]], -1)
        LastAppeared[c[R]] = R+1
        BIT.add(R+1, 1)
        R += 1

    ans[i] = BIT.sum(r) - BIT.sum(l-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
  n,q,*c=map(int,sys.stdin.buffer.read().split())
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:c[x+x-~n]):
    l,r=c[i+i+n],c[i+i-~n]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s=s+t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
C=list(map(int,input().split()))
LR=sorted([[i]+list(map(int,input().split())) for i in range(Q)],key=lambda x:x[2])
from numba import*
import numpy as np
@jitclass((('N',i8),('data',i8[:])))
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=np.zeros(N+1,dtype=np.int64)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        r=0
        i=b
        while i>0:
            r+=self.data[i]
            i-=i&-i
        i=a
        while i>0:
            r-=self.data[i]
            i-=i&-i
        return r
b=BIT(N)
p=[-1]*N
q=0
a=[0]*Q
for i in range(N):
    if p[C[i]-1]>=0:
        b.add(p[C[i]-1],-1)
    p[C[i]-1]=i
    b.add(i,1)
    while q<Q and LR[q][2]==i+1:
        a[LR[q][0]]=b.sum(LR[q][1]-1,LR[q][2])
        q+=1
print(*a,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
def main():
  n,q,*c=map(int,sys.stdin.buffer.read().split())
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:c[x+x-~n]):
    l,r=c[i+i+n],c[i+i-~n]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s+=t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  (n,q),c,*z=[[*map(int,t.split())]for t in open(0)]
  a=[0]*q
  j,*b=t=[0]*9**6
  for i in sorted(range(q),key=lambda x:z[x][1]):
    l,r=z[i]
    while j<r:
      k=c[j]
      j+=1
      x,y,b[k]=b[k]+1,j+1,j
      while x<=n:
        t[x]+=1
        x=x+(x&-x)
      while y<=n:
        t[y]-=1
        y=y+(y&-y)
    s=0
    while l:
      s+=t[l]
      l=l-(l&-l)
    a[i]=s
  print(' '.join(map(str,a)))
main()

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
C=list(map(int,input().split()))
LR=sorted([[i]+list(map(int,input().split())) for i in range(Q)],key=lambda x:x[2])
class BIT:
    def __init__(self,N):
        self.N=N
        self.data=[0]*(N+1)
    def add(self,i,x):
        i+=1
        while i<=self.N:
            self.data[i]+=x
            i+=i&-i
    def sum(self,a,b):
        if a>0:
            r=self.sum(0,b)-self.sum(0,a)
        else:
            r=0
            i=b
            while i>0:
                r+=self.data[i]
                i-=i&-i
        return r
b=BIT(N)
p=[-1]*N
q=0
a=[0]*Q
for i in range(N):
    if p[C[i]-1]>=0:
        b.add(p[C[i]-1],-1)
    p[C[i]-1]=i
    b.add(i,1)
    while q<Q and LR[q][2]==i+1:
        a[LR[q][0]]=b.sum(LR[q][1]-1,LR[q][2])
        q+=1
print(*a,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# Mo's algorithm
# 行ったり来たりバージョン
import sys
from math import sqrt

input = sys.stdin.buffer.readline

n, q = map(int, input().split())
C = list(map(int, input().split()))
bucket_size = int(sqrt(n))
LR = [[] for _ in range(n // bucket_size + 1)]
lmax = 0
for i in range(q):
    l, r = map(int, input().split())
    LR[l // bucket_size].append((r, l, i))
    lmax = max(lmax, l)

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)
preb = -1
for i in range(lmax // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        l -= 1
        # 区間を広げる時
        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)
        ans[idx] = num


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

Submission status: Time Limit Exceeded

Solution code:
# Mo's algorithm
# 言ったり来たりバージョン
import sys
from math import sqrt

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

# 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)
preb = -1
for i in range(n // bucket_size + 1):
    query = LR[i]
    if not query:
        continue
    query.sort(reverse=(i % 2 == 1))
    for r, l, idx in query:
        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

class segtree:
    x_unit=0 # 単位元
    x_func=sum  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def set_val(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

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 for x in range(n)]
d=defaultdict(int)
s=0
seg=segtree(n)
seg.build(isgood)

while lrsort:
    l,r=lrsort.popleft()
    for i in range(s,r+1):
        if goodpos[c[i]]!=-1:
            seg.set_val(goodpos[c[i]],0)
        goodpos[c[i]]=i
        seg.set_val(i,1)
    s=r+1
    d[(l,r)]=seg.fold(l,r+1)

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

Submission status: Time Limit Exceeded

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

class segtree:
    x_unit=0 # 単位元
    x_func=sum  # 関数
    def __init__(self,n):
        self.n=n
        self.x=[self.x_unit]*(2*n)
    def build(self, seq):
        for i,j in enumerate(seq, self.n):  # n番目からseqをx配列に移していく
            self.x[i] = j
        for i in range(self.n-1, 0, -1):
            self.x[i] = self.x_func([self.x[i*2], self.x[i*2+1]])
    def set_val(self,i,j): # 1点更新
        i += self.n
        self.x[i]=j
        while i>1:
            i//=2 # 更新後、木の上へと登っていくついでに更新
            self.x[i]=self.x_func([self.x[i*2], self.x[i*2+1]])
    def fold(self,l,r): # 区間[l, r)の最小値などを取得 
        l+=self.n
        r+=self.n
        val_l=self.x_unit
        val_r=self.x_unit
        while l<r:
            if l & 1: # lが奇数
                val_l=self.x_func([val_l,self.x[l]])
                l+=1 # 偶数に調節
            if r & 1: # rが奇数
                r-=1 # 開区間なので1個前は偶数番目の要素
                val_r=self.x_func([val_r,self.x[r]])
            l //= 2
            r //= 2
        return self.x_func([val_l,val_r])

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 for x in range(n)]
d=defaultdict(int)
s=0
seg=segtree(n)
seg.build(isgood)

while lrsort:
    l,r=lrsort.popleft()
    for i in range(s,r+1):
        if goodpos[c[i]]!=-1:
            seg.set_val(goodpos[c[i]],0)
        goodpos[c[i]]=i
        seg.set_val(i,1)
    s=r+1
    d[(l,r)]=seg.fold(l,n)

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

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)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        nl += l
        nr += l
        num = 0
        count = [0] * (n + 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
    preb = b


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

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_right
from math import ceil
def input(): return sys.stdin.readline().strip()

class BIT:

    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    1-indexedの配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    isom法を使えば、
        1. aiの値を取得する
        2. 区間[i, j]の全ての数にxを加算する
    もO(logN)で行うことができる
    """

    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            raise ValueError("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i # i $ (-i)でiの最下位ビットのみ立った値を得る
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


def main():
    """
    区間の種類数を答える問題は典型みたい。
    https://hama-du-competitive.hatenablog.com/entry/2016/10/01/001418
    ポイントはクエリをrの昇順に整理しておくこと。
    玉の各種類ごとに、それが最後にどこで出現したかをBITに記録していく。
    """
    N, Q = map(int, input().split())
    C = [0] + list(map(int, input().split()))
    queri = []
    for q in range(Q):
        l, r = map(int, input().split())
        queri.append((r, l, q))
    queri.sort()
    # print("queri={}".format(queri))

    lastAppeared = [0] * (N + 1)  # lastAppeared[x] : 値 x が最後に出現した位置
    r0, l0, _ = queri[0]
    for i, c in enumerate(C):
        if i == 0: continue
        if i > r0: break
        lastAppeared[c] = i
    tree = BIT(N)
    for x in range(1, N + 1):
        if lastAppeared[x] != 0:
            tree.add(lastAppeared[x], 1)

    ans = [0] * Q
    pre_R = r0
    for r, l, q in queri:
        if r > pre_R:
            for i in range(pre_R + 1, r + 1):
                if lastAppeared[C[i]] != 0:
                    tree.add(lastAppeared[C[i]], -1)
                lastAppeared[C[i]] = i
                tree.add(i, 1)
        ans[q] = tree.get(l, r)
        pre_R = r
        # print("q={}, lastAppeared={}, ans={}".format(q, lastAppeared, ans[q]))

    for a in ans: print(a)

if __name__ == "__main__":
    main()

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)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        nl += l
        nr += l
        num = 0
        count = [0] * (n + 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:
from sys import exit

import copy

# import numpy as np
from collections import deque, Counter


N, Q = map(int, input().split())
C = list(map(int, input().split()))
R = [list(map(int, input().split())) for _ in range(Q)]


tmp = Counter([])

q = [copy.deepcopy(tmp)]

for c in C:
    tmp[str(c)] += 1
    q.append(copy.deepcopy(tmp))

for r in R:
    d = q[r[1]] - q[r[0] - 1]
    print(len(d))

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)
preb = -1
for i in range(q):
    b, r, l, idx = LR[i]
    l -= 1
    if preb != b:
        nl, nr = 0, 0
        num = 0
        count = [0] * (n + 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 *

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

que = defaultdict(list)

for i in range(Q):
    l, r = map(int, input().split())
    que[l-1].append((i, r-1))
    
idx = 0
bit = BIT(N)
ans = []

for x in range(N-1, -1, -1):
    for y in ys[x]:
        bit.add(y, 1)
    
    for i, r in que[x]:
        ans.append((i, r-x+1-bit.acc(r+1)))
    
ans.sort(key=lambda t: t[0])

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