c628. 皮皮的邀約 - 高中生程式解題系統

內容

雖說一日之計在於晨，但對皮皮而言，璀璨夜晚才是他的活動時刻。作為夜晚的開始，皮皮每天總會邀請三五好友一同享用晚餐，而今晚他遭遇一個難題 ── 一位朋友臨時有事無法抽身，因此多了個位子。

皮皮的朋友足足有 $200005.6$ 位那麼多，對他而言，身邊出現空位是最無法忍受的事。他二話不說掏出紙筆，將所有還沒被邀請的朋友列成名單並寫上他們的「人際度」── 這是種皮皮用來衡量一個人是否適合邀請的指標。皮皮接下來會隨意指出若干個區間，並請你找出區間中「人際度」最高的一位朋友好讓他提出邀約（你只要回答該位朋友的人際度）。儘管這個問題看起來就像第三組測資一樣簡單，皮皮卻立即提出奇怪的限制：只要區間中存在多位擁有同樣人際度的朋友，就必須將他們以兩兩一組的方式從該次選擇剔除。

在漫長的等待中，皮皮逐漸失去耐心，你得在每次詢問後馬上告訴他答案，而非在最後一次回答。

輸入說明

第一行有三個正整數 $N, Q, O (1 \leq N, Q \leq 200000, O \in {0, 1})$ ，分別代表朋友數量、詢問次數以及皮皮是否已失去耐心。

第二行為一整數序列，表示朋友的人際度 $S_{1} \sim S_{N}$ ( $1 \leq S_{i} \leq 10^{9}$ )。

接下來 $Q$ 行分別有兩個正整數 $l, r$ 表示詢問區間。
若 $O = 0$ ，你不用對 $l, r$ 做任何操作；
若 $O = 1$ ，為模擬實際情形， $l, r$ 應替換為 $(l + a n s) % N + 1$ , $(r + a n s) % N + 1$ ，其中 $a n s$ 代表前一次詢問的答案(第一次前視為 $0$ )。

保證替換前後 $1 \leq l, r \leq N$ 。

輸出說明

輸出皮皮邀約對象的人際度。

如果沒有能選擇的朋友，請輸出 $0$ 。

範例輸入 #1

範例輸出 #1

範例輸出一：
1
2
0

範例輸出二：
1
2
0

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (5%): 2.0s , <1M
公開測資點#1 (5%): 2.0s , <1M
公開測資點#2 (10%): 2.0s , <10M
公開測資點#3 (10%): 2.0s , <10M
公開測資點#4 (10%): 2.0s , <10M
公開測資點#5 (6%): 2.0s , <10M
公開測資點#6 (6%): 2.0s , <10M
公開測資點#7 (8%): 2.0s , <10M
公開測資點#8 (8%): 2.0s , <10M
公開測資點#9 (8%): 2.0s , <10M
公開測資點#10 (8%): 2.0s , <10M
公開測資點#11 (8%): 2.0s , <10M
公開測資點#12 (8%): 2.0s , <10M

提示：

範例輸入二和範例輸入一的詢問區間一模一樣。

測資點 $0 \sim 1 (10 %)$ ， $1 \leq N, Q \leq 1000, O = 0$ 。

測資點 $2 \sim 4 (30 %)$ ， $O = 0$ 。

測資點 $5 \sim 6 (12 %)$ ， $O = 1$ ，任兩位朋友的人際度必定相異。

測資點 $7 \sim 12 (48 %)$ ， $O = 1$ 。

標籤:

出處:

[管理者： icube (!@#$%^&*()_...) ]

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