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:
#参考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

#%%

def function():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]
    
    for i in range(len(lrs)):
        lrs[i].append(i)
    
    right_edge = [-1]*(N+1)
    seg = SegTree([0]*(N+1), segfunc, ide_ele)
    # =============================================================================
    # print(seg.tree[1])
    # print(seg.query(0,7))
    # seg.update(0,100)
    # print(seg.tree)
    # =============================================================================
    
    lrs = sorted(lrs, key = lambda x:x[1])
    order_num = 0
    answer = [0]*(Q)
    for i, c_o in enumerate(c):
        if right_edge[c_o] >= 0:
            seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
        
        for i in range(N):
            if order_num >= Q:
                break
            if lrs[order_num][1] == i:
                answer[lrs[order_num][2]] = [order_num,seg.query(lrs[order_num][0],lrs[order_num][1]+1)]
                order_num += 1
            else:
                break
    
    for i in range(len(answer)):
        print(answer[i][1])
        
if __name__ == '__main__':
    function()

Submission status: Runtime Error

Solution code:
import bisect

def answer(kintama, lri0):
    tama = kintama[:]
    tama.sort()
    num = bisect.bisect_left(tama, lri0)
    return 10**5+1 - num

n, q = [int(i) for i in input().split()]
c = [int(i)-1 for i in input().split()]
lr = []
for i in range(q):
    lr_ = [int(_)-1 for _ in input().split()] + [i]
    lr.append(lr_)
lr.sort(key=lambda x: x[1])

k = 0
ans = []
kintama = [-10 for i in range(10**5+1)]

for i in range(q):
    while lr[i][1] > k:
        kintama[c[k]] = k
        k += 1
    kintama[c[k]] = k
    ans.append([answer(kintama, lr[i][0]), lr[i][2]])

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

Submission status: Runtime Error

Solution code:
import bisect

def answer(kintama, lri0):
    tama = kintama[:]
    tama.sort()
    num = bisect.bisect_left(tama, lri0)
    return 10**5 - num

n, q = [int(i) for i in input().split()]
c = [int(i)-1 for i in input().split()]
lr = []
for i in range(q):
    lr_ = [int(_)-1 for _ in input().split()] + [i]
    lr.append(lr_)
lr.sort(key=lambda x: x[1])

k = 0
ans = []
kintama = [-10 for i in range(10**5)]

for i in range(q):
    while lr[i][1] > k:
        kintama[c[k]] = k
        k += 1
    kintama[c[k]] = k
    ans.append([answer(kintama, lr[i][0]), lr[i][2]])

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

Submission status: Runtime Error

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


