Problem solutions

记一些有趣的题。

Codeforces 915F Imbalance Value of a Tree

题意:给一棵大小为 $n$ 的无向树 $(1 \leq n \leq 1e6)$,树上每个点有权值 $a_i (0 \leq a_i \leq 1e6)$。定义 $I(x, y)$ 为 $x$ 到 $y$ 路径上的最大值减去最小值,求 $\sum_{i=1}^{n} \sum_{j=i}^{n} I(i, j)$ 。

题解:显然,问题可以转换为,求树上所有路径的最大值之和减去最小值之和,分别求出这两个和即可。下面考虑求最大值。

定义 $t(i)$ 为一棵以 $i$ 为根的树,树上所有点与 $i$ 相邻,或者与 $t(i)$ 上的点相邻,且权值小于 $a_i$。可以知道,$i$ 对答案的贡献产生在这棵树中。计算 $i$ 的贡献时,依次遍历 $i$ 的子树,计算当前子树与 $i$ 以及之前添加的子树产生的答案,然后将此子树并入 $i$。

我们可以用一个并查集实现上述过程。初始化并查集,将所有点从小到大排序,然后遍历。访问点 $u$ 时,遍历所有与 $u$ 相邻,且之前已经被访问过的点。对于一个满足条件的点 $v$,计算 $v$ 所在并查集与 $u$ 所在并查集产生答案,然后合并 $u$ 和 $v$。

Codeforces 915G Coprime Arrays

题意:对数组 $a$,如果 $gcd(a_1, a_2, ..., a_n) = 1$,称其 $coprime$。给出 $n$ 和 $k$,求出满足 $i < k$,使得大小为 $n$ 的数组内所有元素 $a_j < i$ 且满足 $coprime$ 的数组个数。

题解:求满足 $x < n, y < n$ 且 $gcd(x, y) = 1$ 的个数是个著名的容斥原理 / 莫比乌斯反演问题。这道题同样可以通过莫比乌斯反演解决。

定义 $f(x) \equiv gcd(a_1, a_2, ..., a_n) = x 的 a 的个数$,$F(x) \equiv x | gcd(a_1, a_2, ..., a_n) 的 a 的个数$,则易知 $F(x) = \frac{i}{x}^{n} = \sum_{x|d}f(d)$,莫比乌斯反演可得 $f(x) = \sum_{x|d} \mu(\frac{d}{x})(\frac{i}{d})^{n}$。

要求出答案,则是求 $f(1) = \sum_{i=1}^{k} \sum_{d=1}^{i} \mu(d)(\frac{i}{d})^{n} = \sum_{d=1}^{i} \mu(d) * g(i)$。暴力求 $g(i)$ 肯定会超时。注意到,对 $g(i)$ 中每一项 $\frac{i}{d}$,只有在 $d | i$ 时才会变化,所以每次处理 $i$ 的因数即可。

Codeforces 911G Mass Change Queries

题意:给一个长度为 $n$ 的数组 $a$,进行 $q$ 次操作,每次操作 $l, r, x, y$ 将区间 $[l, r]$ 内的所有 $x$ 变为 $y$。求 $q$ 次操作后的数组。

题解:线段树,节点存 $val[100]$,表示每个值被映射的值。(也可以压位分块。)

TODO:感觉还有其他厉害的做法,线段树跑得有点慢。

Codeforces 920G List Of Integers

题意:定义 $L(x, p) \equiv 满足 y_i > x 且 gcd(p, y_i) = 1 的升序序列 y$。$L(x, p)$ 为下标从 $1$ 开始的序列。给出 $t (1 \leq t \leq 30000)$ 组询问,每次询问给出 $x, p, k (1 \leq x, p, k \leq 1000000)$,求 $L(x, p)$ 的第 $k$ 个元素。

题解:容斥原理可以求出小于 $t$ 且与 $p$ 互素的数的个数。小于 $x$ 的满足条件的个数为常数,加上这一部分后,二分答案,可以找出第 $k$ 个元素。