本人太菜，實在不會 T3，所以只有 T1,T2 的題解。

注：考場上只做出來了 Day1 T1，其他題參考了其他人的題解。

Day1

T1 電池檢測

題面

有 \(a\) 個有電的電池和 \(b\) 個沒電的電池，每次只能選擇兩個電池放進手電筒，只有這兩個電池全有電才能讓手電筒啟動。問最壞情況下最少可以讓手電筒啟動的嘗試次數(shù)。
多測。
數(shù)據(jù)范圍： \(2 \le a \le 10^3，1 \le b \le 10^3，1 \le T \le 10^3\)。

題解

如果我們選擇了兩個電池 \(u,v\)，我們就在他們之間連一條無向邊。
每一個方案對應(yīng)一個無向圖。
如果這個方案不可行，就意味著每一條邊的兩個端點都至少有一個沒電的點，也即有電的點之間沒有邊。
所以方案不可行等價于這個圖的最大獨立集 \(\ge a\)。

于是我們可以 dp，設(shè) \(f_{i,j}\) 表示 \(i\) 個點的圖，最大獨立集為 \(j\)，的最少邊數(shù)。
邊界：\(f_{i,i}=0,f_{i,1}=C_i^2\)。
轉(zhuǎn)移：如果 \(j>1\)，那么為了讓邊數(shù)最少，此時的圖一定不連通，枚舉其中一部分，\(f_{x,y}+f_{i-x,j-y} \to f_{i,j}\)。
答案：\(f_{a+b,a-1}\)。
這個 dp 是 \(O(n^4)\)。

然后你打個表可以發(fā)現(xiàn)最優(yōu)的情況一定是：\(x=\lfloor \frac{i}{j} \rfloor,y=1\)。
所以就優(yōu)化成了 \(O(n^2)\)。

T2 Ancestors

題面

給你一棵樹，\(q\) 次詢問 \(l,r,x\)，求有多少個點 \(u \in [1,n]\) 滿足 \(u\) 是 \([l,r]\) 中其中一個點的 \(x\) 級祖先。
如果 \(u\) 不存在 \(x\) 級祖先，那他的 \(x\) 級祖先是 \(0\)。
數(shù)據(jù)范圍： \(1\le l,r,x \le n \le 10^5，1\le q \le 10^6\)。

題解

我們肯定是統(tǒng)一處理 \(x\) 相同的詢問。

設(shè) \(f_{i}\) 表示目前 \(i\) 的 \(x\) 級祖先。
如果我們能求出 \(f_{i}\)，那么原問題就是一個區(qū)間數(shù)顏色，常見的作法是：
維護一個 \(pre_{i}\)，表示最大的滿足 \(f_j=f_i\) 且 \(j<i\) 的 \(j\)，不存在的話 \(pre_i=0\)。
然后一個點 \(u\) 要對詢問 \(l,r,x\) 產(chǎn)生貢獻就是滿足：\(l\le u \le r\) 且 \(pre_u < l\)。
對 \(pre_u\) 這一維掃描線，這樣詢問就只需要在樹狀數(shù)組上區(qū)間查詢即可。
就是一個經(jīng)典的二維偏序。

這個做法的好處是只需要維護 \(pre\) 數(shù)組就可以了。

因為題面規(guī)定了 \(x\) 級祖先為 \(0\) 的點不產(chǎn)生貢獻，所以會互相影響的點一定在同一個深度。
如果我們把 \(x\) 級祖先相同的點放在一個集合，那么當 \(x\) 增大 \(1\) 就相當于要合并若干個集合。
容易證明將一個點插入一個集合只會最多修改兩個點的 \(pre\)，那么我們在合并的時候采用啟發(fā)式合并就能做到只有 \(O(n\log n)\) 次修改。

處理出這些修改可以先長剖（因為每個點的子樹對不同的深度都要維護一個集合），然后合并輕子樹的時候采用啟發(fā)式合并就可以了，用 set 維護就是兩個 \(\log\)。

現(xiàn)在只需要維護：\(O(n\log n)\) 次單點修改的動態(tài)二維偏序。
就等價于三維偏序，時間復(fù)雜度是三個 \(\log\)。

貌似是有兩個 \(\log\) 的做法的，但是三個 \(\log\) 可過。
因為我沒有寫過，所以不知道要不要卡常，但是場上確實一車人跑步過去了。

Day2

先擱一會。