A. 羊圈

有一个图, $n$ 个点, 初始无边, 给定 $q$ 次操作, 每次要不加入一条边, 要不给定 $k$ 进行询问: 初始所有点为白色, 把所有相邻白点个数 $\le k$ 的点染黑, 求最后黑点个数 (询问互相独立). $n,q\le10^5$.

注意到有效的 $k\le O(\sqrt q)$, 对每个 $k$ 分别处理, 从后往前考虑, 对每个点计算出会在那个点删除. 具体来说, 用 queue 维护, 不断删除度数 $\le k$ 的节点, 每个点被删除时考虑所有未被删除的邻居. 时间复杂度 $O(n\sqrt n)$.

B. 酱油面

给定一棵树, 每个节点有一个初始为 $1$ 的指针 $c_u$, 从 $1$ 开始遍历, 当前到达 $u$, 那么 $c_u\gets (c_u+deg_u)+1$, $u\gets G_{u}(c_u)$, 其中 $G_u(i)$ 表示 $u$ 的第 $i$ 个邻居 (父亲为其中任意一个). 若干次强制在线的询问, 问遍历了 $k$ 个节点时所在节点. $n\le 5\times 10^5,k\le 10^{15}$.

首先通过 rotate $G_u(i)$ 让 $c_u$ 初始为 $0$. 注意到从 $u$ 到 $fa_u$, 那么有 $c_u=j,\ G_u(j)=fa_u$, 且每次遍历经过的节点时原树的一部分的欧拉徐. 当从 $1$ 开始遍历若干遍后, 会有 $\forall u\neq 1:G_u(c_u)=fa_u$ 时, 之后 $1$ 开始遍历会产生该树的一个欧拉序. 考虑在这之前, 对于每个节点 $u$ , 处理出会在 $ti_u$ 次遍历时第一次经过 $u$, 有 $v=G_u(i)\neq fa(u), ti_v=ti_u+[i\gt j], G_u(j)=fa_u$. 那么在 $ti_u$ 轮及以后, $u$ 和 $fa_u$ 会加入欧拉序. 考虑用主席树来维护每一轮. 时间复杂度 $O(n\log n)$.

C. 湖心石

给定序列 $a$, 定义二元运算 $z=s(x,y)$, 有 $z_i=s_i(x_i,y_i)$, 其中 $s_i$ 与, 或, 异或三者之一, $x_i$ 表示 $x$ 的第 $i$ 位. $q$ 次询问, 给定 $s_i$ 和 $x$, 求有序对 $(i,j)$ 的个数, 满足 $s(a_i,a_j)=x$. $n,q\le 10^5, a_i,x\le 2^{16}$.