22 . 我推的盤子
TopCoder
Tags
Description
叉叉李同學覺得上課實在是太無聊了，作為新竹人的他決定開始玩新竹人最喜歡的盤子打發時間。他在桌上放了排成一列的 $N$ 個盒子，每個盒子裡都能裝一疊盤子，每個盤子有不同顏色，盤子的顏色以一個 $[0, 2^ {32})$ 範圍內的整數表示。一開始所有盒子都是空的，接下來的 $Q$ 堂課，叉叉李同學每堂課都會進行以下兩種活動的其中之一：
- 選一個區間 $[l, r]$，對於從左邊數來第 $l, l + 1, \dots, r$ 個盒子，他在每個盒子裡都推一個盤子到最上面，新盤子的顏色是 $x$。
- 選擇從左邊數來第 $p$ 個盒子，欣賞他推的盤子們並評估他們的「有趣度」。如果盒子裡的所有 $k$ 個盤子當中，每個盤子的顏色分別依序是 $x_1, x_2, \dots, x_k$，那他們的有趣度會是 $\sum_{i = 1}^ {k - 1} x_i \oplus x_{i + 1} = (x_1 \oplus x_2) + (x_2 \oplus x_3) + \dots + (x_{k - 1} \oplus x_k)$，其中 $\oplus$ 符號為 exclusive or。
然而上課時間有限，比起欣賞他推的盤子，叉叉李更想趕緊下課回家看最新一話的我推的孩子。你能幫他算一算盤子們的有趣度是多少嗎？
Input Format
輸入第一行是兩個以空白分隔的整數 $N$、$Q$，分別代表叉叉李有幾個盒子、以及接下來有幾堂課。
接下來 $Q$ 行，第 $i$ 行會是以下兩種之一：
- $1\,l\,r\,x$，代表叉叉李要在第 $i$ 堂課進行第一種活動，對 $[l, r]$ 區間內的盒子都推一個盤子。
- $2\,p$，代表叉叉李要在第 $i$ 堂課進行第二種活動，想計算目前第 $p$ 個盒子裡所有盤子的有趣度。
- $1 \le N, Q \le 10^ 6$
- $1 \le l \le r \le N$
- $0 \le x < 2 ^ {32}$
- $1 \le p \le N$
Output Format
對於每次第二種活動，輸出一行一個整數代表答案。
Sample Input 1
5 8
2 3
1 1 3 5
1 5 5 2
2 3
1 2 5 3
2 3
2 4
2 5
2 3
1 1 3 5
1 5 5 2
2 3
1 2 5 3
2 3
2 4
2 5
Sample Output 1
0
0
6
0
1
0
6
0
1
Hints
Problem Source
IOICamp 2024 Day2 pE
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0 | 範例測資 | 0 |
| 2 | 0~5 | $N, Q \le 5000$ | 10 |
| 3 | 0~10 | 無額外限制 | 90 |