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 itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


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


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = [(0, 0, 0) for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries = iter(sorted(queries, key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            add(bit, li, -1)
        last[ci] = i + 1
        add(bit, i + 1, 1)
        while i + 1 == r:
            ans[k] = range_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


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


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) - 1 for i in read().split()]
    queries = iter(sorted([[i] + [int(j) for j in read().split()] for i in range(q)], key=itemgetter(2)))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    k, l, r = next(queries)
    for i in range(n):
        ci = c[i]
        li = last[ci]
        if li > 0:
            add(bit, li, -1)
        last[ci] = i + 1
        add(bit, i + 1, 1)
        while i + 1 == r:
            ans[k] = range_sum(bit, l, r)
            try:
                k, l, r = next(queries)
            except StopIteration:
                break
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


def read():
    return sys.stdin.readline().rstrip()


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


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = [0] * (n + 1)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            if last[ci] > 0:
                add(bit, last[ci], -1)
            last[ci] = ri + 1
            add(bit, ri + 1, 1)
            cr = ri + 1
        ans[i] = range_sum(bit, l, r)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

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

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


def read():
    return sys.stdin.readline().rstrip()


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


def range_sum(arr, a, b):
    s = 0
    i = b
    while i > 0:
        s += arr[i]
        i -= i & -i
    i = a - 1
    while i > 0:
        s -= arr[i]
        i -= i & -i
    return s


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    # bit = BIT(n)
    bit = [0] * (n + 1)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            if last[ci] > 0:
                # bit.add(last[ci], -1)
                add(bit, last[ci], -1)
            last[ci] = ri + 1
            # bit.add(last[ci], 1)
            add(bit, ri + 1, 1)
            cr = ri + 1
        # ans[i] = bit.sum(r) - bit.sum(l - 1)
        ans[i] = range_sum(bit, l, r)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

    def add(self, i, x):
        if not i > 0:
            return
        while i < self.size:
            self.array[i] += x
            i += i & -i

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


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            bit.add(last[ci], -1)
            last[ci] = ri + 1
            bit.add(last[ci], 1)
            cr = ri
        ans[i] = bit.sum(r) - bit.sum(l - 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import sys


class BIT:
    def __init__(self, size: int):
        self.size = size + 1
        self.array = [0] * self.size

    def add(self, i, x):
        if not i > 0:
            return
        while i < self.size:
            self.array[i] += x
            i += i & -i

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


def read():
    return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, read().split())
    c = [int(i) for i in read().split()]
    queries = [() for _ in range(q)]
    for i in range(q):
        l, r = map(int, read().split())
        queries[i] = (i, l, r)
    queries.sort(key=itemgetter(2))
    last = [0] * n
    bit = BIT(n)
    ans = [-1] * q
    cr = 0
    for i, l, r in queries:
        for ri in range(cr, r):
            ci = c[ri] - 1
            bit.add(last[ci], -1)
            last[ci] = ri + 1
            bit.add(last[ci], 1)
            cr = ri
            ans[i] = bit.sum(r) - bit.sum(l - 1)
    print(*ans, sep="\n")


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()
    
    _, q = map(int, input().split())
    c = list(map(int, input().split()))

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

    for i in ans:
        print(i)

main()

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()
    if s!=r+1:
        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
# 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())
c=list(map(int,input().split()))
ques=[]
from collections import defaultdict
ans=defaultdict(int)
for _ in range(q):
    l,r=map(int,input().split())
    ques.append((l,r))

sortques=sorted(ques)
sortques=sorted(sortques, key=lambda x:x[1])

good=BIT(n+1)
goodind=[-1]*n
last=0
for x in range(q):
    l,r=sortques[x]
    for i in range(last, r):
        if goodind[c[i]-1]==-1:
            goodind[c[i]-1]=i
            good.add(i+1, 1)
        else:
            j=goodind[c[i]-1]
            good.add(j+1, -1)
            goodind[c[i]-1]=i
            good.add(i+1, 1)
    ans[(l,r)]=good.get(l-1,r)
    last=r

for i in range(q):
    print(ans[ques[i]])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
# 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())
c=list(map(int,input().split()))
ques=[]
from collections import defaultdict, deque
ans=defaultdict(int)
for _ in range(q):
    l,r=map(int,input().split())
    ques.append((l,r))

sortques=sorted(ques)
sortques=sorted(sortques, key=lambda x:x[1])
sortques=deque(sortques)

good=BIT(n+1)
goodind=[-1]*n
last=0
while sortques:
    l,r=sortques.popleft()
    for i in range(last, r):
        if goodind[c[i]-1]==-1:
            goodind[c[i]-1]=i
            good.add(i+1, 1)
        else:
            j=goodind[c[i]-1]
            good.add(j+1, -1)
            goodind[c[i]-1]=i
            good.add(i+1, 1)
    ans[(l,r)]=good.get(l-1,r)
    last=r

for i in range(q):
    print(ans[ques[i]])

Submission status: Time Limit Exceeded

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

LR = []

for i in range(Q):
    l,r = list(map(int,input().split()))
    LR.append((l-1,r-1,i))

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

class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
        self.N0 = 1
        while self.N0*2 <= self.N:
            self.N0 *= 2

    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break

    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret

    #you can use this function when the BIT has only non-negative values.
    def lower_bound(self, w):
        if w<=0:
            return 0
        x = 0
        k = self.N0
        while k>0:
            if x+k<=self.N:
                if self.bit[x+k-1]<w:
                    w-=self.bit[x+k-1]
                    x+=k
            k//=2
        return x

bit = BIT([0]*N)
ans = [0]*Q
count = 0
last_one = [-1]*N
for l,r,i in LR:
    while count<=r:
        color = c[count]-1
        if last_one[color]==-1:
            last_one[color] = count
            bit.add(last_one[color],1)
        else:
            bit.add(last_one[color],-1)
            last_one[color] = count
            bit.add(last_one[color],1)
        count+=1
    if l==0:
        ans[i] = bit.sum(r)
    else:
        ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))

