P5901 regions

按颜色数量进行根号分治。离线下来，对于出现次数 $\le \sqrt n$ 的点作为下方点的情况，我们处理出这个点到根路径上每种颜色数量，那么对于一次询问，我们只会在这个询问的下方点进行一次询问，这里下方点数量是 $O(\sqrt n)$ 的。然后考虑出现次数 $> \sqrt n$ 的点作为下方点。对于每个点处理出子树内的出现次数 $> \sqrt n$ 的点的数量，然后从每个上方点查询即可。每个点最多只会进行 $O(\sqrt n)$ 次这种询问。复杂度就是 $O(n\sqrt n)$。

但是还需要考虑空间复杂度。每个点都算一下当前子树中大点的出现次数空间会是 $O(n\sqrt n)$ 在这题会被卡死，所以我们可以先减去当前这些点的出现次数，再加上遍历结束后的出现次数。

空间 $O(n)$ 时间 $O(n\sqrt n)$。

10.28 提高组模拟赛 T4

四元环计数，裸题。

四元环计数和三元环做法基本一样，钦定一个点作为最小点，枚举这个点一个出边，再枚举出去后的这个点的出边，两次必须保证编号大于开始点，然后打 tag 即可。

用 lower_bound 实现的，复杂度是 $O(n\log n + n\sqrt n)$ （默认边和点同阶）。

可以开始把图建好，小的点连向大的点，其实是一样的。

10.28 T3 牛牛的凑数游戏

水题。结论大概是前面一段的和 $+1$ 如果小于下一个位置的值，那么这个和加一就是最小的不可被表示的数。可以方便地归纳证明。

正解用了一个迭代然后主席树或者 BIT ，其实可以按位维护，对每个位维护出最小的两个数以及这个位为最高位的所有数的和。不难发现答案只会再这些情况中产生，因为同一个位中的两个数加起来必然会爆到下一位。

10.28 T4 牛牛的RPG游戏

套路题。先 cdq 一下，每次割长的那个边，然后相当于把一条加入凸包再查询一条的答案。这个东西斜率和截距貌似都没啥规律，直接上李超树即可。复杂度两个 $\log$ 。

也可以用 BIT 套李超树整过去，复杂度一样，实际上还快一点。

然后这题每次加入一层来做也可以。。因为对 $n,m$ 大小交换后就只有 $O(\sqrt n)$ 级别了。。数据范围太小暴力没卡掉。

CF480E

有修改，考虑分治。每次选择较长边切开，然后考虑维护跨过中线的最大正方形。

这个东西可以双指针 + 单调队列维护。每次修改复杂度是 $T(n) = T(\frac n 2) + O(n)$ 也就是 $O(n)$ 级别的。所以总的复杂度是 $O(n^2)$。

Hunger Game

最开始的时候，开着的箱子异或为 $0$ 。

如果不存在一个子集异或为 $0$ ，那么先手操作一次后后手通过 nim 游戏的操作一定可以使得开着的箱子的异或为 $0$ 。然后就回到了最初的状态。

否则，如果存在这样的子集，假设先手拿了一个子集异或为 $0$ 后，后手仍然可以拿一个子集使得异或为 $0$ 那么先手其实可以直接拿这两个集合的并。于是拿了一个极大的集合，后手就没异或为 $0$ 的可以拿了，回到了上一种情况。

所以，一旦开始存在一个子集异或为 $0$ ，先手必胜，否则后手必胜。