B 10371: 平均

给定一个长为 $n$ 的序列 $a$，每次操作你可以选择一个数 $a_i$ 满足 $a_{i-1}, a_i, a_{i+1}$ 形成等差数列，将 $a_i$ 从 $a$ 中删除（不可以选择 $a_1$ 和 $a_n$）。 求最少剩几个数。 $n \le 3 \times 10^5$，$1 \le a_i \le 10^9$。

蓝题签到。

首先注意到问题只和 $a$ 的差分有关。令 $b$ 为 $a$ 的差分数组。

令 $k_i = \nu_2(b_i)$，按照 $c_i = \frac {b_i} {2^{k_i}}$ 分颜色段。（$\nu_2$ 写代码的时候可以写 __builtin_ctz）每个颜色段的问题是独立的。

称一个区间合法当且仅当整个区间能被合成一个数。

把精力放在 $k$ 数组上。抄 P3147 [USACO16OPEN] 262144 P 这个题的思路，令 $f_{i,j}$ 表示以 $j$ 为左端点来合成 $i$ 的右端点，转移 $f_{i,j} = f_{i-1,f_{i-1,j}}$，即对着 $j$ 套两次 $f_{i-1, *}$。对每个左端点处理出哪些右端点合法。

合法的区间个数是 $O(n (\log V + \log n))$ 很少，所以可以直接看怎么拼区间是区间数目最少。

总时间复杂度 $O(n (\log V + \log n))$。

A 10370: 排列

对于一个 $[1,n]$ 的排列 $f(p)$，

• $f(p)$ 是 $p$ 对应的置换环个数
• $g(p)$ 是 $i < p_i$ 的 $i$ 的个数

$ans_{i,j}$ 是 $f(p) = i$ 且 $g(p) = j$ 的 $p$ 的个数。求出整个 $n \times n$ 的 $ans$ 数组。

$n \le 500$。对大质数取模（大质数会变，无法打表）。

（以下用 $a += b$ 代表 $a \gets a + b$）

从小到大依次插入，把环上还没插入的部分看成一条边。每次插入要么开一个新环（自环），要么被插入到已有的某一个环中。

令 $f_{i,j,k}$ 为插入到 $i$ 这个点且 $f = j$ 且 $g = k$ 的方案数。

• 不在之前任何一个环，开一个环。
  • $f_{i,j,k} \gets f_{i-1,j-1,k}$
• 被插入到某一个环中，枚举在哪条边被插进去。
  • 每次插入必定是一条 $u < p_u$，一条 $u > p_u$。
  • 被删掉的那条边是哪种呢？分情况：
    • $f_{i,j,k} += f_{i-1,j,k} \times k$（$k$ 个 $u < p_u$ 的边可以断）
    • $f_{i,j,k} += f_{i-1,j,k-1} \times (i-k)$（$i-k$ 个 $u \ge p_u$ 的边可以断）。

$O(n^3)$。滚动数组卡一下空间。

C 10372: 最大独立集

给定一棵 $n$ 个点的树，点 $u$ 的点权为 $a_u$。给定 $m$ 组询问，每次询问给定 $u,k$，求距离 $u$ 不超过 $k$ 的点的最大独立集。

$1 \le n,m \le 2 \times 10^5$，$1 \le a_u \le 10^9$。离线。

TODO: 还没会！

邻域问题的套路。

如果只看子树而不是邻域，是长链剖分。

$f_{u,i}$ $u$ 为根，$i$ 是深度上限。（这是一个信息，不一定是整数）$f_{u,i}$ 可以由 $f_{v,i-1}$ 算出来，$v$ 是 $u$ 的儿子。

但是这是平方的，用长剖优化。

离叶子的距离叫做高度。长儿子只有一个，令 $v_0$ 为 $u$ 的长儿子。

$i$ 保留到高度即可。从长儿子继承信息。

$d$ 是除了长儿子以外的最大深度，$i>d$ 时，只有长儿子还在更新。

用一个线段树维护长儿子链。$O(n \log n)$。

回到原问题，Kubic：换根长剖

$g_{u,i}$ 外子树的信息。询问把 $f$ 和 $g$ 拼起来。

$O(n \log n)$