T1：いまこの時の輝きを（Version1）

Idea：hhf Solution：lxl Std：lxl Data：lxl

https://www.luogu.org/problem/P5071

一个数的约数个数即其每个质因子出现次数加上一然后乘起来

考虑对值域进行一次根号分治，这里取阈值为 $v^{1/c}$ ，大于阈值的数最多有 $c-1$ 个

我们把区间中所有大于阈值的质因子对答案的贡献用莫队维护，小于阈值的质因子的贡献每次暴力枚举质因子，然后即查其在区间中出现次数即可

总时间复杂度$O( (n+m)v^{1/c}/logv + cn \sqrt m )$，空间复杂度$O( nv^{1/c}/logv + m )$

对这题的评价：3/11

T2：どうか、忘れないで（Version1）

Idea：lxl Solution：lxl Std：lxl Data：lxl

https://www.luogu.org/problem/P5072

考虑单次询问怎么算

对于数 $x$ ，假设出现了 $y$ 次，区间长度是 $len$

则 $x$ 对答案的贡献是 $x(2^{len-y}(2^y-1))=x(2^{len}-2^{len-y})$

$2^{len-y}$ 是除了 $x$ 之外的数有这么多个不同的子序列，这些对 $x$ 的贡献没有影响

$2^y-1$ 是所有 $x$ 构成的子序列中有这么多种至少包含一个 $x$ ，有 $1$ 种不包含 $x$

由于模数不同，不能用莫队直接维护

注意到贡献分为两部分 $x2^{len}$ 与 $-x2^{len-y}$

其中第一部分非常好维护

第二部分的贡献，可以把出现次数相同的数一起维护贡献

注意到一个区间中只有 $O( \sqrt n )$ 种不同的出现次数，这是一个自然根号

所以我们可以用一个莫队均摊地维护区间可能的出现次数，从而维护区间中所有出现次数

然后为了 $O(1)$ 实现快速幂，我们可以每次$O( \sqrt n )$算出

$2^1,2^2…2^{\sqrt n} % p$

以及$2^{\sqrt n},2^{2\sqrt n}…2^{ \sqrt n \times \sqrt n} % p$

这样就可以 $O(1)$ 快速幂了

还有一种方法是将出现次数排序，从 $2^x$ 转移到 $2^y$ 的时候的复杂度是 $log(y-x)$ ，类似于finger search的感觉，可以证明这个的复杂度是正确的

总时间复杂度 $O( n \sqrt m + m \sqrt n )$，空间复杂度 $O( n + m )$

对这题的评价：4/11

T3：世界で一番幸せな女の子（Version2）

Idea：lxl Solution：ccz Std：lxl Data：lxl

https://www.luogu.org/problem/P5073

考虑用线段树维护区间的一个凸的分段函数，这个分段函数其实也就是个半平面交

定义

cur -> L()为cur节点内部的左端最大前缀和的一个分段函数

cur -> R()为cur节点内部的右端最大后缀和的一个分段函数

cur -> MID()为cur节点内部的最大子段和的一个分段函数

cur -> L(x)代表cur节点整体被加了$x$后其最大前缀和

cur -> R(x)代表cur节点整体被加了$x$后其最大后缀和

cur -> MID(x)代表cur节点整体被加了$x$后其最大子段和

我们显然有

cur -> L(x) = max( cur -> left -> L(x) , cur -> right -> L(x) + cur -> left -> sum );

cur -> R(x) = max( cur -> left -> R(x) + cur -> right -> sum , cur -> right -> R(x) );

cur -> MID(x) = max( cur -> left -> MID(x) , cur -> right -> MID(x) , cur -> left -> R(x) + cur -> right -> L(x) );

由于两个段数分别为 $a$ 和 $b$ 的分段函数取max和加起来得到的分段函数最多有 $a+b$ 段，而且仍然都是凸函数

所以我们可以递归建线段树，然后由儿子归并得到其的分段函数

这里总复杂度是$T(n)=2T(n/2)+O(n)=O( nlogn )$的

这个其实和不带修改的线段树查询区间最大子段和类似，不过我们维护的是关于这个点被加了多少的一个分段函数从而计算出当前的最大前缀，最大后缀，最大子段和

然后考虑按照全局加有负数，可以按照全局加的这个东西离线，这样就可以做到$O( nlogn + mlogn )$了

总时间复杂度 $O( (n+m)logn )$，空间复杂度 $O( nlogn )$

对这题的评价：6/11