i239. 區間 mex
標籤 :
通過比率 : 10人/16人 ( 62% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-08-18 12:40

內容

有一天肯肯肯在滑手機,看到 $\text{b}$ 國手離線,於是肯肯肯問 $\text{b}$ 國手一個離線的區間 $\text{mex}$ 問題:

給你一個長度為 $n$ 的數列 $a_1 \sim a_n$,有 $q$ 筆詢問,每筆詢問給你 $l, r$,請你輸出沒有出現在 $a_l, \dots, a_r$ 裡的最小非負整數。

輸入說明

第一行有兩個正整數 $n, q$,代表數列長度與詢問次數。

第二行有 $n$ 個非負整數 $a_1 \sim a_n$。

接下來 $q$ 行,每行有兩個整數 $l, r$。

  • $1 \leq n \leq 2 \cdot 10^5$
  • $0 \leq a_i \leq n$
  • $1 \leq l \leq r \leq n$
輸出說明

對於每筆詢問,輸出一個整數代表答案。

範例輸入 #1
10 10
3 2 4 3 1 0 2 3 1 3
1 5
2 6
3 4
6 6
1 10
6 10
6 7
8 10
5 6
3 5
範例輸出 #1
0
5
0
1
5
4
1
0
2
0
測資資訊:
記憶體限制: 512 MB
提示 :

$100\%$:無特別限制

$\text{AC}$ 後可以去寫強制在線版本的這題

標籤:
出處:
[管理者: fire5386 (becaidorz) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」