美妙集训。
day1
https://www.becoder.com.cn/contest/5894
A
用支持全局加 1 的 Trie 维护每个点的所有儿子的情况，父亲单独看。
B
观察、打表发现一棵满二叉树的 sg 等于层数的 lowbit。
C
D
E
问题等价于平面上有若干 \([a,b]\times[b,c](a\le b\le c)\) 的带权矩形，求覆盖某个点的所有矩形的权值最大值。
如果没有强制在线我有至少 5 种方法搞定这玩意。
再次转化为对于一组 \(x,y\)，求在 \([1,x]\times[x,y]\times[y,n]\) 范围内点权的最大值，然后 3-d tree。
F
用 2-d tree 的错解：
开一个恒容的堆维护目前的前 \(k\) 大，然后枚举每一个点，在树上递归，如果某棵子树内不可能更新答案就跳过。
正解：
考虑先找出最远点对，然后用其余所有点与它们的 \(2n-1\) 条边更新答案，再把这两个点删去。重复 \(k\) 次。
显然我们这 \(k\) 次找出来的最远点对不会重复，也就是说现在剩下的所有边的长度都不超过这 \(k\) 条选出的直径，它们自然无法更新答案。
day2
https://www.becoder.com.cn/contest/5897
A
B
C
对每个点，求出子树内最多可以选多少个人，但是自己启发式合并 priority_queue M了，所以打左偏树。
D
发现可以用矩阵维护分子分母的变化，然后发现 \(\begin{bmatrix}a+1&1\\1&0\end{bmatrix}=\begin{bmatrix}a&1\\1&0\end{bmatrix}\times\begin{bmatrix}1&0\\1&1\end{bmatrix}\)，也就是说可以用矩阵表达 W 对数列 \(a\) 的影响。
然后类比发现 \(\begin{bmatrix}2&1\\-1&0\end{bmatrix}\) 可以表达 E。
然后 fhq 维护就可以了
标签：begin,end,省选,然后,times,2025,bmatrix,集训 From： https://www.cnblogs.com/Miss-Grisses/p/18627117