class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = [0]*(n+1)
    
    def summarize(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s
    
    def add(self, i, x):
        # assert i > 0
        self.value[i] += x
        while i <= self.n:
            self.bit[i] += x
            i += i & -i
    
    def init(self, n, lis):
        self.n = n
        self.bit = [0]*(n+1)
        self.value = lis
        for i in range(n):
            self.add(i, lis[i])
            
    def get_value(self, i):
        return self.value[i]
    
    def get_sum(self, i, j):
        return self.summarize(j) - self.summarize(i)


def main():
    n, q = map(int, input().split())
    c = [int(x) for x in input().split()]
    
    judge = dict()
    key = [-1]*n
    for i in range(n):
        if c[i] in judge:
            key[i] = judge[c[i]]
        judge[c[i]] = i
    
    query = [None]*q
    for i in range(q):
        l, r = map(int, input().split())
        query[i] = (r-1, l-1, i)
    
    query.sort()
    
    bit = BIT(n)
    ans = [0]*n
    index = 0
    for i in range(n):
        bit.add(i+1, 1)
        if key[i] != -1:
            bit.add(key[i]+1, -1)
        while True:
            if index == q:
                break
            r, l = query[index][0], query[index][1]
            if r == i:
                ans[query[index][2]] = bit.get_sum(l, r+1)
                index += 1
            else:
                break
        if index == q:
            break
    for v in ans:
        print(v)
    
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from operator import itemgetter
def position_zip(a,flag):
  j=0
  d={}
  for i in sorted(a):
    if i in d:continue
    d[i]=j
    j+=1
  if flag==1:return d
  return [d[i] for i in a]
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
n,q=map(int,input().split())
a=list(map(int,input().split()))
a=position_zip(a,0)
k=max(a)+1
ans=[0]*q
queries=[list(map(lambda x:int(x)-1,input().split()))+[i]for i in range(q)]
queries.sort(key=itemgetter(1))
queries.append([0,0,0])
lastAppeared=[-1]*k
bitt=BinaryIndexedTree(n)
j=0
for i in range(n):
  if lastAppeared[a[i]]!=-1:
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  else:
    bitt.add(i,1)
    lastAppeared[a[i]]=i
  while queries[j][1]==i:
    l,r,ind=queries[j]
    j+=1
    ans[ind]=bitt.sum(l,r-1)
print(*ans)

Submission status: Runtime Error

Solution code:
import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

    def __init__(self, n):
        # 0-indexed
        n += 1
        nv = 1
        while nv < n:
            nv *= 2
        self.size = nv
        self.tree = [0] * nv

    def sum(self, i):
        """ [0, i]を合計する """
        s = 0
        i += 1
        while i > 0:
            s += self.tree[i-1]
            i -= i & -i
        return s

    def add(self, i, x):
        """ 値の追加：添字i, 値x """
        i += 1
        while i <= self.size:
            self.tree[i-1] += x
            i += i & -i

    def get(self, l, r=None):
        """ 区間和の取得 [l, r) """
        # 引数が1つなら一点の値を取得
        if r is None: r = l + 1
        res = 0
        if r: res += self.sum(r-1)
        if l: res -= self.sum(l-1)
        return res

    def update(self, i, x):
        """ 値の更新：添字i, 値x """
        self.add(i, x - self.get(i))

    def print(self, N):
        for i in range(N):
            print(self.get(i), end=' ')
        print()

N, Q = MAP()
A = [a-1 for a in LIST()]

prev = [-1] * N
events = []
bit = BIT(N)
for t, a in enumerate(A):
    s = prev[a]
    if s != -1:
        events.append((t, 0, s))
    prev[a] = t

for i in range(Q):
    l, r = MAP()
    l -= 1; r -= 1
    events.append((r, 1, l, i))

events.sort()
raise Exception
ans = [0] * Q
for event in events:
    if event[1] == 0:
        t, _, s = event
        bit.add(s, 1)
    else:
        r, _, l, i = event
        total = r - l + 1
        ans[i] = total - bit.get(l, N)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(n):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.readline
class BinaryIndexedTree:
  def __init__(self,n):
    self.bit=[0]*n
  def add(self,i,x):
    i+=1
    while i<=len(self.bit):
      self.bit[i-1]+=x
      i+=i&-i
  def sum_sub(self,i):
    a=0
    i+=1
    while i:
      a+=self.bit[i-1]
      i-=i&-i
    return a
  def sum(self,i,j):
    a=self.sum_sub(j+1)
    if i!=0:a-=self.sum_sub(i-1)
    return a
def main():
  n,q,*a=map(int,open(0).read().split())
  ans=[0]*q
  queries=[]
  for i in range(q):queries.append((a[n+i*2+1]-1,a[n+i*2]-1,i))
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[n]*n
  bitt=BinaryIndexedTree(n+1)
  j=0
  for i in range(n):
    bitt.add(lastAppeared[a[i]],-1)
    bitt.add(i,1)
    lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:

def segfunc(x, y):
    return x+y

ide_ele = 0

class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        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 += 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):

        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()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i].append(i)

right_edge = [-1 for _ in range(N+1)]
seg = SegTree([0 for i in range(N+1)], segfunc, ide_ele)

lrs = sorted(lrs, key = lambda x:x[1])
order_num = 0
answer = []
for i, c_o in enumerate(c):
    if right_edge[c_o] == -1:
        right_edge[c_o] = i
        seg.update(i, 1)
    elif right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
    
    while True:
        if order_num >= Q:
            break
        if lrs[order_num][1] == i:
            answer.append(seg.query(lrs[order_num][0],lrs[order_num][1]+1))
            order_num += 1
        else:
            break
        
answer = sorted(answer,key=lambda x: lrs[x][2])

