「lych_cys模拟题2018」橘子树

设值域上限为$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} })$

不提了。。。

orangejuice's blog