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 collections import deque
N,Q=map(int, input().split())

#重複分を引く

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])
    
    # k: index , x: value
    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])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        que.append((state[c-1],i))
        state[c-1]=i

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=sorted(query, key=lambda x: -x[1])

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q



for i in range(len(que)):
    while query and query[-1][1]<que[i][1]:
        q=query.pop()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)

    now=que[i]
    l, r=now  # index
    A[l]+=1
    seg.update(l, A[l])

    while query and query[-1][1]==r:
        q=query.pop()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))

while query:
    q=query.pop()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

#重複分を引く

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])
    
    # k: index , x: value
    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])
    
    # rightは開区間  l<=x<r
    def query(self, left: int, right: int):
        L = left + self.N0
        R = right + self.N0
        res = self.ide_ele
        ##########################
        a, b = [], []
        while L < R:
            if L & 1:
                a.append(L - 1)
                L += 1
            if R & 1:
                R -= 1
                b.append(R - 1)
            L >>= 1
            R >>= 1
        for i in a + b[::-1]:
            res = self.segfunc(res, self.data[i])
        ##########################
        return res


C=list(map(int, input().split()))
state=[-1]*N
que=[]
for i in range(N):
    c=C[i]
    if state[c-1]==-1:
        state[c-1]=i
    else:
        que.append((state[c-1],i))
        state[c-1]=i

que=sorted(que, key=lambda x: x[1])
        
query=[]
for i in range(Q):
    l, r=map(int, input().split())
    query.append((l-1,r-1,i))
query=deque(sorted(query, key=lambda x: x[1]))

A=[0]*(N+1)
def add(a,b):
    return a+b
seg=SegmentTree(A,add,0)
ans=[0]*Q



for i in range(len(que)):
    while query and query[0][1]<que[i][1]:
        q=query.popleft()
        l,r,j=q
        ans[j]=r-l+1-seg.query(l,r+1)

    now=que[i]
    l, r=now  # index
    A[l]+=1
    seg.update(l, A[l])

    while query and query[0][1]==r:
        q=query.popleft()
        lq,rq,j=q
        
        ans[j]=rq-lq+1-seg.query(lq,rq+1)
        #print(lq, rq, seg.query(lq,rq+1))

while query:
    q=query.popleft()
    lq,rq,j=q     
    ans[j]=rq-lq+1-seg.query(lq,rq+1)
    #print(lq, rq, seg.query(lq,rq+1))

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from math import log2,ceil
import sys
input = sys.stdin.buffer.readline

num_factor,num_query = map(int,input().split())
C = list(map(int,input().split()))
LR = [list(map(int,input().split())) for _ in range(num_query)]

length = 2*2**ceil(log2(num_factor)) - 1
tree = [set([])]*length
Ans = []

def update(index,value):#0-indexed
    index += length // 2
    tree[index] = value
    while index > 0:
        index = (index - 1) // 2
        tree[index] = tree[index*2 + 1] | tree[index*2 + 2]
    return

