本人太菜，实在不会 T3，所以只有 T1,T2 的题解。

注：考场上只做出来了 Day1 T1，其他题参考了其他人的题解。

Day1

T1 电池检测

题面

有 \(a\) 个有电的电池和 \(b\) 个没电的电池，每次只能选择两个电池放进手电筒，只有这两个电池全有电才能让手电筒启动。问最坏情况下最少可以让手电筒启动的尝试次数。
多测。
数据范围： \(2 \le a \le 10^3，1 \le b \le 10^3，1 \le T \le 10^3\)。

题解

如果我们选择了两个电池 \(u,v\)，我们就在他们之间连一条无向边。
每一个方案对应一个无向图。
如果这个方案不可行，就意味着每一条边的两个端点都至少有一个没电的点，也即有电的点之间没有边。
所以方案不可行等价于这个图的最大独立集 \(\ge a\)。

于是我们可以 dp，设 \(f_{i,j}\) 表示 \(i\) 个点的图，最大独立集为 \(j\)，的最少边数。
边界：\(f_{i,i}=0,f_{i,1}=C_i^2\)。
转移：如果 \(j>1\)，那么为了让边数最少，此时的图一定不连通，枚举其中一部分，\(f_{x,y}+f_{i-x,j-y} \to f_{i,j}\)。
答案：\(f_{a+b,a-1}\)。
这个 dp 是 \(O(n^4)\)。

然后你打个表可以发现最优的情况一定是：\(x=\lfloor \frac{i}{j} \rfloor,y=1\)。
所以就优化成了 \(O(n^2)\)。

T2 Ancestors

题面

给你一棵树，\(q\) 次询问 \(l,r,x\)，求有多少个点 \(u \in [1,n]\) 满足 \(u\) 是 \([l,r]\) 中其中一个点的 \(x\) 级祖先。
如果 \(u\) 不存在 \(x\) 级祖先，那他的 \(x\) 级祖先是 \(0\)。
数据范围： \(1\le l,r,x \le n \le 10^5，1\le q \le 10^6\)。

题解

我们肯定是统一处理 \(x\) 相同的询问。

设 \(f_{i}\) 表示目前 \(i\) 的 \(x\) 级祖先。
如果我们能求出 \(f_{i}\)，那么原问题就是一个区间数颜色，常见的作法是：
维护一个 \(pre_{i}\)，表示最大的满足 \(f_j=f_i\) 且 \(j<i\) 的 \(j\)，不存在的话 \(pre_i=0\)。
然后一个点 \(u\) 要对询问 \(l,r,x\) 产生贡献就是满足：\(l\le u \le r\) 且 \(pre_u < l\)。
对 \(pre_u\) 这一维扫描线，这样询问就只需要在树状数组上区间查询即可。
就是一个经典的二维偏序。

这个做法的好处是只需要维护 \(pre\) 数组就可以了。

因为题面规定了 \(x\) 级祖先为 \(0\) 的点不产生贡献，所以会互相影响的点一定在同一个深度。
如果我们把 \(x\) 级祖先相同的点放在一个集合，那么当 \(x\) 增大 \(1\) 就相当于要合并若干个集合。
容易证明将一个点插入一个集合只会最多修改两个点的 \(pre\)，那么我们在合并的时候采用启发式合并就能做到只有 \(O(n\log n)\) 次修改。

处理出这些修改可以先长剖（因为每个点的子树对不同的深度都要维护一个集合），然后合并轻子树的时候采用启发式合并就可以了，用 set 维护就是两个 \(\log\)。

现在只需要维护：\(O(n\log n)\) 次单点修改的动态二维偏序。
就等价于三维偏序，时间复杂度是三个 \(\log\)。

貌似是有两个 \(\log\) 的做法的，但是三个 \(\log\) 可过。
因为我没有写过，所以不知道要不要卡常，但是场上确实一车人跑步过去了。