a323. TOI 2019/05 潛力組：邏輯運算

題目描述

有 N 個整數，依序編號為 1 至 N。請依指令修改或查詢這些數字。每條指令的第一個數 α 決定操作：

• 0：結束。
• 1 P：輸出編號 P 的當前數值。
• 2 P Q：對編號為 P 倍數的所有元素，以該元素與 Q 的位元 AND 結果取代它。
• 3 P Q：對編號為 P 倍數的所有元素，以該元素與 Q 的位元 OR 結果取代它。
• 4 P Q：對編號為 P 倍數的所有元素，以該元素與 Q 的位元 XOR 結果取代它。

修改的依據是元素的編號是否為 P 的倍數，不是元素本身的數值。所有修改指令都出現在查詢指令之前；一旦開始輸出，就不會再修改元素。

輸入格式

第一行為 N，原題數值範圍為 0≤N≤10^6。第二行列出 N 個初始整數，範圍為 −2^31 至 2^31−1。

接著有 R 行指令，R≤25000，格式如題目描述，遇到 0 結束。R 本身並未另外列在輸入中。

分組：10 分滿足 0≤N≤10^2；30 分滿足 0≤N≤10^4；60 分滿足 0≤N≤10^6。

輸出格式

依查詢出現的順序，每行輸出對應編號的數值。

範例 1 把所有數與 0 做 AND，得到六個 0。範例 2 先清零，再將偶數編號設成 2147483647，最後全部與 2147483647 做 XOR，奇數編號得到 2147483647，偶數編號得到 0。

原題待釐清事項

• 原題稱 N 為正整數，但明列的數值界限及評分段落均允許 N=0；本稿保留0下界。
• 原題沒有另列指令參數 P、Q 的數值範圍，亦未明確說明負數位元運算的表示慣例；未自行補入限制。

本稿僅供待審，不自行修補以上規格。

範例 1

輸入：

6
1 2 3 4 5 6
2 1 0
1 1
1 2
1 3
1 4
1 5
1 6
0

輸出：

0
0
0
0
0
0

範例 2

輸入：

6
1 2 3 4 5 6
2 1 0
3 2 2147483647
4 1 2147483647
1 1
1 2
1 3
1 4
1 5
1 6
0

輸出：

2147483647
0
2147483647
0
2147483647
0

來源

TOI 2019/05 練習賽潛力組〈邏輯運算〉。依官方原題 PDF 自行整理，所有範例均取自原件。

原題連結：https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/201905/A3-Logic(Q).pdf