def query(left: int, right: int , node : int, node_left :int, node_right :int)->int:#[left, right]
    if node_right < left or right < node_left:
        return set([])
    elif left <= node_left and node_right <= right:
        return tree[node]
    tmp1 = query(left , right , node*2 + 1, node_left, (node_right + node_left) // 2)
    tmp2 = query(left , right , node*2 + 2, (node_right + node_left) // 2 + 1, node_right )
    return tmp1 | tmp2


# def main():
#     for _ in range(num_query):
#         com,x,y = map(int,input().split())
#         if com:
#             Ans.append(query(x,y,0,0,length // 2))
#         else:
#             update(x,y)
#     print(*Ans, sep ="\n")
#     return



def main():
    for i in range(num_factor):
        c = C[i]
        update(i,{c})
    Ans = []
    for l,r in LR:
        Ans.append(len(query(l - 1 ,r - 1,0,0,length // 2)))
    print(*Ans ,sep="\n")
    return

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, Q = map(int, readline().split())
C = list(map(int,readline().split()))
ans = []
for i in range(Q):
    l,r = map(int,readline().split())
    a = C[l-1:r]
    ans.append(len(set(a)))
print('\n'.join(str(i) for i in ans))

Submission status: Time Limit Exceeded

Solution code:
# でつoO(YOU PLAY WITH THE CARDS YOU'RE DEALT..)
import sys
def main(N, Q, C, LR):
    st = SegmentTree(f=lambda x, y: x | y, initial_values=[1 << (c - 1) for c in C])
    for l, r in LR:
        print(popcount(st.query(l - 1, r)))

def popcount(x):
    x = (x & 0x5555555555555555) + (x >> 1 & 0x5555555555555555)
    x = (x & 0x3333333333333333) + (x >> 2 & 0x3333333333333333)
    x = x + (x >> 4) & 0x0f0f0f0f0f0f0f0f
    x += x >> 8
    x += x >> 16
    x += x >> 32
    return x & 0x7f

class SegmentTree:
    def __init__(self, n=None, f=max, identity_factory=int, initial_values=None):
        assert(n or initial_values)
        size = n if n else len(initial_values)
        d = [identity_factory() for _ in range(2 * size + 1)]
        self.__n, self.__d, self.__f, self.__e = size, d, f, identity_factory
        if initial_values:
            for i, v in enumerate(initial_values): d[size + i] = v
            for i in range(size - 1, 0, -1): d[i] = f(d[i << 1], d[i << 1 | 1])

    def get_val(self, index):
        return self.__d[index + self.__n]

    def set_val(self, index, new_value):
        i, d, f = index + self.__n, self.__d, self.__f
        if d[i] == new_value: return
        d[i] = new_value
        while i:
            i = i >> 1
            d[i] = f(d[i << 1], d[i << 1 | 1])

    def modify(self, index, value):
        self.set_val(index, self.__f(self.__d[index + self.__n], value))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__e()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__d, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l + 1
            if r & 1: ans, r = f(d[r - 1], ans), r - 1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(Q)]
    main(N, Q, C, LR)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


class BinaryIndexTree:  # 1-indexed
    def __init__(self, N):
        """
        INPUT
        N [int] -> 全部0で初期化
        N [list] -> そのまま初期化
        """
        if isinstance(N, int):
            self.N = N
            self.depth = N.bit_length()
            self.tree = [0] * (N + 1)
            self.elem = [0] * (N + 1)
        elif isinstance(N, list):
            self.N = len(N)
            self.depth = self.N.bit_length()
            self.tree = [0] + N
            self.elem = [0] + N
            self._init()
        else:
            raise "INVALID INPUT: input must be int or list"

    def _init(self):
        size = self.N
        for i in range(1, self.N):
            if i + (i & -i) > size:
                continue
            self.tree[i + (i & -i)] += self.tree[i]

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

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

    def lower_bound(self, val):
        if val <= 0:
            return 0
        i = 0
        k = 1 << self.depth
        while k:
            if i + k <= self.N and self.tree[i + k] < val:
                val -= self.tree[i + k]
                i += k
            k >>= 1
        return i + 1


N, Q = map(int, input().split())
U = 5 * 10 ** 5 + 10

C = tuple(map(int, input().split()))
LR = []
for i in range(Q):
    l, r = map(int, input().split())
    LR.append((r, l, i))
LR.sort()

ans = [-1] * Q
pos = 0
bit = BinaryIndexTree(N + 5)
seen = [-1] * U
for i, c in enumerate(C, 1):
    if seen[c] != -1:
        bit.add(seen[c], -1)
    bit.add(i, 1)
    seen[c] = i
    while pos < Q and LR[pos][0] == i:
        r, l, j = LR[pos]
        ans[j] = bit.sum(r) - bit.sum(l - 1)
        pos += 1

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

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cn = list(map(int, input().split()))
s = [-1]*(n+1)
t = [0]*n
for i in range(n):
    j = cn[i]
    if s[j] == -1:
        t[i] = -1
        s[j] = i
    else:
        t[i] = s[j]
        s[j] = i

ans = [0]*q
for i in range(q):
    count = 0
    l, r = map(int, input().split())
    for j in range(l-1,r):
        if t[j] >= l-1:
            count += 1
    ans[i] = r-l+1-count

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cn = list(map(int, input().split()))
s = [-1]*(n+1)
t = [0]*n
for i in range(n):
    j = cn[i]
    if s[j] == -1:
        t[i] = -1
        s[j] = i
    else:
        t[i] = s[j]
        s[j] = i

ans = [0]*q
for i in range(q):
    count = 0
    l, r = map(int, input().split())
    for j in range(l-1,r):
        if t[j] == -1:
            count +=1
        elif t[j] < l-1:
            count += 1
    ans[i] = count

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cn = list(map(int, input().split()))
s = [-1]*(n+1)
t = [0]*n
for i in range(n):
    j = cn[i]
    if s[j] == -1:
        t[i] = -1
        s[j] = i
    else:
        t[i] = s[j]
        s[j] = i
    #print(s)
    #print(t)


ans = []
for i in range(q):
    count = 0
    l, r = map(int, input().split())
    for j in range(l-1,r):
        if t[j] == -1:
            count +=1
        elif t[j] < l-1:
            count += 1
    ans.append(count)


for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]
for _ in range(q):
    x, y = map(int, input().split())
    x, y = x + k - 2, y + k - 1
    ans = set()
    while x < y:
        if x % 2 == 0:
            ans |= S[x]
            x += 1
        if y % 2 == 0:
            y -= 1
            ans |= S[y]
        x, y = (x - 1) // 2, (y - 1) // 2
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**19
S = [set()] * (2 * k - 1)
for i in range(n):
    S[k - 1 + i] = {C[i]}
for i in range(k - 1)[::-1]:
    S[i] = S[2 * i + 1] | S[2 * i + 2]


def ans(a=0, b=k, p=0):
    if b <= x or y <= a:
        return set()
    if x <= a and b <= y:
        return S[p]
    left = ans(a, (a + b) // 2, 2 * p + 1)
    right = ans((a + b) // 2, b, 2 * p + 2)
    return left | right


for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    print(len(ans()))

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
N=5*10**5
value_to_index=[[]for i in range(N)]

C=list(map(int,input().split()))

for i,v in reversed(list(enumerate(C))):
    value_to_index[v-1].append(i)
LR=[list(map(int,input().split()))+[i]for i in range(Q)]
LR.sort()

#セグ作成
segtree=[[0]*N for i in range(N.bit_length())]
for num,arr in enumerate(value_to_index):
    if arr:
        v=arr[-1]
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][v//p2]+=1
#セグ取得
def seg_range(r):
    r+=1
    l=0
    ans=0
    tmp=1
    # 大きくしていくゾーン
    while tmp<=r:
        tmp*=2
    # 小さくしていくゾーン
    tmp//=2
    while tmp>0:
        if l+tmp<=r:
            ans+=segtree[tmp.bit_length()-1][l//tmp]
            l+=tmp
        tmp//=2
    return ans

tmp=0
ans=[0]*N
for l,r,idx in LR:
    while tmp<l-1:
        v=C[tmp]-1
        tmp+=1
        old = value_to_index[v].pop()
        if value_to_index[v]:
            new = value_to_index[v][-1]
            for i in range(len(segtree)):
                p2=2**i
                segtree[i][new//p2]+=1
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][old//p2]-=1
    ans[idx]=seg_range(r-1)
print(*ans[:Q],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
N=5*10**5
value_to_index=[[]for i in range(N)]

C=list(map(int,input().split()))

for i,v in reversed(list(enumerate(C))):
    value_to_index[v-1].append(i)
LR=[list(map(int,input().split()))+[i]for i in range(Q)]
LR.sort()

#セグ作成
segtree=[[0]*N for i in range(N.bit_length())]
for num,arr in enumerate(value_to_index):
    if arr:
        v=arr[-1]
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][v//p2]+=1
#セグ取得
def seg_range(r):
    r+=1
    l=0
    ans=[]
    tmp=1
    # 大きくしていくゾーン
    while tmp<=r:
        tmp*=2
    # 小さくしていくゾーン
    tmp//=2
    while tmp>0:
        if l+tmp<=r:
            ans.append((tmp.bit_length()-1,l//tmp))
            l+=tmp
        tmp//=2
    return ans

tmp=0
ans=[0]*N
for l,r,idx in LR:
    while tmp<l-1:
        v=C[tmp]-1
        tmp+=1
        old = value_to_index[v].pop()
        if value_to_index[v]:
            new = value_to_index[v][-1]
            for i in range(len(segtree)):
                p2=2**i
                segtree[i][new//p2]+=1
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][old//p2]-=1
    ans[idx]=sum([segtree[i][j] for i,j in seg_range(r-1)])
print(*ans[:Q],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N,Q=map(int,input().split())
N=5*10**5
value_to_index=[[]for i in range(N)]

C=list(map(int,input().split()))

for i,v in reversed(list(enumerate(C))):
    value_to_index[v-1].append(i)
LR=[list(map(int,input().split()))+[i]for i in range(Q)]
LR.sort()

#セグ作成
segtree=[[0]*N for i in range(N.bit_length())]
for num,arr in enumerate(value_to_index):
    if arr:
        v=arr[-1]
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][v//p2]+=1
#セグ取得
def seg_range(l,r):
    r+=1
    ans=[]
    tmp=1
    # 大きくしていくゾーン
    while True:
        while l%(tmp*2)==0 and tmp<=r:
            tmp*=2
        if l+tmp<=r:
            ans.append((tmp.bit_length()-1,l//tmp))
            l+=tmp
        else:
            break
    # 小さくしていくゾーン
    tmp//=2
    while tmp>0:
        if l+tmp<=r:
            ans.append((tmp.bit_length()-1,l//tmp))
            l+=tmp
        tmp//=2
    return ans

tmp=0
ans=[0]*N
for l,r,idx in LR:
    while tmp<l-1:
        v=C[tmp]-1
        tmp+=1
        old = value_to_index[v].pop()
        if value_to_index[v]:
            new = value_to_index[v][-1]
            for i in range(len(segtree)):
                p2=2**i
                segtree[i][new//p2]+=1
        for i in range(len(segtree)):
            p2=2**i
            segtree[i][old//p2]-=1
    ans[idx]=sum([segtree[i][j] for i,j in seg_range(l-1,r-1)])
print(*ans[:Q],sep='\n')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
f=defaultdict(int)
n,q=list(map(int,input().split()))
l=list(map(int,input().split()))
for _ in range(q):
  x,y=list(map(int,input().split()))
  f=defaultdict(int)
  for i in range(x-1,y):
    f[l[i]]+=1
  print(len(f))

Submission status: Time Limit Exceeded

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  input=b.readline
  n,q=map(int,input().split())
  d=[0]*n+[1<<int(i)for i in input().split()]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  add=r.append
  for a,b in zip(*[iter(b.read().split())]*2):
    i,s=int(a)+n-1,0
    j=int(b)+n
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i>>=1
      j>>=1
    add(bin(s).count('1'))
  print(' '.join(map(str,r)))
main()

Submission status: Time Limit Exceeded

Solution code:
N, Q = map(int, input().split())
Color = [0] + list(map(int, input().split()))
Query =[]
for i in range(Q):
    l, r = map(int, input().split())
    Query.append((r, l, i))
Query.sort()
Ans = [0] * Q

BIT = [0] * (N + 1)  # BITを使う


def BIT_query(idx):  # idxまでの合計を返す
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum


def BIT_update(idx,x):  # idxにxを足す
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return


cn = max(Color)
Last = [-1] * cn

cnt = 0
for r, l, i in Query:
    while cnt < r:
        cnt += 1
        c = Color[cnt] - 1
        if Last[c] == -1:
            Last[c] = cnt
            BIT_update(cnt, 1)
        else:
            x = Last[c]
            BIT_update(x, -1)
            Last[c] = cnt
            BIT_update(cnt, 1)
    Ans[i] = BIT_query(r) - BIT_query(l-1)

for a in Ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sort_index = sorted(list(range(len(sect))), key=lambda i: sect[i][0])

    bit = [0] * (N + 1)

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

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

    ans = [0] * Q
    for i in sort_index:
        r, l, n = sect[i]
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def input(): return sys.stdin.readline().rstrip("\r\n")
def List(): return list(map(int, input().split()))
def Num(): return int(input())


def build(tree, a):
    n = len(a)
    for i in range(n):
        tree[n + i].add(a[i])
    for i in range(n - 1, 0, -1):
        tree[i] |= tree[2 * i + 1]
        tree[i] |= tree[2 * i]


def query(tree, a, l, r):
    n = len(a)
    l += n
    r += n
    ans = set()
    while l < r:
        if l & 1:
            ans |= set(tree[l])
            l += 1
        if r & 1:
            r -= 1
            ans |= set(tree[r])
        l //= 2
        r //= 2
    return ans


n, q = List()
a = List()
tree = [set() for _ in range(2 * n)]
build(tree, a)
# print(tree)
for _ in range(q):
    l, r = List()
    print(len(query(tree, a, l - 1, r)))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r + 0.1, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort()

    bit = [0] * (N + 1)

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

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

    ans = [0] * Q
    for s in sect:
        r, l, n = s
        r = int(r)

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def RSQ_add(i, x):
    while True:
        if i > n:
            break
        b[i] += x
        i += i & -i

def RSQ_getsum(i):
    s = 0
    while True:
        if i <= 0:
            break
        s += b[i]
        i -= i & -i
    return s

n, q = map(int, input().split())
c = list(map(int, input().split()))
cc = [0] * n
b = [0] * (n + 1)
a = [deque() for _ in range(n)]
addlist = [0] * (n + 1)
for i in range(n):
    if cc[c[i] - 1] == 0:
        RSQ_add(i + 1, 1)
        cc[c[i] - 1] = 1
        addlist[i + 1] = 1
        #print(b)
    else:
        a[c[i] - 1].append(i + 1)
x = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    x[i] = [l, r, i]
#print(x)
x.sort()
u = 1
xx = [0] * q
endcnt = 0
for i in range(q):
    for j in range(u, x[i][0]):
        if cc[c[j - 1] - 1] == 1:
            if a[c[j - 1] - 1]:
                p = a[c[j - 1] - 1].popleft()
                RSQ_add(p, 1)
                addlist[p] = 1
        if addlist[j + 1]:
            endcnt += 1
            addlist[j + 1] = 0
    u = x[i][0]
    xx[x[i][2]] = RSQ_getsum(x[i][1]) - endcnt
    #print(b)
for i in xx:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n, q = map(int, input().split())
cn = list(map(int, input().split()))
ans = []
for _ in range(q):
    l, r = map(int, input().split())
    ls = set(cn[l-1:r])
    a = len(ls)
    ans.append(a)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

def make_tree(n):
    i = 2
    while True:
        if i >= n * 2:
            tree = [0] * i
            break
        else:
            i *= 2
    return tree

def update(i, x):
    i += lt // 2
    tree[i] = x
    i //= 2
    while True:
        if i == 0:
            break
        tree[i] = tree[2 * i] + tree[2 * i + 1]
        i //= 2
    return

def getsum(s, t):
    s += lt // 2
    t += lt // 2
    ans = 0
    while True:
        if s > t:
            break
        if s % 2 == 0:
            s //= 2
        else:
            ans = ans + tree[s]
            s = (s + 1) // 2
        if t % 2 == 1:
            t //= 2
        else:
            ans = ans + tree[t]
            t = (t - 1) // 2
    return ans

n, q = map(int, input().split())
c = list(map(int, input().split()))
cc = [0] * (n + 1)
tree = make_tree(n)
lt = len(tree)
a = [deque() for _ in range(n)]
for i in range(n):
    if cc[c[i]] == 0:
        update(i, 1)
        cc[c[i]] = 1
    else:
        a[c[i] - 1].append(i)
"""
x = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    x[i] = [l - 1, r - 1, i]
#print(x)
x.sort()
u = 0
xx = [0] * q
for i in range(q):
    for j in range(u, x[i][0]):
        if tree[lt // 2 + j] == 1:
            if a[c[j] - 1]:
                update(a[c[j] - 1].popleft(), 1)
            update(j, 0)
    u = x[i][0]
    xx[x[i][2]] = getsum(0, x[i][1])
    #print(tree)
for i in xx:
    print(i)
"""

x = [deque() for _ in range(n)]
xx = [0] * q
for i in range(q):
    l, r = map(int, input().split())
    x[l - 1].append([r - 1, i])
i = 0
while not i == n:
    while x[i]:
        r, j = x[i].popleft()
        xx[j] = getsum(i, r)
    if tree[lt // 2 + i] == 1:
        if a[c[i] - 1]:
            update(a[c[i] - 1].popleft(), 1)
        update(i, 0)
    i += 1
for i in xx:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort(key=lambda x: (x[0], x[2]))

    bit = [0] * (N + 1)

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

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

    ans = [0] * Q
    for s in sect:
        r, l, n = s

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans[n] = r - l + 1 - t

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


class Bit:

    def __init__(self, a):  # 配列か要素数で初期化
        if hasattr(a, "__iter__"):
            le = len(a)
            self.n = 1 << le.bit_length()
            self.values = values = [0] * (self.n + 1)
            values[1:le + 1] = a[:]
            for i in range(1, self.n):
                values[i + (i & -i)] += values[i]
        elif isinstance(a, int):
            self.n = 1 << a.bit_length()
            self.values = [0] * (self.n + 1)
        else:
            raise TypeError

    def add(self, i, val):  # a[i] += val
        n, values = self.n, self.values
        while i <= n:
            values[i] += val
            i += i & -i

    def sum(self, i):  # (0, i] の累積和
        values = self.values
        res = 0
        while i > 0:
            res += values[i]
            i -= i & -i
        return res


def main():

    N, Q = in_nn()
    C = in_nl()
    LR = []

    for q in range(Q):
        l, r = in_nn()
        LR.append((r, l, q))

    t = [-1] * (N + 1)
    sect = []
    for i in range(N):
        x = C[i]
        if t[x] != -1:
            sect.append((i + 1, t[x], -1))
        t[x] = i + 1

    sect += LR
    sect.sort(key=lambda x: (x[0], x[2]))

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

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

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

    for s in sect:
        r, l, n = s

        if n == -1:
            add(l, 1)
        else:
            t = sum(r) - sum(l - 1)
            ans.append((n, r - l + 1 - t))

    ans.sort()
    for q in range(Q):
        print(ans[q][1])


if __name__ == '__main__':
    main()