What is the Codeforces Round #XXX problem set like?

本文共计1517个文字，预计阅读时间需要7分钟。

Codeforces 赛事预告

Codeforces Round #705 (Div. 2) 链接：codeforces.com/contest/1493 D ：GCD of an Array 题意：

给定一个长度为 \(n\) 的序列，\(q\) 次操作： 每次操作将 \(a_x\) 乘上 \(d\) 。每次操作完后询问全部数字的 \(gcd\)。

思路：

我们考虑使用线段树。对于每个节点，我们很容易想到维护其区间的 \(gcd\) 。但这其实是行不通的， 因为我们有至多 \(2e5\) 次操作， 每次最大又是乘上 \(2e5\)。显然会爆LL。但是我们可以分解质因数，以这样的形式储存信息，在上传到根节点时，将其再乘回原数， 输出即可。
所以我们对叶子节点，存储其对应数的分解质因数以后的形式。使用一个 \(map\) 来存储。 那么很显然，父亲存储的是两个儿子的 \(gcd\)， 在分解质因数的形式下， 也就是左右儿子的共同拥有的质因数, 且每个数取其中的最小值。那么我们就完成了建树。
我们考虑更新，只需要递归到叶子节点将其维护的信息修改即可。在上传信息时，只需要按建树时的逻辑，维护其父节点的信息即可。 但是此处我们一个优化 ：
显然我们在叶子节点更新信息时，只需要将乘上的数的分解质因子形式。也就是说，在原来的 \(map\) 中只有该数的质因子会被修改。那么在上传的时候同理， 并且由于另一个儿子和 \(gcd\) 的约束， 受到更新的信息只会越来越少，我们完全没有必要遍历每个节点的 \(map\)。