for i in range(len(answer)):
    print(answer[i])

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()))
lrs = [list(map(lambda x:int(x)-1, input().split())) for i in range(Q)]

for i in range(len(lrs)):
    lrs[i].append(i)

right_edge = [-1 for _ in range(N+1)]
seg = SegTree([0 for i in range(N+1)], segfunc, ide_ele)
# =============================================================================
# print(seg.tree[1])
# print(seg.query(0,7))
# seg.update(0,100)
# print(seg.tree)
# =============================================================================

lrs = sorted(lrs, key = lambda x:x[1])
order_num = 0
answer = []
for i, c_o in enumerate(c):
    if right_edge[c_o] == -1:
        right_edge[c_o] = i
        seg.update(i, 1)
    elif right_edge[c_o] >= 0:
        seg.update(right_edge[c_o], 0)
        right_edge[c_o] = i
        seg.update(i, 1)
    
    while True:
        if order_num >= Q:
            break
        if lrs[order_num][1] == i:
            answer.append(seg.query(lrs[order_num][0],lrs[order_num][1]+1))
            order_num += 1
        else:
            break
        
answer = sorted(answer,key=lambda x: lrs[x][2])

for i in range(len(answer)):
    print(answer[i])

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res


n, q = LI()
ans = [0] * q
C = LI()
Q = []
for i in range(q):
    l, r = LI()
    Q += [(l-1, 0, i)]
    Q += [(r-1, 1, i)]

Q.sort()
Q += [(INF, 0, 0)]
last = [-1] * n
DD = {}
bit = BIT(n + 1)
now = 0
for i in range(n):
    col = C[i]
    bit.add(i, 1)
    if last[col] != -1:
        bit.add(last[col], -1)
    last[col] = i
    while Q[now][0] == i:
        idx, flg, qq = Q[now]
        if flg:
            ans[qq] = bit.sum(idx) - bit.sum(DD[qq] - 1)
        else:
            DD[qq] = idx
        now += 1


#    print(q_now, "b")

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    """
    Binary Index Tree
    ###1-origin####

    add :L[i]+=x
    sum: sum(L[:l])
    range_sum : sum(L[l:r])

    #material http://hos.ac/slides/20140319_bit.pdf
    """


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

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

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


n, q = LI()
ans = [0] * q
C = LI()
Q = []
for i in range(q):
    l, r = LI()
    Q += [(l-1, 0, i)]
    Q += [(r-1, 1, i)]

Q.sort()
Q += [(INF, 0, 0)]
D = defaultdict(lambda:-1)
DD = {}
bit = BIT(q + 1)
now = 0
q_now = 0
for i in range(n):
    col = C[i]
    last_q_now = D[col]
    if last_q_now == -1:
        bit.add(0, 1)
    else:
        bit.add(last_q_now, 1)
# print(bisect_right(l_idx, last_idx), "a")
    while Q[now][0] <= i:
        idx, flg, qq = Q[now]
        if flg:
            ans[qq] = bit.sum(DD[qq])
        else:
            DD[qq] = q_now
        q_now += 1
        now += 1
    D[col] = q_now
    bit.add(q_now, -1)
#    print(q_now, "b")


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

Submission status: Runtime Error

Solution code:
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
R=range
for i in R(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in R(N)]
for i in R(n):A[c[i]].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=x>>40-1
	r=x>>20&N
	i=x&N
	while t+1<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	while r:o[i]+=B[r];r-=r&-r
	while l:o[i]-=B[l];l-=l&-l
for i in o:print(i)

Submission status: Runtime Error

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

Solution code:
n, q = map(int, input().split())
*C, = map(int, input().split())
k = 2**16
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: Runtime Error

Solution code:
from math import ceil,log,floor 

  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 

segment=[[] for i in range(1000)] 

  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 

