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: Runtime Error

Solution code:
import bisect
def main():
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
    E = []

    D = {C[i]: -1 for i in range(N)}
    for i in range(N):
        if D[C[i]] == -1:
            D[C[i]] = i
        else:
            E.append((D[C[i]], i, -1))
            D[C[i]] = i

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

    def f(tup):
        return tup[0]
    E.sort(key=f, reverse=True)

    ANS = [0] * Q
    y_list = [500005]
    for e in E:
        ans = bisect.bisect_right(y_list, e[1])
        if e[2] == -1:
            y_list[ans] = e[1]
        else:
            ANS[e[2]] = e[1] - e[0] + 1 - ans

    for i in range(Q):
        print(ANS[i])

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
N, Q = map(int, input().split())
C = list(map(int, input().split()))
L = [0] * N
R = [0] * N
E = []

D = {C[i]: -1 for i in range(N)}
for i in range(N):
    if D[C[i]] == -1:
        D[C[i]] = i
    else:
        E.append((D[C[i]], i, -1))
        D[C[i]] = i

for i in range(Q):
    l, r = map(int, input().split())
    L[i] = l
    R[i] = r
    E.append((l - 1, r - 1, i))

def f(tup):
    return tup[0]
E.sort(key=f, reverse=True)

ANS = [0] * Q
y_list = []
for e in E:
    if e[2] == -1:
        y_list.append(e[1])
        y_list.sort()
    else:
        ans = bisect.bisect_right(y_list, e[1])
        ANS[e[2]] = e[1] - e[0] + 1 - ans

for i in range(Q):
    print(ANS[i])

Submission status: Runtime Error

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+2)
ans = [None] * Q
last_idx = [-1] * N
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: Runtime Error

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
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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int32)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int32)
    nl, nr = 0, 0
    for i in ind:
        pass
    return answers

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

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

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

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)
print('\n'.join(map(str, ans.tolist())))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

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

Bsize = 700

def Mo_argsort(LR):
    L = LR[:, 0]
    R = LR[:, 1]
    key1 = L // Bsize
    key2 = np.where(key1 & 1, -R, R)
    key = (key1 << 32) + key2
    return np.argsort(key)

def main(A, LR):
    N = len(A)
    Q = len(LR)
    ind = Mo_argsort(LR)
    count = np.zeros(N + 1, np.int32)
    ans = 0

    def add(x):
        nonlocal ans
        if not count[x]:
            ans += 1
        count[x] += 1

    def rem(x):
        nonlocal ans
        count[x] -= 1
        if not count[x]:
            ans -= 1

    answers = np.empty(Q, np.int32)
    nl, nr = 0, 0
    return answers

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

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

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

from my_module import main

N, Q = map(int, readline().split())
A = np.array(readline().split(), np.int64)
LR = np.array(read().split(), np.int64).reshape(Q, 2)

ans = main(A, LR)

Submission status: Runtime Error

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

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = []
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    i = 1
    for _ in range(Q):
        l,r,j = query[j]
        #良い玉の情報を更新する
        while i <= r:
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
            i += 1
        ans.append([j,bit.sum(r)-bit.sum(l-1)])

    ans.sort()
    for a in ans:
        print(a)
main()

Submission status: Runtime Error

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

    N,Q = map(int,input().split())
    bit = BIT(N)
    C = list(map(int,input().split()))
    query = []
    for i in range(Q):
        l,r = map(int,input().split())
        query.append([l,r,i])
    query.sort(key=lambda x: x[1])
    ans = []
    #良い玉のindexを1-indexで管理する
    colorMemo = [0]*(N+1)
    i = 1
    for _ in range(Q):
        l,r,j = query[j][:2]
        #良い玉の情報を更新する
        while i <= r:
            c = C[i-1]
            if colorMemo[c]:
                bit.add(colorMemo[c],-1)
            bit.add(i,1)
            colorMemo[c] = i
            i += 1
        ans.append([j,bit.sum(r)-bit.sum(l-1)])

    ans.sort()
    for a in ans:
        print(a)
main()

