a015: C. The Jet-Black Wing ∼ 漆⿊之翼
標籤 : NPSC2017
通過比率 : 100% (1 人 / 1 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2018-07-20 19:41

內容 :

「呃啊 · · · 可惡!· · · 要發狂了嗎!」

艾迪,⼀個⾃稱為「漆⿊之翼」的⼈,正在與名為「Dark Reunion」的邪惡組織作戰。接著他就驚醒了,原來只是⼀場夢阿 · · ·

「我⼀定要變得更強。」艾迪在⼼中激勵⾃⼰。

為了成為⼀名強悍的戰⾾者,艾迪認真的鍛鍊⾃⼰。在他的練習中,他收集了 N 顆魔法⽯
頭,第 i 顆魔法⽯頭有著 Ai 單位的⿊暗⼒量。⼀開始,艾迪先將所有的魔法⽯頭依照⿊暗⼒量
的⼤⼩由⼩到⼤排序,接着,艾迪會進⾏ Q 次操作,每次操作有以下三種:


• 1 X:使⽤ X 單位的⿊暗⼒量於每顆魔法⽯頭,因此,第 i 顆魔法⽯頭的暗⿊⼒量會變
成 Ai ⊕ X 單位。
• 2 L R:詢問第 L 顆魔法⽯頭⾄第 R 顆魔法⽯頭⿊暗⼒量的總和。
• 3:將魔法⽯頭依照⿊暗⼒量由⼩到⼤排序好。


你能夠幫助艾迪確認他操作的過程是否正確嗎?


x⊕y 表⽰將 x 與 y 進⾏互斥或 (exclusive OR) 操作。即將兩數以⼆進制展開後,每位元分
別做互斥或運算,當兩兩數值相同時為 0,⽽數值不同時為 1。舉例來說,1 ⊕ 2 = 3, 2 ⊕ 2 = 0。
這個操作存在於所有常⽤的程式語⾔中,例如:C/C++ 與 Java 即是使⽤「ˆ」。

輸入說明

測試資料第⼀⾏有兩個數字 N, Q,表⽰艾迪蒐集的魔法⽯頭個數與訓練的操作次數。

測試資料第⼆⾏有 N 個數字 A1, A2, . . . , AN,其中 Ai 表⽰第 i 顆魔法⽯頭的⿊暗⼒量;保 證 A 序列是⼀個⾮遞減序列。

接下來 Q ⾏,每⾏表⽰⼀個操作「1 X」、「2 L R」或「3」。

• 1 ≤ N, Q ≤ 10^5

• 0 ≤ Ai , X < 2^31

• 1 ≤ L ≤ R ≤ N

輸出說明

對於每個「2 L R」的操作,輸出⼀個數字於⼀⾏,表⽰第 L 顆魔法⽯頭⾄第 R 顆魔法⽯ 頭⿊暗⼒量的總和。

範例輸入
5 6
0 2 3 4 5
2 2 4
1 12
2 2 4
3
2 1 5
2 1 1
範例輸出
9
37
58
8
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (10%): 4.0s , <1K
公開 測資點#1 (10%): 4.0s , <1K
公開 測資點#2 (10%): 4.0s , <1M
公開 測資點#3 (10%): 4.0s , <1K
公開 測資點#4 (10%): 4.0s , <1K
公開 測資點#5 (10%): 4.0s , <1K
公開 測資點#6 (10%): 4.0s , <1M
公開 測資點#7 (10%): 4.0s , <1K
公開 測資點#8 (10%): 4.0s , <1K
公開 測資點#9 (10%): 4.0s , <1K
提示 :
標籤:
NPSC2017
出處:
NPSC2017 [編輯: han910625 (Satisfy) ]
編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」