def build(i, s, e, arr): 

  

    # If start is equal to end then 

    # append the array element 

    if (s == e): 

        segment[i].append(arr[s]) 

        return

  

    # Else divide the range into two halves 

    # (start to mid) and (mid+1 to end) 

    # first half will be the left node 

    # and the second half will be the right node 

    build(2 * i, s, (s + e) // 2, arr) 

    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 

  

    # Insert the sets of right and left 

    # node of the segment tree 

    segment[i].append(segment[2 * i]) 

  

    segment[i].append(segment[2 * i + 1]) 

  
# Query in an range a to b 

def query(node, l, r, a, b): 

    left, right, result=[],[],[] 

  

    # If the range is out of the bounds 

    # of this segment 

    if (b < l or a > r): 

        return result 

  

    # If the range lies in this segment 

    if (a <= l and r <= b): 

        return segment[node] 

  

    # Else query for the right and left 

    # leaf node of this subtree 

    # and append them into the set 

    left = query(2 * node, l, (l + r) // 2, a, b) 

    result.append(left) 

  

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 

    result.append(right) 

  

    # Return the result 

    return result 

def answer(ans): 

    d = {} 

    for i in str(ans): 

        if i not in ['[',',',']',' ']: 

            d[i]=1

    return len(d) 

  
# Initialize the segment tree 

def init(n): 

      

    # Get the height of the segment tree 

    h = ceil(log(n, 2)) 

    h = (2 * (pow(2, h))) - 1

  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 

def getDistinct(l, r, n): 

      

    # Query for the range set 

    ans = query(1, 0, n - 1, l, r) 

  

    print(answer(str(ans))) 

  
# Driver code
N,Q=map(int,input().split())

arr=list(map(int,input().strip().split()))


n = len(arr) 

  
init(n) 

  
# Bulid the segment tree 

build(1, 0, n - 1, arr) 

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

Submission status: Runtime Error

Solution code:
from math import ceil,log,floor 

  
# Each segment of the segment tree would be a set 
# to maintain distinct elements 

segment=[[] for i in range(1000)] 

  
# Build the segment tree 
# i denotes current node, s denotes start and 
# e denotes the end of range for current node 

def build(i, s, e, arr): 

  

    # If start is equal to end then 

    # append the array element 

    if (s == e): 

        segment[i].append(arr[s]) 

        return

  

    # Else divide the range into two halves 

    # (start to mid) and (mid+1 to end) 

    # first half will be the left node 

    # and the second half will be the right node 

    build(2 * i, s, (s + e) // 2, arr) 

    build(1 + 2 * i, 1 + (s + e) // 2, e, arr) 

  

    # Insert the sets of right and left 

    # node of the segment tree 

    segment[i].append(segment[2 * i]) 

  

    segment[i].append(segment[2 * i + 1]) 

  
# Query in an range a to b 

def query(node, l, r, a, b): 

    left, right, result=[],[],[] 

  

    # If the range is out of the bounds 

    # of this segment 

    if (b < l or a > r): 

        return result 

  

    # If the range lies in this segment 

    if (a <= l and r <= b): 

        return segment[node] 

  

    # Else query for the right and left 

    # leaf node of this subtree 

    # and append them into the set 

    left = query(2 * node, l, (l + r) // 2, a, b) 

    result.append(left) 

  

    right = query(1 + 2 * node, 1 + (l + r) // 2, r, a, b) 

    result.append(right) 

  

    # Return the result 

    return result 

def answer(ans): 

    d = {} 

    for i in str(ans): 

        if i not in ['[',',',']',' ']: 

            d[i]=1

    return len(d) 

  
# Initialize the segment tree 

def init(n): 

      

    # Get the height of the segment tree 

    h = ceil(log(n, 2)) 

    h = (2 * (pow(2, h))) - 1

  
# Function to get the result for the 
# subarray from arr[l] to arr[r] 

def getDistinct(l, r, n): 

      

    # Query for the range set 

    ans = query(1, 0, n - 1, l, r) 

  

    print(answer(str(ans))) 

  
# Driver code
N,Q=map(int,input().split())

arr=list(map(int,input().strip().split()))


n = len(arr) 

  
init(n) 

  
# Bulid the segment tree 

build(1, 0, n - 1, arr) 

  
for i in range(Q):
	l,r=map(int,input().split())
	getDistinct(l+1, r+1, n)

Submission status: Runtime Error

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.bit_length() 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: Runtime Error

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.bit_length() 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[:n],sep='\n')

Submission status: Runtime Error

Solution code:
import sys
b=sys.stdin.buffer
input=b.readline
def main():
  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()