TopCoder

User's AC Ratio

85.7% (18/21)

Submission's AC Ratio

37.3% (50/134)

Tags

Description

你玩過植物大戰殭屍嗎?

這是一款用植物打趴殭屍的熱門遊戲,已經紅了一段時間了。

在遊戲中,不同的植物可能相互作用,產生類似「合體技」的功能。這題的主要目標就是探討如何安排這些植物才能達到最大的攻擊力。為了簡化問題,我們只考慮只有一個殭屍以及田地只有一列的情況。

一列有$N$格的田地由左至右編號為$0,1,\dots,N-1$,每格田地的肥沃度是$a_i$。共有$Q$個關卡,而且每一個關卡都只有一個殭屍,並且進行的場地(也就是你能種植物的地方)是$N$格田地中的某一個區間$[L,R)$。而在每一關,你只有一個工具可以用:播種機。這是一個一次性道具,使用方法就是把他放在某一格落在區間內的田地,之後他會開始往右開,並且在所經過的田地都種下一顆種子(含起點)。播種完(也就是超過編號R的田地)之後,還會直接輾過殭屍造成一定的傷害。而對於某個已種下種子且肥沃度是$a_i$的格子,過了一小段時間之後就會長出「特徵值」是$a_i$的植物。所種出的植物會發動合體技,產生一顆種子子彈。這顆種子子彈的特徵值就是將所有植物的特徵值xor起來後的結果,並且這顆種子子彈會筆直地朝殭屍射過去,造成傷害。傷害的計算方法也非常容易,就是將種子子彈的特徵值和殭屍的特徵值$v$ xor後得到的結果。

對於給定的$Q$個關卡,請計算你能造成的最大傷害。

Input Format

第一行有兩個正整數$ N\leq 10^ 4, Q\leq 10^ 6$,分別代表田地大小以及關卡數目。
第二行有$N$個整數$0\leq a_0,a_1,\dots,a_{N-1}<2^ {30}$,代表每格田地的肥沃度。
接下來的$Q$中每行會有三個非負整數$L_i, R_i \leq N, v < 2^ {30}$($L_i<R_i$),分別代表關卡進行場地的左右界以及殭屍的特徵值。

子任務(測資) 額外限制 分數
1 (0~4) $Q\leq 10^ 4$ 7
2 (5~7) 肥沃度、$v<2^ {17}$ 31
3 (8~10) 62

Output Format

對於每個關卡,請輸出能造成的傷害最大值。

Sample Input

4 2
0 2 1 3
0 3 3
2 4 1

Sample Output

2
3

Hints

對於第一個關卡,將播種機放在第2格是最佳方案。
對於第二個關卡,將播種機放在第2格是最佳方案。

輸入很大,若使用C++輸入請記得加上ios_base::sync_with_stdio(false); cin.tie(0);,並將輸出時的endl替代為\n

Problem Source

Problem set / Description by Paupière

Subtasks

For Testdata: 0 ~ 4, Score: 7
For Testdata: 5 ~ 7, Score: 31
For Testdata: 8 ~ 10, Score: 62
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 262144
1 1000 65536 262144
2 1000 65536 262144
3 1000 65536 262144
4 1000 65536 262144
5 1000 65536 262144
6 1000 65536 262144
7 1000 65536 262144
8 2000 65536 262144
9 2000 65536 262144
10 2000 65536 262144