Public NOIP Round #7

A

答案为 \(\sum\limits_{k \ge 0} \sum\limits_{i = 1}^n \sum\limits_{j = 1}^n [a_i + b_j \ge 10^k]\)。先把 \(a, b\) 排序，枚举 \(k\) 后双指针统计答案即可。时间复杂度 \(O(n (\log n + \log V))\)。

B

若 \(|a_i - a_j| = k\) 就在它们之间连一条无向边。因为保证序列没有相同元素所以图是若干条链。

容斥，相当于断开若干条边，然后把剩下的链拼接在一起，其中长度 \(\ge 2\) 的链要乘一个 \(2\) 的系数（顺序正着或者反着均可）。预处理出长度为 \(i\) 的链断成 \(j\) 条链的贡献系数，最后直接 DP 即可。

时间复杂度 \(O(n^2)\)。

C

考虑固定了 \(w, b\) 如何算 \(f(w, b)\)。不失一般性假设 \(w \ge b\)。

设 \(S\) 为必须是白色的点（其所有子树大小均 \(< w\)），分类讨论。

• 若 \(S \ne \varnothing\)，把 \(S\) 中的点删除后黑点只能在其中一棵子树内，\(f(w, b)\) 为大小 \(\ge b\) 的子树个数。
• 若 \(S = \varnothing\)，\(f(w, b)\) 只能为 \(1\) 或 \(2\)。\(f(w, b) = 1\) 当且仅当存在一个点，它有两棵子树 \(\ge w\)，另外还有一棵子树 \(\ge b\)。感性理解一下，若这个条件不满足那么黑色连通块相当于被白色连通块堵住了，要么在它前面要么在它后面，不可能跨过它，所以等价类数量为 \(2\)。

得到这个结论后计算答案是简单的。仍然分两类讨论。

• 若 \(S \ne \varnothing\)，从大到小枚举 \(w\)，并查集维护删除 \(S\) 后各个连通块的大小。线段树维护 \(\sum\limits b \times f(w, b)\) 即可。
• 若 \(S = \varnothing\)，我们预处理出每个点前三大的子树大小，然后算出第二大子树大小 \(\ge w\) 时第三大子树大小的最大值 \(t\)。那么 \(b \in [1, \min(t, w)]\) 时 \(f(w, b) = 1\)，\(b \in [\min(t, w) + 1, w]\) 时 \(f(w, b) = 2\)。

这样只计算了 \(\sum\limits_{w = 1}^{n - 1} \sum\limits_{b = 1}^{\min(w, n - w)} w \times b \times f(w, b)\)，把答案乘 \(2\)，最后减去 \(\sum\limits_{i = 1}^n i^2 f(i, i)\) 即可。

时间复杂度 \(O(n \log n)\)。

D

考虑 \(a_i \le 10\) 的部分分。

拆贡献，转 \(01\)，枚举一个 \(p\)，令 \(b'_i = [b_i \ge p]\)，把所有 \(p\) 的情况的 \(1\) 的个数求和即可。

差分，转化为计算 \(\sum\limits_{i = 1}^x a_i\)。

发现只有 \(01\) 的冒泡排序过程是非常好看的，大致形如每个 \(0\) 每轮都会往前移一格。所以我们不妨统计 \(0\) 的个数和。发现这个就是 \([l, \min(l + x + k - 1, r)]\) 中 \(0\) 的个数对 \(x\) 取 \(\min\)。

这个是很好用主席树算的。大概就是求出区间中第 \(r - l + 2 - x\) 大的数，设其为 \(t\)，那么 \(p \le t\) 时贡献为区间 \(0\) 的个数（这个等于 \(\sum\limits_{i = l}^r \max(t - a_i, 0)\)，可以主席树计算），\(p > t\) 时贡献为区间长度。

时间复杂度 \(O(n \log n)\)。