i832: 區間 mex (在線)
Tags :
Accepted rate : 2人/3人 ( 67% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-22 15:11

Content

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

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

因為肯肯肯想要在線,所以他會把 $l, r$ 分別對前一次詢問的答案 $\text{xor}$ 得到 $l', r'$,也就是 $l' = l \text{ xor } ans, r' = r\text{ xor }ans$,$ans$ 代表前一次詢問的答案,若此次為第一次詢問,那 $ans$ 預設為 $0$。

Input

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

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

接下來 $q$ 行,每行有兩個整數 $l', r'$,代表被前一次答案 $\text{xor}$ 過的詢問。

  • $1\leq n, q\leq 2 \times 10^5$
  • $0\leq a_i \leq 10^9$
  • $1\leq l \leq r \leq n$,這裡的 $l, r$ 還沒被 $\text{xor}$ 過。
Output

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

Sample Input #1
10 10
3 2 4 3 1 0 2 3 1 3
4 4
3 6
5 11
4 7
12 13
3 4
4 5
10 10
3 7
7 15
Sample Output #1
0
2
0
4
0
0
0
0
5
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 1.5s , <10M
公開 測資點#1 (5%): 1.5s , <10M
公開 測資點#2 (5%): 1.5s , <10M
公開 測資點#3 (5%): 1.5s , <10M
公開 測資點#4 (5%): 1.5s , <10M
公開 測資點#5 (5%): 1.5s , <10M
公開 測資點#6 (5%): 1.5s , <10M
公開 測資點#7 (5%): 1.5s , <10M
公開 測資點#8 (5%): 1.5s , <10M
公開 測資點#9 (5%): 1.5s , <10M
公開 測資點#10 (5%): 1.5s , <10M
公開 測資點#11 (5%): 1.5s , <10M
公開 測資點#12 (5%): 1.5s , <10M
公開 測資點#13 (5%): 1.5s , <10M
公開 測資點#14 (5%): 1.5s , <10M
公開 測資點#15 (5%): 1.5s , <10M
公開 測資點#16 (5%): 1.5s , <10M
公開 測資點#17 (5%): 1.5s , <10M
公開 測資點#18 (5%): 1.5s , <10M
公開 測資點#19 (5%): 1.5s , <10M
Hint :

$100\%:無特別限制$

Tags:
出處:
[管理者: becaido(Caido) ]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」