TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

95.2% (99/104)

Submission's AC Ratio

42.1% (163/387)

Tags

Description

你,妹可,睜開眼睛後發現關於自己的事唯一記得的只有名字。

你從損壞的冷凍艙中爬了出來,周圍都是無機質的儀錶板。
由於一直等待也不是辦法,你決定去尋找一些線索。
經由一些蛛絲馬跡以及你驚人的推理(DP)能力,你很快的知道這裡是硬佛石株式會社的總部,硬佛大樓。
硬佛石株式會社是硬佛帝國最大的企業,也是整個帝國運作的中心。

但是很顯然的你身處在一片廢墟中。

你到處亂走,終於發現了一扇門裡透出了微弱的光。

「這是!」

在你眼前的是一個未損壞的冷凍艙,裡面好像躺了一個人。
身為妹可,看到有人在睡覺當然要叫醒他,於是你到了儀表板前面,儀表板上顯示出ᚳᚤᛤᛘᛰ᛭᛭ᚻ, 看起來很像C/C++11

運用你驚人的推理(DP)能力,你很快的知道供應這個冷凍艙能量的,是一整排的「萌」能量槽,每個能量槽都有一個能量值。
而每經過一段時間,冷凍艙就會對一段區間的能量槽發出一陣擾動,而你只要將那個區間的能量槽進行一種很特別的運算-XOR-就可以得到和諧的共鳴頻率,抵消該次擾動。只要成功抵消所有的擾動,你就能喚醒沉睡在冷凍艙中的人。
也就是說,你只要將該區間全部的數字 XOR 起來,就可以得到和諧的共鳴頻率。

『在別人睡覺時配合她打呼的頻率這種變態的行為,我才沒有呢!』----妹可。

Input Format

第一行有兩個整數 $N, Q$,代表能量槽的數量和有幾陣擾動。
第二行有 $N$ 個整數 $H_i$,代表第i個能量槽的「萌」能量值。
接下來 $Q$ 行每行兩個整數 $l, r$,代表擾動的區間。

你可以假設,
對於 33% 的測資,滿足 $N \le 50$,將區間中的值全部加起來也可以得到答案。
對於 66% 的測資,滿如 $N \le 100000, Q \le 10$。
對於 100% 的測資,滿足 $N \le 1000000, Q\le 1000000, 0 \le H_i \le 10 ^ {18}, 1 \le l \le r \le N$。

Output Format

總共輸出 $M$ 行。
每行對於每陣擾動輸出一個整數代表和諧的共鳴頻率。

Sample Input 1

6 3
8 4 2 32 1 16
2 5
1 6
3 6

Sample Output 1

39
63
51

Hints

在ᚳᚤᛤᛘᛰ᛭᛭ᚻ裡,如果要做 XOR 運算可以用 ^ 運算子。
附帶一提,XOR 運算是符合結合律的喔!
而且 A ^ B ^ B == A 喔!
由於輸入檔龐大,請使用ᚳᚤᛤᛘᛰ᛭᛭ᚻ中較快的輸出入函式。
如果你要用ᚳᚤᛤᛘᛰ᛭᛭ᚻ裡的ᚥᛔᛕ(也許是scanf)輸入ᚧᚧᚩᛗᛉ(大概是long long int )時,請用ᛨᚫᚫᛄ(%lld吧)輸入。

PS.由於那些是古代文字,所以你的電腦可能看不到,可以考慮換個字體XD。

Problem Source

資訊社 28屆C/C++學術考試 by果茶
2021.03.14 Update: Added $\LaTeX$ by FHVirus

Subtasks

No. Testdata Range Score
1 0~2 33
2 3~5 33
3 6~8 34

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 1
2 1000 65536 262144 1
3 1000 65536 262144 2
4 1000 65536 262144 2
5 1000 65536 262144 2
6 1000 65536 262144 3
7 1000 65536 262144 3
8 1000 65536 262144 3