NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
175 . 落葉賽局
TopCoder
Tags
Description
相信你一定知道 nim 和特徵值是什麼，如果不知道的話麻煩你去找早上的組合賽局導師道歉。
現在小 Y 和小 P 在玩 nim 的落葉版本。簡單來說就是找 $N$ 棵行道樹，第 $i$ 棵樹下有 $a_i$ 片落葉。之後他們會選擇一段編號連續的樹，把這些樹樹下的落葉當成一堆石頭來玩 nim。
可惜最近是東北季風的季節，落葉可能會被吹走，具體來說，如果有一陣強度是 $c_i$ 的風吹過 $[l_i, r_i]$，那麼這個區間內所有樹，樹下的落葉數量超過 $c_i$ 的部分會被吹走。
現在封一陣一陣的吹來，請隨時幫助小 Y 和小 P 計算，如果當下選擇某個區間的樹進行 nim 的特徵值是多少。
Input Format
第一行有兩個正整數 $N,Q$，代表行道樹以及事件的數量。
第二行包含 $N$ 個正整數 $a_1, a_2, \ldots, a_N$，代表第 $i$ 棵行道樹下一開始有 $a_i$ 片葉子。
接下來的 $Q$ 行形如以下兩者之一：
- $0 \ l \ r \ c$：表示有一陣強度是 $c$ 的風吹過 $[l, r]$ 這個區間。
- $1 \ l \ r$：詢問如果選擇 $[l, r]$ 這個區間內的行道樹來玩 nim 的特徵值是多少。
資料滿足：
- $1\le N, Q\leq 10^ 5$
- $1\le l \le r \le N$
- $1\leq a_i,c\leq 10^ 9$
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
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
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
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
3
2
3
Hints
Problem Source
IOICamp 2022 Day3 pG
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~1 | 範例測資 | 0 |
| 2 | 0~24 | 無額外限制 | 100 |