T2
官方题解：
考虑自底向上贪⼼
\(G(x,k)\) 表示 \(x\) 下面距离为 \(k\) 的需要灭⽕器的房间数，\(F(x,k)\)表示 \(x\) 下面距离为 \(k\) 的多余灭⽕器数
每个灭⽕器和房间的匹配在 lca 处处理
每次假设⼦树里已经最优了，那么 \(G(x,k)\) ⼀定要用 \(F(x,0)\)填满
然后距离为 \(k\) 的⼀定会在 \(x\) 处匹配掉，否则到上面不会更优（可以交叉互换）
在不存在距离为 \(k\) 的前提下，\(k-1\) ⼀定会在 \(x\) 处匹配掉否则可以交叉互换
根处 \(G\) 和 \(F\) 的匹配再做⼀个简单的贪⼼即可
T3
先写一个朴素的dp，设\(f(i,j)\)表示第\(i\)段走廊，灰尘量为\(j\)的最小时间。设\(F(j)\)表示第\(i\)段走廊的dp数组，\(G(j)\)表示第\(i-1\)段的dp数组。
首先显然有\(G(j)=f(i-1,j)\)，考虑到上一段走廊打扫完成后可以直接清空集尘盒，再做一个转移，\(G(0)=\min(G(0),\min_j G(j)+b)\)。
然后考虑本段走廊的转移，\(F((j+v_i) \bmod C)=G(j) + K \times a_i + (K-1) \times b + (a_i + b) \times [(j+v_i) \bmod C < j]\)，其中\(K=\lceil \frac{v_i}{C} \rceil\)。
最后显然\(f(i,j)=F(j)\)。
考虑数据结构优化这个dp，\(G(0)=\min(G(0),\min_j G(j)+b)\)就是查全局最小值。第二个转移如果不考虑中途集尘盒满了的情况（\((a_i + b) \times [(j+v_i) \bmod C < j]\)），那么就是把整个序列循环位移\(v_i\)，再整体加\(K \times a_i + (K-1) \times b\)。
如果考虑中途集尘盒满了的情况，也就是再来一次区间加。
但是正解\(C\)很大，如果动态开点也比较幽默，更好的方法是减少状态数。通过对上面那个dp的观察，我们发现如果不每次都从\(0\)开始，而是从\(X_i = \sum_{j=1}^i v_j \bmod C\)开始，反而不用每次进行循环位移，并且\(\lbrace X_i \rbrace\)就是最终用到的所有合法状态了。转移和上面差不多，就是做第\(i\)段走廊的转移的时候你都认为下标已经循环位移了\(X_i\)就行。只用全局最小值、区间加、整体加、单点修改这几个操作，数据结构选用线段树即可，时间复杂度\(O(n\log n)\)。
T4
算法 1
考虑如何求出一个序列的答案，我们先将所有 \(a_i\) 的值都增加 \(1\)，然后令 \(cnt_i\) 表示 \(a_j\le i\) 的 \(j\) 的数量。
结论：答案为 \(\max_{i=1}^{n}\{\lceil\frac{cnt_i}{i}\rceil\}\)。
证明：考虑对于一个答案 \(k\) 判断是否合法。我们构建一个二分图，左边 \(n\) 个点，流量为 \(cnt_i\)，右边 \(n\) 个点，流量为 \(k\)。\(\forall i\ge j\)，左边第 \(i\) 个点和右边第 \(j\) 个点之间都有 \(+\infty\) 的流量。那么如果此时最大流 \(=n\)。
由于最大流 \(=\) 最小割，所以我们考虑假设右侧割掉 \(i\) 个点。注意到由于编号小的点入边集合是编号大的点的超集，所以我们肯定会删右侧的前 \(i\) 个点，那么左侧 \(>i\) 的点需要割掉，于是需要满足 \(n-cnt_i+ik\ge n\)，即 \(cnt_i\le ik\)，所以 \(k\ge \frac{cnt_i}{i}\)。
于是，我们每次暴力求即可，时间复杂度 \(O(n^2)\)。
算法 2
我们考虑离线，按照值域扫描线。
我们根据最后取 \(i\) 时，对答案的贡献。
注意到由于只有 \(\frac{n}{i}\) 个断点，所以我们枚举第 \(j\) 个端点，相当于要维护：
\(O(n)\) 次插入；
\(O(n\log n)\) 次求第 \(ij\) 小。
使用树状数组倍增或线段树维护，时间复杂度 \(O(n\log^2 n)\)。
算法 3
我们还是考虑离线，按照值域扫描线。
我们还是根据最后取 \(i\) 时，对答案的贡献。
假设值为 \(i\) 的有 \(x_i\) 个数，那么，若 \(i\) 比 \(i-1\) 优，一定需要满足 \(\frac{a}{i-1}<\frac{a+x_i}{i}\)。
可以得到 \(a<x_ii-x_i\)，那么就说明 \(\frac{a+x_i}{i}<x_i\)。
所以对于 \(i\)，说明只有 \(x_i\) 个位置需要被更新，相当于要维护：
\(O(n)\) 次插入；
\(O(n)\) 次求第 \(ij\) 小。
使用树状数组倍增或线段树维护，时间复杂度 \(O(n\log n)\)。
算法 4
这是出题人没有想到的做法，是验题人以及几乎全部赛时通过选手的做法）
注意到答案是单调不降的，并且每次最多增加 \(1\)，所以我们可以动态维护答案的变化。
我们令 \(d_i\) 表示 \(\le i\) 的数再增加多少会使得答案增加 \(1\)（即 \(d_i = (-cnt_i) \bmod i\)）。那么答案增加 \(1\) 当且仅当 \(\exists d_i=0\)。每次当 \(i \to i + 1\)，假设 \(x = a_{i+1} + 1\)，则我们需要对 \(d[x, n]\) 这个后缀 \(-1\)。然后查询是否有 \(d_i = -1\) 的情况出现，如果出现则 \(ans \to ans + 1\)。
注意到假设当前答案为 \(ans\)，由于 \(cnt_i \le n\)，因此，想要出现 \(\frac{cnt_i}{i} > ans\) 的情况，则必然要求 \(i \le \frac{cnt_i}{ans} \le \frac{n}{ans}\)。因此只需要考虑 \(i \le \frac{n}{ans}\) 的 \(d_i\)（即线段树长度 \(\le \frac{n}{ans}\)），于是对于答案变化的情况，我们直接重构线段树即可。
时间复杂度 \(O(n\log n)\)。
算法 5（lrher）
首先考虑如果一个合法嵌套组的 \(a_i\) 必须互不相同 , 记 \(cnt_i\) 为 \(i\) 的出现次数 , 则答案为 \(\max cnt_i\)
对于存在 \(a_i\) 相同的合法嵌套组 , 把相同部分的任意一个相同的 \(a_i\) 变小 \(1\) , 会发现这个嵌套组依然合法 , 我们可以不断这样操作 , 直到 \(a_i\) 互不相同
于是问题就变成了对于 \(a\) 的每个前缀都要求 : \(a_i\) 可以变小且强制一个合法嵌套组的 \(a_i\) 必须互不相同，最少形成的合法嵌套组的组数
这样就可以比较优美的 \(check\) 一个答案是否合法 , 具体的记录一个变量 \(c\) 表示在值域上从大往小扫完 \(cnt_{i\ge x}\) 的时候 , 还有 \(c\) 个套娃因为 \(ans\) 的限制需要变小 , 从 \(n\) 扫到 \(1\) 之后就只需要知道 \(c\) 是否 \(=0\)
可以发现 \(ans\) 在套娃逐渐变多的过程中是单调不降的 , 且在每次加入一个套娃的时候最多 \(+1\)
考虑用值域线段树 , 第 \(i\) 个位置权值为 \(cnt_i\) 每次单点加 \(1\) , 维护 \(c\) 并且每次 \(check\ ans\) 是否 \(+1\) , 值域线段树每个节点维护从当前节点对应的区间 \([l,r]\) 从 \(r\) 扫到 \(l\) 的时候 \(c\) 的权值是多少 , 这个东西可以通过维护区间和 \(O(1)\) 合并 , 注意到一个区间要是最大值 \(\le ans\) , 那 \(c\) 的权值肯定为 \(0\) , 每次 \(ans\) 变大的时候重构整个线段树只需要遍历 \(cnt_i>ans\) 的位置 , 所有前缀遍历的位置个数总和最多是 \(\sum cnt_i=n\) , 于是时间复杂度为 \(O(nlogn)\) , 空间复杂度为 \(O(n)\) .