JOISC 2022 Day2 T1 「チーム戦 / Team Contest」
首先优先考虑选择各项属性最大的那个。如果一只海狸同时霸占多项属性的最大值，那么这只海狸是不可能产生贡献的，将它删掉，然后对剩下的海狸继续进行如下的操作。如果没有就直接输出答案。如果所有海狸都删完了，则无解。时间复杂度 \(O(n\log n)\)。（这只 \(\log\) 是排序的，后面的处理部分实际上是线性的）
JOISC 2022 Day3 T2 「スプリンクラー / Sprinkler」
这题的 trick 似乎十分有用。
考虑到 \(d_{\max}\) 非常小，我们可以每次进行 \(O(d)\) 的修改，具体如下：
将 \(x\) 的 \(d\) 和 \(d-1\) 位置的标记乘 \(w\)，将 \(x\) 父亲的 \(d-1\) 和 \(d-2\) 位置的标记乘 \(w\)，然后是二级祖先，三级祖先……直到将 \(x\) 的 \(d\) 级祖先的 \(0\) 位置的标记乘 \(w\)。具体的细节可以手玩。
那么查的时候查 \(x\) 在 \(0\) 处的标记，在 \(x\) 父亲的 \(1\) 处的标记……直到 \(d\) 级父亲的 \(d\) 处的标记。可以发现每次修改如果有贡献，那么仅有一次贡献且一定是合法的贡献。这个可以证明手玩出来。
时间复杂度 \(O(n+qd)\)。要注意的一点就是要在根上面再开 \(40\) 个节点来存标记。
[北大集训 2021] 基因编辑
比较显然的一道题。考虑有解的情况，实际上是一个动态 RMQ 问题，用线段树解决就好了。然而我听说有线性的解法。
[北大集训 2021] 算术
我们可以通过一些奇妙的方法证明出题目中的条件等价于 \(b^{k+1}\equiv -1\pmod p\)。它的必要条件是 \(b^{2k+2}\equiv 1\pmod p\)。
根据阶的性质，我们知道 \((2k+2)\) 是 \(\varphi(p)\) 的约数，那么先对 \(\varphi(p)\) 分解质因数，然后试除，最后再判断就可以了。时间复杂度 \(O(\sqrt p+T\log p)\)。
小 Y 和二叉树
找到中序遍历的第一个数 \(t\)（即最小的的树不超过 \(2\) 的点），然后向右拓展。从 \(x\) 拓展就是找原树以 \(t\) 为根，\(x\) 的子树内度数不超过 \(2\) 的最小的点，然后比较。注意这里的形态有两种，分别是儿子和父亲，要分别记录形态与其确定性，因为不同形态的转移方式可能不同。时间复杂度 \(O(n)\)。
标签：Set,log,标记,复杂度,Solution,然后,贡献,PKUSC,海狸 From： https://www.cnblogs.com/tulipenoire/p/17368232.html