TopCoder

Thumb tumblr m6532itd121rnos1s
$(pr)^3pony$
https://prprprpony.github.io/blog/ $\\\huge PinkiePie:"OkieDokieLokie"$

User's AC Ratio

40.0% (8/20)

Submission's AC Ratio

5.2% (9/173)

Tags

Description

你有聽過殿仁.王嗎?

傳說那時,魔法少女小向放棄了IPhO(International Phase Olympiad,國際「向」奧林匹亞)天龍國國家代表隊正選資格,跑去開早餐店了。而重力之神CBD收完了貢品後,也回到了重力之中。

有一個黑影,盯著當年周強留下的石板,傳說當年周強盯著石板就用腦袋算出了石板上的魔法問題,而那是現代科技都難以在短時間內解出的問題,這個人摸著這塊石板,探了一口氣。
「你什麼人啊?我們要研究石板,你快點離開吧!」
「無趣。」
「你是誰好大的口氣!你也懂魔法?」
這時,周圍出現了異象,空氣發出撕裂的聲音,瞬間,強大的電流爆發出來,將洞穴照得如同白晝一般,幾個無名小卒轉眼間就變成了灰燼。
「啊啊……你……你到底是誰啊!」
「我,沒有名字,但是,人們都叫我『電人王』」
「啊啊啊啊啊啊啊啊啊……」無名小卒慘叫一聲, 然後他就死掉了

黑影嘆了一口氣,轉身離開了石穴,對他來說,這裡已經沒有任何繼續留下來的價值了。
「慢著!!」一位名叫多多的魔法師呼喚了王。
「還有什麼事……」
「難道對你來說,魔法就是用來電人的工具嗎!」
「我不懂你再說什麼……」
「隨手就把人電爆……這樣的作風,是一個魔法師該有的素養嗎!魔法,不是用來讓世界更美好的嗎!」
「你也懂魔法?你那也叫作魔法?」
多多退後了幾步。「身為魔法師,有維護世界和平的必要!」
「我不是魔法師……」王轉身面對多多。「不要把我和你們這種不認識學妹的魔法師相提並論!」

一道強勁的電流貫穿了多多,多多的眼前,出現了人生跑馬燈,一幕幕的回憶出現在多多的眼前,包含他的青梅竹馬、喜歡疊疊樂的烏龜、他的妹妹、第一次學魔法、誤入歧途的魔法師……,回憶湧上心頭,多多流出了眼淚。「我……當然也想認識學妹啊!!!!!」

洞穴發出了強大的光芒,多多的魔法和王的電流強烈的碰撞,學妹之間的戰鬥已經一發不可收拾了。

魔法和電流的碰撞非常複雜,就算是王也不能輕鬆處理。

魔法和電流激烈交織出了一個序列,每個位置的能量強度能用一個整數表示,想要打敗對方,就必須仔細分析這個序列的內容。

我們就姑且稱這個序列為電魔序列吧!
電魔序列由一排魔法整數構成。分析一個電魔序列,我們會需要知道某個區間的「電魔指數」最大是多少,所謂的電魔指數,就是把連續一段魔法整數XOR起來。
根據魔法少女小向的研究,電魔序列有時候會有一段區間會發出光芒,光芒的亮度就是那個區間內的數字的最大的電魔指數,而知道這個亮度將有助於了解電魔序列,也就有可能打敗對手。

舉例來說,假設電魔序列長的像這樣「1 5 4 3 2 」。
區間 [1,2] 的最大電魔指數是 5,而區間 [2,5] 則是 7,因為你可以把 4 和 3 XOR起來得到 7 。

當然這種東西用大腦去計算大概只有周強和他的6500萬顆大腦做的到,平常遇到這種事情還是會交給魔法來計算,現在在聽這個故事的你,不如就來寫寫看吧!

Input Format

第1行有兩個整數 N,Q,代表電魔序列的長度,還有發光的次數。
第2行有 N 個整數 Ai,代表第 i 個魔法數字是多少。
接下來 Q 行,每行有兩個整數 Lj,Rj,代表第 j 個發光的區間是 [Lj,Rj]。

20%, $ 1 \leq N \leq 100, 1 \leq Q \leq 200 $
30%, $ 1 \leq N \leq 1000, 1 \leq Q \leq 2000 $
49%, $ 1 \leq N \leq 15000, 1 \leq Q \leq 15000 $
1%, $ 1 \leq N \leq 10^ 5, 1 \leq Q \leq 10^ 5 $

100%, $ 0 \leq Ai \leq 10^ 9, 1 \leq Lj \leq Rj \leq N $

Output Format

請輸出Q行,
對於每個發光的區間,輸出一行,包含一個整數代表發光的區間的亮度。

Sample Input

5 4
1 5 4 3 2
1 5
1 3
3 5
2 3

Sample Output

7
5
7
5

Hints

「哼……什麼二十年單身魔法師,也不過如此嗎……真是無趣……」王轉身,準備離開奄奄一息的多多。
「不……你錯了……」
「嗯?你說什麼?」
「你錯了,對於學妹……我不是不能……是不想!」
「就憑你……?你認識幾個學妹?你覺得你想就可以嗎?」
「殿仁·王……其實……我這次來……不是為了別的……只是……只是想要祝你生日快樂而已啊!!!」
「你說什—— >////<!!!!??....你.你你.你再說一次?!」
「我只是想祝你生日快樂啊!!!!!」
「你是白痴嗎!!!啊啊啊啊啊!!!」
「不!我一開始就想這麼說了,王,學妹什麼的,根本就不重要,跟我一起研究魔法吧!!!」
「嗚……!!!!!!!既然你這麼堅持的話……」

後來,世界上出現了兩位偉大的大法師,但那又是另外一個故事了。

Problem Source

題目:電人王
測資&敘述:果茶
2016/12/13 測資加強 增加一筆 $ 1 \leq N \leq 100000, 1 \leq Q \leq 100000 $

Subtasks

For Testdata: 0 ~ 0, Score: 20
For Testdata: 1 ~ 1, Score: 30
For Testdata: 2 ~ 2, Score: 49
For Testdata: 3 ~ 3, Score: 1
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1999 65536 262144
3 6000 131072 262144