Source
好题:E、F
E
几乎是抄了一遍题解系列……
$$
\begin{aligned}
ans&=\sum_{i=1}^n ( \prod p_t^{\lfloor k_t/2 \rfloor} )=\sum_{i=1}^n ( i/\prod p_t^{\lceil k_t/2 \rceil} ) \\
&=\sum_{i=1}^n \sum_{j=1}^i[i|j^2]=\sum_{i=1}^n \sum_{j=1}^i \sum_{k=1}^{j^2} [ik=j^2] \\
&看到乘积为完全平方数,考虑最大公约数\\
&=\sum_{d=1}^n \sum_{i=1}^{n/d} \sum_{k=1}^i [gcd(i,k)=1] [i,k为完全平方数] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \sum_{k=1}^i [gcd(i^2,k^2)=1] \\
&=\sum_{d=1}^n \sum_{i=1}^{\sqrt{n/d}} \varphi(i^2)=\sum_{i=1}^n \varphi(i) \lfloor n/i^2 \rfloor
\end{aligned}
$$
F 黄金体验
有个不会证明但找不到反例的结论:k可以由k-1增量得到
那么如果静态的话,不难想到可以先求出k=2即带权直径,搞出一个端点作为根,然后k-1次找当前贡献最大的链并加入
仔细思考发现这东西本质上就是带权长剖,这种链的信息可以用lct来维护:
按照到根权值和从小到大access每个节点,得出带权长链,前k-1大长链之和就是答案
现在考虑怎么动态维护,更改一个节点,那么唯一的改动就是向上的长链
可以类似access那样,直到无法从轻儿子变为重儿子,这个过程中会有一系列长链的权值改动,要用segt维护
还有一个问题就是修改以后带权直径会变,但考虑到新的根可以从新带权直径任意一个端点中选择
而新直径一定会保留原本直径中的某个端点,以那个为根的话长链的结构是没有变化的,这方面在access的时候特判就好了
时间复杂度为 $O(qlog^2n)$
代码好写归好写,花了一上午,一个错误调一年
1 |
|