题意:
分析:
远看数论题,实则是道数据结构。
记 \(f_{i}\) 表示 \(r_{k}=i\) 的方案数,\(g_{i}\) 表示 \(l_{1}=i\) 的方案数,那么运用简单容斥,可得:
\[ans_{x} = (\sum_{i=1}^{n} f_{i}) - ((\sum_{i=1}^{x-1}f_{i})+1) \times ((\sum_{i=x+1}^{n}g_{i})+1)+1 \]先考虑如何计算 \(f_{i}\),对于一个相同的 \(i\):
记 \(z=\gcd(a_{x},a_{x+1},\dots,a_{i})\),可以发现随着 \(x\) 变小,\(z\) 单调不升且 \(z\) 的本质不同的值不超过 \(\log V\) 个。因此可以使用二分把所有 \(z\) 相同的左端点的区间求出来,对于 \(z\) 相同的一段左端点 \(x \in [l,r]\) 而言,它在 \(dp\) 转移时必须满足上一个区间的 \(gcd\) 与这个区间的 \(gcd\) 值相等,解决方法也不难,只需要先二分离线预处理出一些四元组:
\[(l,r,i,z) \]其表示左端点所属的区间为 \([l,r]\),右端点为 \(i\),\(gcd\) 为 \(z\)。根据上面的分析,这样的四元组的个数不超过 \(n \log V\) 个。我们将 \(z\) 相同的四元组按 \(i\) 排序,记 \(sum_{i}\) 表示在该 \(gcd\) 下 \(\sum_{j=1}^{i}f_{i}\),那么转移为:
\[(\sum_{j=l-1}^{r-1} g_{j}) \to f_{i} \]转移它可以使用线段树(不用树状数组是因为树状数组无法快速清空),套路地维护 \(f_{i}\) 和 \(if_{i}\) 的前缀和,这样就能快速求出 \(g_{j}\) 的前缀和,这样就能转移了。总时间复杂度 \(O(n \log n \log V)\)。
标签:钉耙,log,sum,2024,四元组,端点,1005,gcd From: https://www.cnblogs.com/xcs123/p/18333257