Submission status: Runtime Error

Solution code:
def add(idx):
    global s
    if cnt[cs[idx]]==0:
        s += 1
    cnt[cs[idx]] += 1

def delete(idx):
    global s
    cnt[cs[idx]] -= 1
    if cnt[cs[idx]]==0:
        s -= 1

def distribute(idx):
    v[idx]^=True
    if v[idx]:
        add(idx)
    else:
        delete(idx)

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

v=[False]*N
cnt=[0]*N

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


nl=0
nr=0
s=0
ans=[0]*Q
for i in order:
    while nl > querys[i][0]:
        nl -=1
        distribute(nl)
    while nr < querys[i][1]:
        distribute(nr)
        nr +=1
    while nl < querys[i][0]:
        distribute(nl)
        nl +=1
    while nr > querys[i][1]:
        nr -=1
        distribute(nr)
    ans[i] = s
for i in range(Q):
    print(ans[i])

Submission status: Runtime Error

Solution code:
            #init_valは操作する数列
            for i in range(N):
                self.seg[i+self.num-1]=init_val[i]    
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])

Submission status: Runtime Error

Solution code:
from heapq import heapify,heappush,heappop
from sys import stdin
input = stdin.readline

def arr_4(x):
  return [x,x,x,x]

H, W, K = map(int, input().split())
INF = 10 * H * W

x1, y1, x2, y2 = map(int, input().split())
start = (x1-1 ,y1-1, 0)
goal = (x2-1, y2-1, 0)

G = [list(map(arr_4,input().rstrip())) for _ in range(H)]
#G[i][j][k]: (i,j)座標、k方向(0-3)

def dijkstra(G, start, goal):# G:格子、G[i][j][l] = 0 なら通過可、1ならコスト+1 
  H = len(G)
  W = len(G[0])
  #Dir = 4 方向
  task = [] 
  min_cost = [[[(INF,0) for _ in range(4)] for _ in range(W)] for _ in range(H)]
  cost = [[[(INF,0) for _ in range(4)] for _ in range(W)] for _ in range(H)]
  #prev_points = [[[(-2,-2) for _ in range(4)] for _ in range(W)] for _ in range(H)]
  for i in range(4):
    heappush(task, ((1, 0), (start[0], start[1], i), start)) 
    
  #（開始）頂点、コスト、前の点
  # !!コストは（加速回数、慣性で進んだ距離）で規定!! #
  # !!最初の点番号が0でないときは、真ん中の0を変更する!! #
  
  flag = 0
  while task:
    while task:
      c, p, prev = heappop(task)    
      if not G[p[0]][p[1]][p[2]] == "@":
        break  
      if len(task) == 0:
        flag = 1
    if flag == 1:
      break
    #print(task)
    G[p[0]][p[1]][p[2]] = "@"
    min_cost[p[0]][p[1]][p[2]] = c
    #prev_points[p[0]][p[1]] = prev
    
    if p[0] == goal[0] and p[1] == goal[1]:
      return min_cost#, prev_points)
  
    #次の頂点を列挙
    q = []
    if p[0] > 0 and p[2] == 0:#南
      q.append((p[0]-1,p[1],p[2])) 
    if p[0] < H-1 and p[2] == 1:#北
      q.append((p[0]+1,p[1],p[2])) 
    if p[1] > 0 and p[2] == 2:#西
      q.append((p[0],p[1]-1,p[2])) 
    if p[1] < W-1 and p[2] == 3:#東
      q.append((p[0],p[1]+1,p[2]))   
    for i in range(4):
      if not i == p[2]:
        q.append((p[0],p[1],i)) 
    
    for j in q: #制約が入るときはここに追加
      if G[j[0]][j[1]][j[2]] == "@": continue
      
      if p[2] == j[2]:#向き変更なし
        if c[1] == K:
          cost_next = (c[0]+1,1)
        else:
          cost_next = (c[0],c[1]+1)
      else:#向き変更
        cost_next = (c[0]+1,0)
      
      if cost[j[0]][j[1]][j[2]] > cost_next:
        cost[j[0]][j[1]][j[2]] = cost_next
        heappush(task, (cost_next, j, p))
        #print(cost_next, j, p)  
      #print(task)
      
    del q
    
  return min_cost#, prev_points)

