TopCoder

Caido
主唱太拼命了

User's AC Ratio

85.7% (6/7)

Submission's AC Ratio

28.2% (11/39)

Tags

Description

相信你一定知道 nim 和特徵值是什麼,如果不知道的話麻煩你去找早上的組合賽局導師道歉。

現在小 Y 和小 P 在玩 nim 的落葉版本。簡單來說就是找 N 棵行道樹,第 i 棵樹下有 ai 片落葉。之後他們會選擇一段編號連續的樹,把這些樹樹下的落葉當成一堆石頭來玩 nim。

可惜最近是東北季風的季節,落葉可能會被吹走,具體來說,如果有一陣強度是 ci 的風吹過 [li,ri],那麼這個區間內所有樹,樹下的落葉數量超過 ci 的部分會被吹走。

現在封一陣一陣的吹來,請隨時幫助小 Y 和小 P 計算,如果當下選擇某個區間的樹進行 nim 的特徵值是多少。

Input Format

第一行有兩個正整數 N,Q,代表行道樹以及事件的數量。

第二行包含 N 個正整數 a1,a2,,aN,代表第 i 棵行道樹下一開始有 ai 片葉子。

接下來的 Q 行形如以下兩者之一:

  • 0 l r c:表示有一陣強度是 c 的風吹過 [l,r] 這個區間。
  • 1 l r:詢問如果選擇 [l,r] 這個區間內的行道樹來玩 nim 的特徵值是多少。

資料滿足:

  • 1N,Q105
  • 1lrN
  • 1ai,c109

Output Format

對於每個詢問輸出一行,包含一個整數,代表該 nim 遊戲的特徵值。

Sample Input 1

3 5
1 2 1
1 1 3
1 1 2
0 1 2 1
1 1 3
1 1 2

Sample Output 1

2
3
1
0

Sample Input 2

3 5
1 2 1
1 1 3
1 1 2
0 1 2 3
1 1 3
1 1 2

Sample Output 2

2
3
2
3

Hints

Problem Source

IOICamp 2022 Day3 pG

Subtasks

No. Testdata Range Constraints Score
1 0~1 範例測資 0
2 0~24 無額外限制 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 262144 65536 1 2
1 2000 262144 65536 1 2
2 2000 262144 65536 2
3 2000 262144 65536 2
4 2000 262144 65536 2
5 2000 262144 65536 2
6 2000 262144 65536 2
7 2000 262144 65536 2
8 2000 262144 65536 2
9 2000 262144 65536 2
10 2000 262144 65536 2
11 2000 262144 65536 2
12 2000 262144 65536 2
13 2000 262144 65536 2
14 2000 262144 65536 2
15 2000 262144 65536 2
16 2000 262144 65536 2
17 2000 262144 65536 2
18 2000 262144 65536 2
19 2000 262144 65536 2
20 2000 262144 65536 2
21 2000 262144 65536 2
22 2000 262144 65536 2
23 2000 262144 65536 2
24 2000 262144 65536 2