2021
❤ 末日魔法少女计划
类似百万富翁。
💔 魔塔 OL
首先这是个经典贪心，做法就是先按 $b-a$ 从大到小排序，然后 $b-a>0$ 按 $a$ 从小到大排序，$b-a=0$ 随意，$b-a<0$ 按 $b$ 从大到小排序。
然后发现题目让你求一个四维偏序的东西，于是考虑 bitset。离线按上述方案排序，每个询问都对应一个 01 序列。按 $B$ 分块，可以 $O(\frac{n}{B})$ 求出对应 01 序列。考虑预处理 $2^B$ 个状态的方案，时间复杂度 $O(\frac{n2^B}{B})$。每次询问 $O(\frac{n}{B})$ 求得答案。$B$ 取 $\log n$，最终时间复杂度为 $O(\frac{n^2}{\log n})$。
基因编辑
若不合法，那么必有 $x’=x$ 或 $y’=y$，最终答案一定是 $x,y$ 都对应它能取到的最优解。
❤ 简单数据结构
发现经过一次操作一后的位置永远满足单调不降，操作一可以线段树二分加区间修改实现。其他位置对答案的贡献可以简单维护。找到这个时刻可以整体二分加凸包。时间复杂度 $O(n\log n)$。
还有一种不用整体二分的做法？算了，不懂。
❄ Datalab
可以做到两次询问。
❤ 随机游走
允许自环重边，那么肯定是加一条到 $1$ 的边，记每个点的出度为 $d_i$，最终答案为
有 $O(nm^2)$ 的简单 DP。打表发现极差 $\le 2$。
❄ 小明的树
将点亮的点记为黑点，考虑白点，由于根一定是白点，该树完美当且仅当白点形成一个连通块，此时贡献为相邻颜色不同的边的数量。这些信息都和根无关，可以简单维护。
❤ 出题高手
注意到 $a$ 随机生成，猜测最终答案的区间长度为根号级别，然后就可以做到 $O(n\sqrt{n})$。
类似随机游走，单调栈大小期望为 $O(\sqrt{n})$，考虑分治，处理 $[l,r]$ 求出 $mid$ 前后缀的单调栈，期望大小 $O(\sqrt{r-l+1})$，即有用的区间个数为 $O(r-l+1)$，即支配对总数为 $O(n\log n)$。然后扫描线可以做到 $O(\min(mn\log n,n\log^2n+m\log n))$。
分析
好像可以用 Sparre Andersen Theorem 转化为 $[-1,1]$ 的情况，然后直接算。
😪 扑克比大小
❄ 算术
考虑段数为 $2$ 的情况，最终得到 $k$ 合法当且仅当 $\gcd(b,p)=1$ 且 $b^{k+1} \equiv -1 \mod p$。这也是最终的充要条件。
$\gcd(b,p)=1$ 是好考虑的。同余 $1$ 是好考虑的，于是转化为 $b^{2k+2} \equiv 1 \mod p$，这是必要条件，这等价于 $\delta_p(b) | 2k+2$。
求阶
$\delta_p(a)$ 即为满足 $a^{x} \equiv 1 \mod p$ 的最小的正整数 $x$。
记当前为 $x$ 初始为 $\varphi(p)$， 枚举质因子 $v$，若 $a^{\frac{x}{v}} \equiv 1 \mod p$，那么 $x \gets \frac{x}{v}$，最终得到的 $x$ 即为 $\delta_p(a)$。
时间复杂度 $O(\log^2p)$。
那么需要满足 $\delta_p(b) | 2k+2,b^{k+1} \equiv -1 \mod p$。
- $\delta_p(b)$ 为奇数，$p=2$ 则答案为 $1$，否则无解。
- $\delta_p(b)$ 为偶数，$\delta_p(b)=2$ 则答案为 $2$，否则判断是否有 $b^{\frac{\delta_p(b)}{2}-1} \equiv -1 \mod p$ 得到答案。
时间复杂度 $O(\sqrt{p} + T \log^2 p)$。
2025
🍬 阿尔塔尔 2
答案 $\le 2$，证明就是找到出度最大的点 $a$，其出点集合为 $S$，入点集合为 $T$，若 $T$ 中存在点 $x$ 使得 $a$ 不能 $\le 2$ 步到达，那么 $x$ 出度至少为 $|S|+1$。
显然要随机，随机找到一个点 $a$，划分为 $S,T$，如果 $|T|=0$ 那么 $a$ 即为答案，否则答案一定在 $|T|$ 中，因为 $T$ 中的点可以 $\le 2$ 步达到 $a$ 和 $S$ 中的点，而前面证明一定有解，所以递归到 $T$ 即可。期望 $2n$ 次询问。
😪 颠倒歌
😪 路南柯
