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:
class BinaryIndexedTree(object):
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)

    def bit_add(self, index, num):
        while (index <= self.N):
            self.bit[index] += num
            index += index & -index
        return

    def bit_sum(self,index):
        result = 0
        while (index > 0):
            result += self.bit[index]
            index -= index & -index
        return result

def main():
    N, Q = list(map(int, input().split()))
    c = list(map(int, input().split()))
    query = [tuple(list(map(int, input().split())) + [i]) for i in range(Q)]
    query_result = [0 for i in range(Q)]
    collar_pos = [-1] * (N + 1)
    bit = BinaryIndexedTree(N)

    sorted_query = sorted(query, key=lambda query: query[1])

    index = 1
    for query in sorted_query:
        while (index <= query[1]):
            # update BIT
            if (collar_pos[c[index-1]] != -1):
                bit.bit_add(collar_pos[c[index-1]], -1)
            bit.bit_add(index, 1)
            # update collar_pos
            collar_pos[c[index-1]] = index
            index += 1
        query_result[query[2]] = bit.bit_sum(query[1]) - bit.bit_sum(query[0]-1)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(Q)]
for i in range(Q):
    start=A[i][0]-1
    last=A[i][1]
    print(len(set(c[start:last])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
c = list(map(int, input().split()))
A = [list(map(int, input().split())) for i in range(Q)]
for i in range(Q):
    
    A[i][0] -=1
    
for i in range(Q):
    start=A[i][0]
    last=A[i][1]
    print(len(set(c[start:last])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
num_C = len(set(C))
for q in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    #print(len(set(C[l:r+1])))
    ans = []
    for c in C[l:r+1]:
        if c not in ans:
            ans.append(c)
        if r - l + 1 >= num_C and len(ans) == num_C:
            break
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
C = list(map(int, input().split()))
for q in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    print(len(set(C[l:r+1])))

Submission status: Time Limit Exceeded

Solution code:
N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
query = [tuple(list(map(int, input().split())) + [i]) for i in range(Q)]
query_result = [0 for i in range(Q)]

collar_pos = [-1] * (N + 1)
bit = [0] * (N + 1)

def bit_add(index, num):
    while (index <= N):
        bit[index] += num
        index += index & -index
    return

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

sorted_query = sorted(query, key=lambda query: query[1])

index = 1
for query in sorted_query:
    while (index <= query[1]):
        # update BIT
        if (collar_pos[c[index-1]] != -1):
            bit_add(collar_pos[c[index-1]], -1)
        bit_add(index, 1)
        # update collar_pos
        collar_pos[c[index-1]] = index
        index += 1
    query_result[query[2]] = bit_sum(query[1]) - bit_sum(query[0]-1)

for q in query_result:
    print(q)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

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

C = [int(y) for y in input().split()]

Left = [] 

lis = [0] * (N + 1)

for i in C:
    lis[i] += 1
    Left.append(lis.copy())

lis = [0] * (N + 1)

for i in range(Q):
    index = -1
    ans = 0
    l,r = map(int,input().split())
    for a,c in zip(Left[l-1],Left[r-1]):
        index += 1
        on = c-a
        if index == C[l-1]:
            on += 1
        if on != 0:
            ans += 1
    print("{}".format(ans))

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8

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

C = [int(y) for y in input().split()]

Left = [] 
Right = []

lis = [0] * (N + 1)

for i in C:
    lis[i] += 1
    Left.append(lis.copy())

lis = [0] * (N + 1)

for i in C[::-1]:
    lis[i] += 1
    Right.append(lis.copy())

Right = Right[::-1]

for i in range(Q):
    index = -1
    ans = 0
    l,r = map(int,input().split())
    for a,b,c,d in zip(Left[l-1],Right[l-1],Left[r-1],Right[r-1]):
        index += 1
        on = c-a
        off = b-d
        if index == C[l-1]:
            on += 1
        if index == C[r-1]:
            off += 1
        if on * off != 0:
            ans += 1
    print("{}".format(ans))

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()))
prn = lambda x: print(*x, sep='\n')

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_


def solve():
    n, q = nm()
    c = nl()
    m = 500010
    m2 = m * m
    g = [0]*q
    for i in range(q):
        l, r = nm()
        g[i] = ((r-1) << 40) + ((l-1) << 20) + i
    mask = (1 << 20) - 1
    g.sort()
    ans = [0] * q
    b = BIT(m)
    last = [n + 5]*(n+1)
    cr = -1
    for r in g:
        i = r & mask
        r >>= 20
        l = r & mask
        r >>= 20
        while cr < r:
            cr += 1
            b.bitadd(last[c[cr]], -1)
            last[c[cr]] = cr
            b.bitadd(cr, 1)
        ans[i] = b.bitsum(l, r+1)
    prn(ans)
    return

solve()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        return x + y

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1] = init[i]
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
    
    
    def update(self,k,x):
        k += self.num-1
        self.seg[k] += x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p > 1:
            if p & 1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p //= 2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res


n,k = m()

Seg = SegmentTree(n,[0 for i in range(n)],0)
a = l()

data = []
for i in range(k):
    po = l()
    po.append(i+1)
    data.append(po)

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

where = [-1 for i in range(n)]
ans = []
left = -1
for i in range(k):
    aaa = data[i]
    aaa[0] -= 1
    aaa[1] -= 1
    if aaa[1] > left:
        for j in range(left+1,aaa[1]+1):
            popopo = a[j]-1
            if where[popopo] != -1:
                Seg.update(where[popopo],-1)
            Seg.update(j,1)
            where[popopo] = j
        left = aaa[1]
    ans.append([aaa[2],Seg.query(aaa[0],aaa[1]+1)])



ans.sort(key = lambda x:x[0])

for i in range(k):
    print(ans[i][1])

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def solver(n, q, balllist, queries):
    sums = {k: [0]*(n+1) for k in Counter(balllist).keys()}
    for i, ci in enumerate(c):
        for k, v in sums.items():
            sums[k][i+1] = v[i] + (ci == k)
    for l, r in queries:
        yield sum(v[l-1] < v[r] for v in sums.values())


if __name__ == "__main__":
    n, q = map(int, input().split())
    c = list(map(int, input().split()))
    lr = [list(map(int, input().split())) for _ in range(q)]
    for s in solver(n, q, c, lr):
        print(s)

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 defaultdict
import sys
# Binary Indexed Tree (Fenwick Tree)
class BIT():
    def __init__(self, n):
        '''
        n = 要素数
        要素の添字iは 0 <= i < n となる
        '''
        self.n = n
        self.bit = [0] * (n + 1)

    def add(self, i, value):
        '''i番目の要素にvalueを加算する O(logN)'''
        i = i + 1
        while i <= self.n:
            self.bit[i] += value
            i += i & -i

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

    def sum(self, l, r):
        '''区間[l, r)の和を求める O(logN)'''
        return self._sum(r) - self._sum(l)


input = sys.stdin.readline
N, Q = map(int, input().split())
C = list(map(int, input().split()))
LR = [tuple(map(int, input().split())) for _ in range(Q)]
query = [[] for _ in range(N)]
for i, (l, r) in enumerate(LR):
    query[l-1].append((i, r-1))

hist = defaultdict(lambda: -1)
nx = [-1] * N
for i in range(N-1, -1, -1):
    nx[i] = hist[C[i]]
    hist[C[i]] = i

bit = BIT(N)
ans = [None]*Q
for l in range(N-1,-1,-1):
    if nx[l] != -1:
        bit.add(nx[l],-1)
    for i,r in query[l]:
        ans[i] = (r-l+1) + bit.sum(l,r+1)

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

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, Q = map(int, input().split())
lis = input().split()
for i in range(0, Q):
    s, e = map(int, input().split())
    print(len(Counter(lis[s-1:e]).keys()))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N, Q = map(int, input().split())
lis = input().split()
for i in range(0, Q):
    s, e = map(int, input().split())
    temp = lis[s-1:e]
    print(len(Counter(temp).keys()))

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

class BIT:
    def __init__(self, size):
        self.size = size
        self.A = [0] * (size+1)
    def read(self, i):
        s = 0
        while i > 0: s += self.A[i]; i -= i&-i;
        return s
    def add(self, i, k):
        while i <= self.size: self.A[i] += k; i += (i&-i);

n, q = map(int, input().split())
cs = list(map(int, input().split()))
last_seen = [n+1]*(n+2)
queries = [list(map(int, input().split())) + [-999] for i in range(q)]
queriesAt = [[] for i in range(n+1)]
for q in queries:
    queriesAt[q[0]].append(q)

answers = {}
bit = BIT(n+3)
for l in range(n, 0, -1):
    bit.add(last_seen[cs[l-1]], -1)
    bit.add(l, 1)
    last_seen[cs[l-1]]=l
    for q in queriesAt[l]:
        q[2] = bit.read(q[1])
for q in queries: print(q[2])

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

class BIT:
    def __init__(self, size):
        self.size = size
        self.A = [0] * (size+1)
    def read(self, i):
        s = 0
        while i > 0: s += self.A[i]; i -= i&-i;
        return s
    def add(self, i, k):
        while i <= self.size: self.A[i] += k; i += (i&-i);

n, q = map(int, input().split())
cs = list(map(int, input().split()))
last_seen = [n+1]*(n+2)
queries = [list(map(int, input().split())) + [-999] for i in range(q)]
from collections import defaultdict
queriesAt = defaultdict(list)
for q in queries:
    queriesAt[q[0]].append(q)

answers = {}
bit = BIT(n+3)
for l in range(n, 0, -1):
    bit.add(last_seen[cs[l-1]], -1)
    bit.add(l, 1)
    last_seen[cs[l-1]]=l
    for q in queriesAt.get(l, []):
        q[2] = bit.read(q[1])
for q in queries: print(q[2])

Submission status: Time Limit Exceeded

Solution code:
from itertools import *

class BIT:
    def __init__(self, size):
        self.size = size
        self.A = [0] * (size+1)
    def read(self, i):
        s = 0
        while i > 0: s += self.A[i]; i -= i&-i;
        return s
    def add(self, i, k):
        while i <= self.size: self.A[i] += k; i += (i&-i);

n, q = map(int, input().split())
cs = list(map(int, input().split()))
last_seen = [n+1]*(n+2)
queries = [tuple(map(int, input().split())) for i in range(q)]
answers = {}
bit = BIT(n+3)
for l in range(n, 0, -1):
    bit.add(last_seen[cs[l-1]], -1)
    bit.add(l, 1)
    last_seen[cs[l-1]]=l
    for (ql, qr) in queries:
        if ql==l:
            answers[(ql, qr)] = bit.read(qr)
for q in queries: print(answers[q])

Submission status: Time Limit Exceeded

Solution code:

import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

class BIT:
    def __init__(self, n=0):
        self.n = n
        self.d = [0] * (n+1)
    
    def add(self, i, x=1):
        i = int(i+1) # index begin 1
        while i <= self.n:
            self.d[i] += x
            i += i&-i # add LSB
    
    def sum(self, i=None):
        x = 0
        i = int( i+1 if not (i is None) else self.n )
        while i > 0:
            x += self.d[i]
            i -= i&-i # sub LSB
        return x

n, q = list(map(int, input().split()))
c = list(map(int, input().split()))
dprint("n, q =", n, q)
dprint("c =", c)

# check colors pair index (s,t)
st = [0] * (n+1)
col_last = [0] * (n+1)
for i in range(n):
    t = i + 1
    col = c[i]
    s = col_last[col]
    if s > 0:
        st[s] = t
    col_last[col] = t
dprint("st =", st)

# input querys (l,r)
lr = [None] * n
qs = list()
sorted_qs = list()
for i in range(q):
    l, r = list(map(int, input().split()))
    qs.append((i,l,r)) 
sorted_qs = sorted(qs, key=lambda q: q[1], reverse=True)
dprint("qs =", qs)
dprint("sorted_qs =", sorted_qs)

i_qs = 0
x = n
d = BIT(n+1)
qs_ans = [0] * len(qs)
for i_qs in range(len(sorted_qs)):
    i, l, r = sorted_qs[i_qs]
    dprint("i, l, r", i, l, r)
    while (x >= l):
        if st[x] > 0:
            d.add(st[x])
            dprint("add x(s), t =", x, st[x])
        x -= 1
    qs_ans[i] = (r-l+1)-d.sum(r)

for ans in qs_ans:
    print(ans)

Submission status: Time Limit Exceeded

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

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

# 1-indexed
left_index_dict = {}
d = defaultdict(int)

for i, ci in enumerate(c):
    index = d[ci]
    if index in left_index_dict:
        left_index_dict[index].append(i+1)
    else:
        left_index_dict[index] = [i+1]
    d[ci] = i + 1

lr.sort()

index = list(left_index_dict.keys())
index.sort()
i = 0

N = n
bit = [0] * (N+1)

def sum(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

def add(i, x):
    while i <= N:
        bit[i] += x
        i += i & -i

ans = [0] * q

for l, r, _i in lr:
    while i < len(index) and index[i] < l:
        for j in left_index_dict[index[i]]:
            add(j, 1)
        i += 1
    ans[_i] = sum(r) - sum(l-1)

for ansi in ans:
    print(ansi)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

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

c_d = [0] * n
col_i = [-1] * n
for i in range(n):
    col = c[i] - 1
    c_d[i] = col_i[col]
    col_i[col] = i

for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    ans = r - l + 1
    for j in range(l, r+1):
        if (l <= c_d[j]):
            ans -= 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def bit_add(arr, n, i, x):
    while i <= n:
        arr[i] += x
        i += i & -i

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

n, q = map(int, input().split())
color = [int(i) for i in input().split()]
query = []
rli = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    query.append((l, r))
    rli[i] = (r << 40) + (l << 20) + i
rli.sort()
mask = (1 << 20) - 1
bn = n + 2
bit = [0] * (bn + 1)
ans = [0] * q
appeared = [-1] * (n + 1)
p = 0

for j in range(q):
    k = rli[j]
    r = k >> 40
    l = (k >> 20) & mask
    i = k & mask
    while p < r:
        c = color[p]
        before_appeared = appeared[c]
        if before_appeared != -1:
            bit_add(bit, bn, before_appeared + 2, -1)
        bit_add(bit, bn, p + 2, 1)
        appeared[c] = p
        p += 1
    ans[i] = bit_sum(bit, r + 1) - bit_sum(bit, l)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import time
sys.setrecursionlimit(int(1e6))
if False:
    dprint = print
else:
    def dprint(*args):
        pass

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

c_d = [0] * n
col_i = [-1] * n
for i in range(n):
    col = c[i] - 1
    c_d[i] = col_i[col]
    col_i[col] = i

for i in range(q):
    l, r = list(map(int, input().split()))
    l -= 1
    r -= 1
    dup = 0
    for j in range(l, r+1):
        if (l <= c_d[j]):
            dup += 1
    ans = r - l + 1 - dup
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted((r, i) for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i > 0:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, i in W:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
LR = tuple(tuple(map(int, input().split())) for _ in range(q))
W = sorted((r, i) for i, (l, r) in enumerate(LR))
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, i in W:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  l = LR[i][0]
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
C = [0] + list(map(int, input().split()))
D = [-1]*(n+1)
A = [0]*q
RL = []
for i in range(q):
  l, r = map(int, input().split())
  RL.append((r, l, i))
RL.sort()
B = [0]*(1<<n.bit_length())
def add(i, a):
  while i <= n:
    B[i] += a
    i += i & -i
def acc(i):
  res = 0
  while i:
    res += B[i]
    i -= i & -i
  return res
temp = 1
for r, l, i in RL:
  while temp <= r:
    c = C[temp]
    add(temp, 1)
    if D[c] != -1:
      add(D[c], -1)
    D[c] = temp
    temp += 1
  A[i] = acc(r) - acc(l-1)
print(*A, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import math

N, Q = list(map(int, input().split()))
c = list(map(int, input().split()))
l = []
r = []

for i in range(Q):
    li, ri = list(map(int, input().split()))
    l.append(li)
    r.append(ri)

for i in range(Q):
    print(len(set(c[l[i]-1:r[i]])))

Submission status: Time Limit Exceeded

Solution code:
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
            #print(i)
    '''
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)
    '''

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

query = []

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

query.sort(key = lambda x:x[2])

###
#print(query)
###

ans = [0]*Q
place = [-1]*(N+1)###各色のいい玉がどこにあるか、なければ-1
next_query = 0

bit = BIT(N)

###
#print(bit)
###

for i in range(N):

    bit.add(i+1,1)

    if place[c[i]] != -1:
        bit.add(place[c[i]]+1,-1)

    place[c[i]] = i

    #print(i,bit.data,place)

    while next_query < len(query) and query[next_query][2] == i+1:
        ###
        #print(query[next_query])
        ###
        j,l,r = query[next_query]
        ans[j] = bit.sum(r)-bit.sum(l-1)###l,rは入力時のまま(1-indexed)であることに注意
        next_query += 1
        ###
        #print(i,ans)
        ###
        

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

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self,n,li):
    self.n = n
    self.el = [0] + li
    self.data = [0]*(n+1)
    for i in range(1,n+1):
      self.data[i] = sum(self.el[i+1-(i&-i):i+1])
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self,i,x):
    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-1)
n,q = map(int,input().split())
c = list(map(int,input().split()))
c = [0] + c
a = [0 for _ in range(n+1)]
b = BIT(n,a)
qs = []
ans = [0 for _ in range(q)]
qsa = qs.append
for i in range(q):
  l,r = map(int,input().split())
  qsa((i,l,r))
qs.sort(key=lambda x:x[2])
i = 1
j = 0
while i <= n:
  if a[c[i]] > 0:
    b.add(a[c[i]],-1)
    b.add(i,1)
    a[c[i]] = i
  else:
    b.add(i,1)
    a[c[i]] = i
  while (j < q) and (qs[j][2] == i):
    y = b.get(qs[j][1],i)
    ans[qs[j][0]] = y
    j += 1
  if j >= q:
    break
  i += 1
for ansi in ans:
  print(ansi)

Submission status: Time Limit Exceeded

Solution code:
class BIT:
  def __init__(self,n,li):
    self.n = n
    self.el = [0] + li
    self.data = [0]*(n+1)
    for i in range(1,n+1):
      self.data[i] = sum(self.el[i+1-(i&-i):i+1])
  def sum(self,i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self,i,x):
    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-1)
