題目
pA
直播循環
一個直播循環是由 $s$ 天的直播時段和 $r$ 天的休息時間構成。
現有位直播主要進行 $n$ 個遊戲的直播，第 $i$ 個遊戲需在某個循環的第 $a_i$ 天遊玩。且每個遊戲直播之間須間隔至少 $r$ 天的休息日。
求最少需幾個直播循環才能至少玩過所有遊戲一遍，並輸出每個遊戲須在第幾個循環進行直播（輸入任一種安排方式）。
$n \leq 2 \times 10^5$
$0 \leq r \leq s \leq 10^9$
Subtask
pB
兔田彩券
給定 $m$ 個數對 $(a_i, b_i), a_i \neq b_i$，每個數對的數字皆 $\leq n$。
接著有 $q$ 筆詢問，每筆詢問給定 $(l, r, s, t)$，求有多少數對 $(a_i, b_i)$ 滿足 $(l \leq a_i \leq r \land s \leq b_i \leq t)$ 或 $(l \leq b_i \leq r \land s \leq a_i \leq t)$。
$1 \leq n \leq 2000$
$1 \leq m, q \leq 2 \times 10^5$
Subtask
pC
魔法師測驗
有一棵 $n$ 個節點的樹，每個節點有權重 $a_i$，求最長的路徑滿足路徑上的節點權重 $gcd \neq 1$，輸出該路徑的節點數。
$1 \leq n, a_i\leq 2 \times 10^5$
Subtask
pD
刷怪塔
有 $T$ 筆測資，每筆測資有兩個數字 $a, b$。
令 $s$ 初始為 $1$，定義一次操作如下：
- 選擇 $a, b$ 數字較大者（若相同則選擇 $a$），並將該數字減去 $s$。
- 將 $s$ 的值增加 $1$。
重複操作直到 $a, b$ 皆 $\leq s$。
輸出總操作次數。
$1 \leq T \leq 10^5$
$0 \leq a, b \leq 10^{18}$
Subtask
pE
時空旅人之爭
有一棵 $n$ 個節點的樹，自第 $0$ 秒開始，複製人便佔領節點 $1$，並且每隔 $2$ 秒往相鄰節點擴散。
接著有 $q$ 筆詢問 $(s, t)$，代表從節點 $s$ 開始經過最短路徑到達 $t$。時間從 $0$ 秒開始計算，每前往下一個節點需要 $1$ 秒。求這段路程中有多少節點已經被複製人佔領。
$1 \leq n, q \leq 2 \times 10^5$
Subtask
比賽結果
Score：135／Rank：3rd
比賽過程
開賽先下載所有題本，大概先花了15分鐘閱讀題本。
當時的難度排序：pA < pE < pC < pD < pB
pA 在紙上畫了一些圖後，馬上就想到 greedy+STL 就好了。
感覺這是最簡單的題目，沒什麼猶豫就寫下去了，刻模板 10 分鐘，但寫到後面才發現完了，我連 STL 的操作都不太熟悉，於是把 multiset 砍掉換成 map 才終於刻完。丟上去一發 AC。
00:35 pA 100分
接下來輪流想其他題目的作法。
pE 也是畫圖出來之後，很快想到 LCA+倍增二分搜，加上最近剛好有補到 LCA，所以我對實作滿有信心的，這題於是被我排在前面。
pC 感覺樹 DP，有觀察到每個數字的質因數不多，可是還是沒有複雜度好的想法，只有想到枚舉每個 $\leq 2\times 10^5$ 的質因數後套樹直徑。
pD 二分搜，但還要分一堆 case，非常麻煩，感覺寫下去了就會炸掉。
pB 有注意到 $n$ 特別小，除此之外沒任何想法，感覺是要寫線段樹或是莫隊，我對這種區間問題真的完全沒轍QQ。但是有 15 分是很水的暴力分，寫完 5 分鐘就丟上去了。
01:04 pB 15分
pD 的 20 分也很好水，先拿了簡單二分搜的 8 分，再拿暴力 12 分。
這裡比較雷的點是，明明 8 分的二分搜很好寫（大概兩分鐘就可以寫完），但我心態上一直覺得二分搜才 8 分感覺沒什麼價值，莫名地一直猶豫到底要不要寫，或是去想正解，拖一拖結果拖了 15 分鐘才拿掉。我到底在想什麼啊wwwwwwwwww
01:27 pD 20分
這時已經過半場，pC 樹 DP 依舊只有那個暴力的想法，這題子題切得很細但我完全沒有認真讀，很主觀地認為這個做法頂多 10~20 分，加上對於 pE 的滿分解太過自信，也沒想著要撈分就直接刻下去了。
LCA 的部分很順，5 分鐘就搞定，但最後的倍增二分搜沒有想清楚就直接寫，導致碰到一大堆 bug，碰一個 bug 就多加幾行特判處理，搞到最後 code 長得很肥。
好不容易範測過了，丟上去，結果
02:01 pE 0分
心中默念一聲幹之後回去好好看子題，結果我連一條鍊的測資都沒過。於是隨便生了一個鍊的測資，結果又找到更多問題，但我沒有打算重寫，反而是在那複雜的 code 上面又多加了更多的 if。看似解決了又丟上去。
02:16 pE 0分
糟糕，心態越來越不對，已經砸了 50 分鐘在這題了但我沒有收手，給自己停損點但都是給假的。一直很懊惱很不捨，寫了那麼長的 code 但一分也沒有，抱著「只要再修一下可能就可以 AC 了，現在放棄的話前面那一個小時就全都白費」這種斷不開的糟糕想法一直燒到比賽剩 20 分鐘。
02:27 pE 0分
02:37 pE 0分
這時候頭已經很脹痛，腦中思緒全部打結，心態上又一直很自責、懊悔，暴躁到敲了幾下鍵盤後去上廁所，但心情還沒完全平復就又回到電腦桌前。
這時候才開始寫 pC 的暴力分，順便加個唬爛剪枝（按照質因數出現的次數排序做樹直徑）。質數篩 + 質因數分解 + 樹直徑 DP 刻完大概剩 5 分鐘，結果測了範測，完了，是爛的。最後就盯著 code 盯到結束前 30 秒，很情感地把 code 丟了上去，想當然的一分都沒有。
02:59 pC 0分
賽後檢討
耍智障的地方真的太多了 = ="
- pA 居然刻到後面才發現不能用 multiset 而要用 map。
- pB 耍笨，套到二維平面上才發現只需要二維前綴和就行了，但我所有的思考過程全都在一維直線上，沒跳脫出來。
- pC 有兩個智障 bug。
- 我所有的 code 都是 1-based 的，但輸入數字的時候卻從 index 0 開始輸入。
- 樹 DP 有一段 code
關鍵在於不能馬上 return 而是要繼續 dfs，真是智障。1
2
3
4if (tag[u] == 0) {
dp[u] = 0;
return;
} - pE 爛在倍增二分搜，結果只是我沒有注意到我的寫法會讓指針跳到 LCA 上面。