min_cost = dijkstra(G, start, goal)

#print(min_cost)

c = min(min_cost[x2-1][y2-1])[0]
if x1 == x2 and y1 == y2:
  c = 0
print(c if c < INF else -1)

Submission status: Runtime Error

Solution code:
from sys import stdin
#import numpy as np

readline = stdin.readline

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

def main(N, Q, C, S):    
  # Binary Indexed Tree 
  # https://juppy.hatenablog.com/entry/2018/11/17/%E8%9F%BB%E6%9C%AC_python_Binary_Indexed_Tree_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0
  b = [0 for _ in range(N+1)]
  def BIT_query(idx): #idxまでの和(1からスタート)
    res_sum = 0
    while idx > 0:
      res_sum += b[idx]
      idx -= idx&(-idx) #一番下の位を減らす（例：13=1011 → 1010 → 1000） 
    return res_sum
  def BIT_update(idx,x): #idxをx増やした時
    while idx <= N:
      b[idx] += x
      idx += idx&(-idx) #一番下の位を繰り上げる（例：13=1011 → 1100 → 10000 ※N=16のとき） 
    return

  loc = [0 for _ in range(N)] #各種類の玉のうちの最右端の所在地
  S = [[S[i][1], S[i][0], i] for i in range(Q)] #クエリ
  S.sort() #区間の右端でソート
  #S = np.array(S, dtype = np.int64)
  #print(S)
  ans = [0 for _ in range(N)]
  k = 0
  for j in range(N):
    if loc[C[j]-1] > 0: #玉の更新
      BIT_update(loc[C[j]-1], -1)
    loc[C[j]-1] = j+1
    BIT_update(j+1, 1)  
    
    if S[k][0] == j+1:
      t = BIT_query(j+1)
    while k < len(S) and S[k][0] == j+1: #クエリへの返答
      ans[S[k][2]] = t - BIT_query(S[k][1]-1)
      k += 1
    if k == len(S):
      break
  return ans