n,q = map(int,input().split())
c = list(map(int,input().split()))
c = [0] + c
a = [0 for _ in range(n+1)]
b = BIT(n,a)
qs = []
ans = []
ansa = ans.append
qsa = qs.append
for i in range(q):
  l,r = map(int,input().split())
  qsa((i,l,r))
qs.sort(key=lambda x:x[2])
i = 1
j = 0
while i <= n:
  if a[c[i]] > 0:
    b.add(a[c[i]],-1)
    b.add(i,1)
    a[c[i]] = i
  else:
    b.add(i,1)
    a[c[i]] = i
  while (j < q) and (qs[j][2] == i):
    y = b.get(qs[j][1],i)
    ansa((qs[j][0],y))
    j += 1
  if j >= q:
    break
  i += 1
ans.sort(key = lambda x:x[0])
for i in range(q):
  print(ans[i][1])

Submission status: Time Limit Exceeded

Solution code:
# Binary Indexed Tree (Fenwick Tree)
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 = map(int, input().split())
ccc = list(map(int, input().split()))
lri = []
for i in range(Q):
    l, r = map(int, input().split())
    lri.append([l, r, i])
lri.sort(key=lambda x:x[1])
color = [-1] * (N + 1)
bit = BIT(N + 1)
now = 0
ans = []
for l, r, i in lri:
    while now != r:
        now += 1
        if color[ccc[now - 1]] == -1:
            bit.add(now, 1)
            color[ccc[now - 1]] = now
        else:
            bit.add(color[ccc[now - 1]], -1)
            bit.add(now,1)
            color[ccc[now - 1]] = now
    if r == l:
        ans.append([i, bit.get(l)])
    else:
        ans.append([i, bit.get(l - 1, r)])
ans.sort()
for i, 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 sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr = []
for i in range(q):
    l, r = map(int, input().split())
    lr.append([l, r, i])
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

import sys
input = sys.stdin.buffer.readline

n, q = map(int, input().split())
clst = 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 = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

n, q = map(int, input().split())
clst = list(map(int, input().split()))
lr_1 = [list(map(int, input().split())) + [i] for i in range(q)]
lr = lr_1.copy()
lr.sort(key=lambda x:x[1])
bit = Bit(n)
pos = 0
last = [-1 for _ in range(n)]
ans = []
for i, c in enumerate(clst):
    bit.add(i + 1, 1)
    if last[c - 1] != -1:
        bit.add(last[c - 1] + 1, -1)
    last[c - 1] = i
    while lr[pos][1] == i + 1:
        l = lr[pos][0]
        r = lr[pos][1]
        ans.append([bit.sum(r) - bit.sum(l - 1), lr[pos][2]])
        pos += 1
        if pos == q:
            break
    if pos == q:
        break
ans.sort(key=lambda x:x[1])
for num, _ in ans:
    print(num)