D_origin = {C[i]:0 for i in range(N)}

D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

ANS = []
for i in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        E_dif = dict(E[r - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[r - 1].items() - E[l - 2].items())
    ans = len(E_dif.values())
    ANS.append(ans)
for i in range(Q):
    print(ANS[i])

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))

D_origin = {}
for i in range(N):
    D_origin.update({C[i]:0})
D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

ANS = []
for i in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        E_dif = dict(E[r - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[r - 1].items() - E[l - 2].items())
    ans = len(E_dif.values())
    ANS.append(ans)
for i in range(Q):
    print(ANS[i])

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D_origin = {}
for i in range(N):
    D_origin.update({C[i]:0})
D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = dict(E[R[i] - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    e_dif = collections.Counter(E_dif)
    values, counts = zip(*e_dif.most_common())
    ans = len(values)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
D = {}
E = [{0:0}] * N
for i in range(N):
    if D.get(C[i], -1) == -1:
        D[C[i]] = 1
        D_other = dict(D)
        E[i] = D_other
    else:
        D[C[i]] += 1
        D_other = dict(D)
        E[i] = D_other

for i in range(Q):
    if L[i] == 1:
        E_dif = E[R[i] - 1]
    else:
        E_dif = dict(E[R[i] - 1].items() - E[L[i] - 2].items())
    ans = len(E_dif.values())
    print(ans)

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

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

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    rl = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        rl[i] = (r, l, i)
    rl.sort()
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for r, l, i in rl:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    for a in ans:
        print(a)
            
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N, Q = map(int, input().split())
    bit = [0] * (N+1)

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

    def sum(x):
        ret = 0
        while x != 0:
            ret += bit[x]
            x -= x & -x
        return ret

    c = list(map(int, input().split()))
    rl = [None] * Q
    for i in range(Q):
        l, r = map(int, input().split())
        rl[i] = (r, l, i)
    rl.sort()
    ans = [None] * Q
    last_idx = [-1] * (N+1)
    j = 0
    for r, l, i in rl:
        while j < r:
            if last_idx[c[j]] == -1:
                last_idx[c[j]] = j
            else:
                add(last_idx[c[j]]+1, -1)
                last_idx[c[j]] = j
            add(j+1, 1)
            j += 1
        ans[i] = sum(r) - sum(l-1)
    print(*ans, sep='\n')
            
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

def sum(x):
    ret = 0
    while x != 0:
        ret += bit[x]
        x -= x & -x
    return ret

N, Q = map(int, input().split())
bit = [0] * (N+1)
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        add(j+1, 1)
        j += 1
    ans[i] = sum(r) - sum(l-1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

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

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

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

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_right

""" Binary Indexed Tree """
class BIT:

    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N+1)

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

    def sum(self, x):
        ret = 0
        while x != 0:
            ret += self.bit[x]
            x -= x & -x
        return ret

    # x < sum(index) となる最小の index を返す
    def upper_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if x < y:
                r = m
            else:
                l = m
        return r

    # x <= sum(index) となる最小の index を返す
    def lower_bound(self, x):
        l, r = -1, self.N
        while l+1 < r:
            m = (l+r)//2
            y = self.sum(m)
            if y < x:
                l = m
            else:
                r = m
        return r

N, Q = map(int, input().split())
c = list(map(int, input().split()))
rl = [None] * Q
for i in range(Q):
    l, r = map(int, input().split())
    rl[i] = (r, l, i)
rl.sort()
bit = BIT(N+1)
ans = [None] * Q
last_idx = [-1] * (N+1)
j = 0
for r, l, i in rl:
    while j < r:
        if last_idx[c[j]] == -1:
            last_idx[c[j]] = j
        else:
            bit.add(last_idx[c[j]]+1, -1)
            last_idx[c[j]] = j
        bit.add(j+1, 1)
        j += 1
    ans[i] = bit.sum(r) - bit.sum(l-1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
input_ = input()
input_ = input_.split(' ')
N = int(input_[0])
Q = int(input_[1])

input_ = input()
input_ = input_.split(' ')
c_ = [0] * N
for i in range(N):
    c_[i] = int(input_[i])
lr_list = [[]] * Q
for i in range(Q):
    input_ = input()
    input_ = input_.split(' ')
    lr_list[i] = [int(input_[0]), int(input_[1])]

for i in range(Q):
    l = lr_list[i][0] - 1
    r = lr_list[i][1] - 1
    seen = []
    for j in range(l, r + 1):
        data = c_[j]
        if data not in seen:
            seen.append(data)
    print(len(seen))

Submission status: Time Limit Exceeded

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

    def add(self, i, x):
        """Add x to a[i]."""
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        """Sum a[1]~a[i]."""
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        """Sum a[i]~a[j]."""
        return self.sumup(j) - self.sumup(i - 1)


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

ans = [0] * Q
last_appeared = [0] * (N + 1)
bit = BIT(N + 1)
rm = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(rm + 1, r + 1):
        if last_appeared[C[j - 1]] > 0:
            bit.add(last_appeared[C[j - 1]], -1)
        last_appeared[C[j - 1]] = j
        bit.add(j, 1)

    rm = r
    ans[i] = bit.query(l, r)

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

Submission status: Time Limit Exceeded

Solution code:

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

    def add(self, i, x):
        # Add x to a[i]
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        # Sum a[1]~a[i]
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        # Sum a[i]~a[j]
        return self.sumup(j) - self.sumup(i - 1)


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

ans = [0] * Q
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(k + 1, r + 1):
        if last[C[j - 1]] > 0:
            bit.add(last[C[j - 1]], -1)

        bit.add(j, 1)
        last[C[j - 1]] = j

    k = r
    ans[i] = bit.query(l, r)

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

Submission status: Time Limit Exceeded

Solution code:

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

    def add(self, i, x):
        # Add x to a[i]
        while i < self.size:
            self.bit[i] += x
            i += i & -i

    def sumup(self, i):
        # Sum a[1]~a[i]
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & -i
        return res

    def query(self, i, j):
        # Sum a[i]~a[j]
        return self.sumup(j) - self.sumup(i - 1)


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

ans = [0] * Q
bit = BIT(N + 1)
last = [0] * (N + 1)
k = 0
for i, (l, r) in sorted(enumerate(X), key=lambda x: x[1][1]):
    for j in range(k + 1, r + 1):
        if last[C[j - 1]] > 0:
            bit.add(last[C[j - 1]], -1)

        bit.add(j, 1)
        last[C[j - 1]] = j

    k = r

    # Answer query
    ans[i] = bit.query(l, r)

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

Submission status: Time Limit Exceeded

Solution code:
import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * Q
R = [0] * Q
for i in range(Q):
    l,r = map(int, input().split())
    L[i] = l
    R[i] = r
for j in range(Q):
    C_after = C[L[j] - 1:R[j]]
    D = collections.Counter(C_after)
    print(len(D))

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

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())
  lc = []
  for i in range(l-1,r):
    lc.append(C[i])
  s = set(lc)
  print(len(s))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
unit = int(n**0.5)
n_unit = (n+unit-1)//unit
c = list(map(int, input().split()))
lst = []
for i in range(q):
    li, ri = map(int, input().split())
    li -= 1; ri -= 1
    left_unit = li // unit
    lst.append([li, ri, i, -1, left_unit])
lst.sort(key=lambda x: x[1])
lst.sort(key=lambda x: x[4])

dic_lst = [{} for i in range(n_unit)]
for i in range(n):
    idx = i // unit
    if c[i] in dic_lst[idx]:
        dic_lst[idx][c[i]] += 1
    else:
        dic_lst[idx][c[i]] = 1

left_unit = -1
right_unit = -1
for i in range(q):
    li, ri = lst[i][0], lst[i][1]
    if li//unit != left_unit:
        temp = {}
        left_unit = li // unit
        right_unit = ri // unit
        for j in range(left_unit+1, right_unit):
            for key, value in dic_lst[j].items():
                if key in temp:
                    temp[key] += value
                else:
                    temp[key] = value

        now = temp.copy()
        for j in range(li, min((left_unit+1)*unit, ri+1)):
            if c[j] in now:
                now[c[j]] += 1
            else:
                now[c[j]] = 1
        for j in range(max((right_unit)*unit, li), ri+1):
            if c[j] in now:
                now[c[j]] += 1
            else:
                now[c[j]] = 1

        lst[i][3] = len(now)
    else:
        for j in range(max(right_unit, left_unit+1), ri//unit):
            for key, value in dic_lst[j].items():
                if key in temp:
                    temp[key] += value
                else:
                    temp[key] = value

        now = temp.copy()
        for j in range(li, min((left_unit+1)*unit, ri+1)):
            if c[j] in now:
                now[c[j]] += 1
            else:
                now[c[j]] = 1
        for j in range(max((right_unit)*unit, li), ri+1):
            if c[j] in now:
                now[c[j]] += 1
            else:
                now[c[j]] = 1

        lst[i][3] = len(now)

lst.sort(key=lambda x: x[2])
for i in range(q):
    print(lst[i][3])