「lych_cys模拟题2018」橘子树

Posted on 2023-08-12 Edited on 2024-04-19 In CP 题解

设值域上限为 \(M=2\cdot 10^5,T=3\cdot 10^5\)

筛去 \(n^{\frac{1}{3}}\) 以内的质因数，此时 \(n\) 剩下的质因数 \(>n^{\frac{1}{3}}\)

剩下的 \(n\) 中，可能出现贡献的只有 \(n\) 是完全平方数的情况， \(O(1)\) 判断即可

复杂度为 \(O(n^{\frac{1}{3}})\)

\[ \ \]

预处理 \(a_i,b_i\) 的答案 \(c_i=F(a_i),d_i=F(b_i)\) ，复杂度为 \(O(n\pi(M^{\frac{1}{3}}))\)

那么此时查询的权值就是 \(a_i\cdot t\) ，如果 \(>b_i\) 特判掉

否则，显然 \(c_i\) 的贡献可以先分离掉考虑进答案

对于剩下的部分，不妨设 \(x=\frac{a_i}{c_i}\) ，显然 \(x\) 不包含平方因子

考虑 \(x\) 与 \(t\) 的合并所产生的贡献，实际上就是 \(\gcd(x,t)\) (让 \(x\) 的单个因子与 \(t\) 匹配一下)

然后对于 \(t\) 剩下的部分 \(\frac{t}{\gcd(x,t)}\) ，由于 \(t\leq 3\cdot 10^5\) ，可以预处理一下答案

综合一下上面的部分，那么一个点的答案就是 \(c_i\gcd(x,t)^2 F(\frac{x}{\gcd(t,x)})\)

因此查询一个点的复杂度就是 \(\gcd\) 的 \(O(\log T)\)

\[ \ \]

综合利用上面的方法，勉强可以拿到 \(nm\log T\) 的20分

剩下的部分，可以考虑把树树剖一下，然后每个查询可以化为在 \(\text{dfs}\) 序上的若干更新区间 \(L_i,R_i,t_i\)

由于题目考虑的实际上是查询总和，因此可以对于每个点计算答案

不妨从 \(1-n\) 扫描 \(\text{dfs}\) 序，对于每个区间在 \(L_i\) 插入 \(t_i\) ，在 \(R_i+1\) 删除 \(t_i\)

用一个set来维护 \(t_i\) 的顺序，复杂度为 \(O(n\log ^2n)\)

在插入/删除set元素的同时，维护每一个 \(\Delta_i=t_i-t_{i-1}\) ，也就是我们要查询的每个数

查询单点时，由于这样的 \(\sum \Delta_i\leq T\) ，所以最多包含 \(O(\sqrt T)\) 种不同的 \(\Delta_i\)

用另一个set之类的东西维护这些不同的位置，然后暴力查询，复杂度为 \(O(n\sqrt T\log T)\)

总复杂度为 \(O(n\pi(M^{\frac{1}{3}})+n\sqrt T\log T)\) 左右

\[ \ \]

后记

由于特(智)殊(力)的(缺)原(陷)因

我考场上写了一个树剖+分块+莫比乌斯反演的做法，而且还没调出来，代码是这个，复杂度大概差不多 \(O(n\sqrt n \log_n^{\frac{3}{2}})\)

不提了。。。