ans = main(N, Q, C, S)
for a in ans:
  print(int(a))

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_add3(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    bit_add(a, i, n, x)
    bit_add(a, j, n, -x)
def bit_add4(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    while i < n:
        a[i] += x
        i += i & -i
    while j < n:
        a[j] -= x
        j += j & -j

def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    X = Q.bit_length()
    mask, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & mask

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add4(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_add3(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    bit_add(a, i, n, x)
    bit_add(a, j, n, -x)
def bit_add4(a, i, j, n, x):
    if j<<1 < n:
        n = 1 << j.bit_length()
    while i < n:
        a[i] += x
        i += i & -i
    while j < n:
        a[j] -= x
        j += j & -j

def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    N, Q = next(it), next(it)
    X = Q.bit_length()
    mask, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = (r, i)
        Ac[i] = l
    Aq.sort()

    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q

    def f2():
        offset = 0
        for r, i in Aq:

            for j in range(offset, r):
                ci = Aa[j]
                j += 2

                j0 = dp[ci]
                bit_add4(bit, j0, j, N1, 1)
                #bit_add(bit, j0, N1, 1)
                #bit_add(bit, j, N1, -1)

                dp[ci] = j

            offset = r
            l = Ac[i]

            ans[i] = bit_sum(bit, l)
    f2()

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#https://qiita.com/takayg1/items/c811bd07c21923d7ec69
#####segfunc#####
def segfunc(x, y):
    return x+y
#################

#####ide_ele#####
ide_ele = 0
#################

class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res



N, Q = map(int, input().split())
c = list(map(int, input().split()))
q = []
for k in range(Q):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  q.append([l, r, k])


q.sort(key = lambda x: x[1])
ans = [0 for k in range(Q)]


good = [0 for _ in range(N)]
good = SegTree(good, segfunc, ide_ele)
lastapp = [-1 for _ in range(N)]
lastapp = SegTree(lastapp, segfunc, ide_ele)
end = -1

for k in range(Q):
  l = q[k][0]
  r = q[k][1]
  a = q[k][2]
  for j in range(r, end, -1):
    if lastapp[c[j]-1] == -1:
      lastapp.update([c[j]-1], j)
      good.update(j, 1)
    elif lastapp[c[j]-1] < j:
      good.update(lastapp[c[j]-1], 0)
      good.update(j, 1)
      lastapp.update([c[j]-1], j)
  ans[a] = good.query(l, r+1)
  end = r
  
for k in range(Q):
  print(ans[k])

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            #bit_add2(bit, j0, j, N1, 1)
            bit_add(bit, j0, N1, 1)
            bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def bit_add(a, i, n, x):
    while i < n:
        a[i] += x
        i += i & -i
def bit_add2(a, i, j, n, x):
    while i < j:
        while i < j:
            a[i] += x
            i += i & -i
        while j < i and j < n:
            a[j] -= x
            j += j & -j
def bit_sum(a, i):
    res = 0
    while i > 0:
        res += a[i]
        i ^= i & -i
    return res
def bit_select(a, i):
    if i & 1: return a[i]
    return a[i] - a[i-1]

def resolve():
    it = map(int, sys.stdin.read().split())
    X = 19
    N, Q = next(it), next(it)
    X = Q.bit_length()
    b1, br, bc = (1 << X)-1, 2*X+1, 1<<X

    if Q == 3:
        raise 1

    Aa = [next(it)-1 for i in range(N)]
    Aq = [0] * Q
    Ac = [0] * Q
    for i in range(Q):
        l, r = next(it), next(it)
        Aq[i] = r<<X | i
        Ac[i] = l

    Aq.sort()
    dp = [1] * N
    N1 = N+1
    bit = [0] * N1

    ans = [0] * Q
    offset = 0
    for arg in Aq:
        r = arg >> X
        i = arg & b1

        for j in range(offset, r):
            ci = Aa[j]
            j += 2

            j0 = dp[ci]
            bit_add2(bit, j0, j, N1, 1)
            #bit_add(bit, j0, N1, 1)
            #bit_add(bit, j, N1, -1)

            dp[ci] = j

        offset = r
        l = Ac[i]

        ans[i] = bit_sum(bit, l)

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


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
from dataclasses import dataclass
    
class BIT:
    '''
    All methods use 0-based index while the implementation use 1-based index
    '''
    def __init__(self, N, val=0):
        self.data = [val] * (N + 1)
        self.N = N
    
    def add_at(self, idx, val):
        i = idx + 1
        while i <= self.N:
            self.data[i] += val
            i += i & (-i)
    
    def sum_to(self, idx):
        res = 0
        i = idx + 1
        while i > 0:
            res += self.data[i]
            i -= i & (-i)
        return res
    
    def sum_in(self, l, r): # [l, r]
        return self.sum_to(r) - self.sum_to(l - 1)
    
    
@dataclass
class Query:
    i: int
    l: int
    r: int
    
    
N, Q = map(int, input().split())
C = list(map(int, input().split()))
    
queries = [[] for _ in range(N)]
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    queries[r].append(Query(i, l, r))
    
V = max(C)
bit = BIT(N)
last = [-1] * (max(C) + 1)
    
query_idx = 0
ans = [-1] * Q
for i, c in enumerate(C):
    if last[c] != -1:
        bit.add_at(last[c], -1)    
    bit.add_at(i, +1)
    last[c] = i
    
    for q in queries[i]:
        ans[q.i] = bit.sum_in(q.l, q.r)
    
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
    from dataclasses import dataclass
     
    class BIT:
        '''
        All methods use 0-based index while the implementation use 1-based index
        '''
        def __init__(self, N, val=0):
            self.data = [val] * (N + 1)
            self.N = N
     
        def add_at(self, idx, val):
            i = idx + 1
            while i <= self.N:
                self.data[i] += val
                i += i & (-i)
     
        def sum_to(self, idx):
            res = 0
            i = idx + 1
            while i > 0:
                res += self.data[i]
                i -= i & (-i)
            return res
     
        def sum_in(self, l, r): # [l, r]
            return self.sum_to(r) - self.sum_to(l - 1)
     
     
    @dataclass
    class Query:
        i: int
        l: int
        r: int
     
     
    N, Q = map(int, input().split())
    C = list(map(int, input().split()))
     
    queries = [[] for _ in range(N)]
    for i in range(Q):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        queries[r].append(Query(i, l, r))
     
    V = max(C)
    bit = BIT(N)
    last = [-1] * (V + 1)
     
    query_idx = 0
    ans = [-1] * Q
    for i, c in enumerate(C):
        if last[c] != -1:
            bit.add_at(last[c], -1)    
        bit.add_at(i, +1)
        last[c] = i
     
        for q in queries[i]:
            ans[q.i] = bit.sum_in(q.l, q.r)
     
    print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from numba import njit#,i8


def input(): return sys.stdin.readline()

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

C=np.array(input().split(), int)

# Query取得-rightでソート
# dtypeQuery = [("index", int), ("start", int), ("end", int)]
queries=np.empty((Q,2),int)
# #rights=[[] for _ in range(N+1)]

for q in range(Q):
	l,r=map(int,input().split())
	#queries[q] = (q,l,r)
	queries[q][0] = l
	queries[q][1] = r
	#queries=np.sort(queries,order="end")

#queries=np.array(sys.stdin.buffer.read().split(),int).reshape(Q,2)

orderByR=np.argsort(queries[:,1])

# 各色の現在の一番右のindex
mostRightColorIndex = np.zeros(N+1, int)
# bit indexed tree
bitArray=np.zeros(N+1,int)

#@njit(cache=True)
# @jit(返り値の型(引数1の型,引数2の型,．．．,引数nの型))
#@jit(i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:]))
def main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):

	def add(itemCount, items, i, value):
		while i <= itemCount:
			items[i] += value
			i += (i & (-i))

	def sumFromStart(items, end):
		summary = 0
		i = end
		while i > 0:
			summary += items[i]
			i -= (i & (-i))
		return summary

	def sum(items, start,end):
		summary = sumFromStart(items, end) - sumFromStart(items, start-1)
		return summary

	# 答え配列
	ans=np.zeros(Q, dtype=np.int64)
	#ans=[0]*Q
	# 左からBITと現在色の更新をしながら、クエリのrightに到達したときにBITにクエリ発行する
	qindex = 0

	for n in range(N):
		# 外側のループでは、全部の色をループ

		if Q <= qindex:
			break

		if 0 < mostRightColorIndex[C[n]]:
			# ループ中の場所の色のindexが既にある場合(=過去に、同じ色が登録されていた場合)
			# 今回で、同じ色の一番右側の要素はループ中の要素になる
			# 前登録したこの色の一番右のindexを一度BITから抜く(↓で再度登録される)
			add(N,bitArray,mostRightColorIndex[C[n]], -1 )

		# この要素の色の一番右のindexを、BITに登録
		mostRightColorIndex[C[n]] = n+1
		add(N,bitArray,n+1, 1)

		# while qindex < Q and n+1 == queries[qindex][2]:
		while qindex < Q and n+1 == queries[orderByR[qindex]][1]:
			# 今のBITが次のクエリ発行するための状態(n==query.right)だったら、クエリ発行
			tmpIndex = orderByR[qindex]
			start = queries[tmpIndex][0]
			end = queries[tmpIndex][1]
			ans[tmpIndex]=sum(bitArray,start,end)
			# print(tmpIndex,start,end,ans[tmpIndex])
			qindex += 1

	return ans

if sys.argv[-1]=='ONLINE_JUDGE':
	from numba.pycc import CC
	cc=CC('my_module')
	cc.export('main','i8[:](i8,i8,i8[:],i8[:,:],i8[:],i8[:],i8[:])')(main)
	cc.compile()
	exit()
from my_module import main

for a in main(N,Q,C,queries,orderByR,mostRightColorIndex,bitArray):
	print(a)