22 . 我推的盤子

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

96.4% (53/55)

Submission's AC Ratio

39.1% (75/192)

Tags

ioicamp ioicamp-2024

Description

叉叉李同學覺得上課實在是太無聊了，作為新竹人的他決定開始玩新竹人最喜歡的盤子打發時間。他在桌上放了排成一列的 N 個盒子，每個盒子裡都能裝一疊盤子，每個盤子有不同顏色，盤子的顏色以一個 [0,232) 範圍內的整數表示。一開始所有盒子都是空的，接下來的 Q 堂課，叉叉李同學每堂課都會進行以下兩種活動的其中之一：

  1. 選一個區間 [l,r]，對於從左邊數來第 l,l+1,…,r 個盒子，他在每個盒子裡都推一個盤子到最上面，新盤子的顏色是 x。
  2. 選擇從左邊數來第 p 個盒子，欣賞他推的盤子們並評估他們的「有趣度」。如果盒子裡的所有 k 個盤子當中，每個盤子的顏色分別依序是 x1,x2,…,xk，那他們的有趣度會是 ∑i=1k−1xi⊕xi+1=(x1⊕x2)+(x2⊕x3)+⋯+(xk−1⊕xk)，其中 ⊕ 符號為 exclusive or。

然而上課時間有限，比起欣賞他推的盤子，叉叉李更想趕緊下課回家看最新一話的我推的孩子。你能幫他算一算盤子們的有趣度是多少嗎？

Input Format

輸入第一行是兩個以空白分隔的整數 N、Q，分別代表叉叉李有幾個盒子、以及接下來有幾堂課。
接下來 Q 行，第 i 行會是以下兩種之一：

  • 1lrx，代表叉叉李要在第 i 堂課進行第一種活動，對 [l,r] 區間內的盒子都推一個盤子。
  • 2p，代表叉叉李要在第 i 堂課進行第二種活動，想計算目前第 p 個盒子裡所有盤子的有趣度。
  • 1≤N,Q≤106
  • 1≤l≤r≤N
  • 0≤x<232
  • 1≤p≤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

Sample Output 1

0
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≤5000 10
3 0~10 無額外限制 90

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 262144 65536 1 2 3
1 3000 262144 65536 2 3
2 3000 262144 65536 2 3
3 3000 262144 65536 2 3
4 3000 262144 65536 2 3
5 3000 262144 65536 2 3
6 3000 262144 65536 3
7 3000 262144 65536 3
8 3000 262144 65536 3
9 3000 262144 65536 3
10 3000 262144 65536 3
Submit
Back to Top