944 . 異常原料偵測
TopCoder
Tags
Description
你是三角形工廠的一名員工，最近你們的工廠時不時會製造出奇怪的形狀，為了保障工廠的安全與名聲，你打算仔細調查異常事件出現的原因。
工廠產出的三角形是由正整數所組成的，每一個三角形都可以被一個正整數 $a_i$ 所表示，而我們說這個三角形的組成原料是 除了 1 和自己以外的正因數，精確的來說，一個三角形 $a_i$ 的原料集合為
$$
S = \lbrace d | 1 < d < a_i, d | a_i \rbrace
$$
同時每個三角形的原料中至少存在兩種以上的質數，也就是說 $a_i$ 至少有兩種質因數。
在追查三角形的原料時，你發現工廠發生異常的原因和一些異常的數字有關係，如果這些數字出現太多次，工廠就會故障，具體來說，在生產的三角形中，如果有種原料佔據所有原料個數的一半（含）以上，那麼工廠就會開始發生異常。
為了偵測工廠發生異常的情況，你想要能夠回答異常的原料是否有出現在一堆三角形之中，並將這些異常的原料找出來，也就是說，一開始先給定一堆三角形，你想要能夠維護下列操作：
- 給定一個三角形 $k_i$，將其加入到三角形堆之中
- 將一個三角形 $k_i$ 於三角形堆中移除（保證能夠在三角形堆中找到 $k_i$，若有多個 $k_i$ 只移除一個）
每次操作結束後，輸出任意一種異常原料，若沒有則輸出 $-1$
保證在過程中三角形堆裡永遠存在兩種以上的三角形。
Input Format
第一行輸入有兩個正整數 $n, q$，表示一開始三角形堆的大小和操作數量。
第二行有 $n$ 個正整數 $a_1, a_2 \cdots a_n$ 表示一開始三角形堆的樣子。
接下來 $q$ 行，每行包含兩個正整數 $t_i, k_i$
- 若 $t_i = 1$，表示此操作為將 $k_i$ 加入三角形堆中
- 若 $t_i = 2$，表示此操作為將一個三角形 $k_i$ 從三角形堆中移除。
在二種操作中，保證要刪除的三角形一定存在。
- $2 \leq n \leq 2\times 10^ 5$
- $1 \leq q \leq 2\times 10^ 5$
- $1 \leq a_i,k_i \leq 10^ {18}$ 保證 $a_i,k_i$ 都至少有兩種質因數
- 保證在操作中三角形堆中至少有兩種數字
Output Format
輸出 $q$ 個數字，每個操作之後輸出三角形堆中的任意一種異常原料，若沒有則輸出 $-1$。
Sample Input 1
3 3 6 10 14 1 14 1 12 2 12
Sample Output 1
2 -1 2
Sample Input 2
2 5 62 87 1 115 1 143 2 87 1 133 2 62
Sample Output 2
-1 -1 -1 -1 -1
Sample Input 3
2 5 21 33 1 6 1 15 1 33 1 45 1 14
Sample Output 3
3 3 3 -1 -1
Hints
在第一筆測試資料中，一開始的三角形堆中的原料為：
${ 2, 3, 2, 5, 2, 7 }$
在經過第一個操作後變成
${ 2, 3, 2, 5, 2, 7, 2, 7 }$
2 出現 4 次，所以他是異常原料，輸出 2
在經過第二個操作後變成
${ 2, 3, 2, 5, 2, 7, 2, 7, 2, 3, 6 }$
沒有原料佔據一半或以上，輸出 -1
其他以此類推
Problem Source
YTP 2025 高中組初賽 p8
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測試資料 | 0 |
| 2 | 3~18 | $t_i=1$ | 2 |
| 3 | 0~2, 19~38 | $1\leq a_i,k_i \leq 10^ 6$ | 4 |
| 4 | 0~2, 19~58 | $1\leq a_i,k_i \leq 10^ {12}$ | 6 |
| 5 | 0~78 | 無額外限制 | 8 |