很牛的一套题，非常非常综合。做完感觉 ds 水平飞起来了。
我会把实现讲的详细一些。
当然，这篇文章没有 Day2T3 世界上最幸福的女孩。我不会 geo，geo 是我最菜的领域。
按照个人难度排序。
Day2T1 此时此刻的光辉
主要练习点：常数优化/Pollard-Rho
当之无愧的签子。
显然根据 \(d\) 的计算式子，要统计区间内素数的出现次数。那么显然可以先用 Pollard-Rho，\(O(nV^{0.25})\) 把每个数的质因数先预处理出来。因为 \(V \leq 10^9\) 每个数最多只有 \(10\) 个不同的质因数。
区间显然可以用莫队维护，用一个 gp_hash_table 这样就是 \(O(n \sqrt{n})\) 的，但是枚举质因数有 \(10\) 倍常数。
如果前面用暴力分解，会跑的比较慢，卡常应该是相当折磨的。Pollard-Rho 就不一样了，瓶颈在于莫队，应该会快很多。但是这样依然过不了。
然后考虑还有没有什么优化方式。考虑把 \(1000\) 以内的质数筛出来，这部分前缀和作差暴力做，剩下的质因数最多只有 \(2\) 个（\(1001^3>10^9\)），而这些质因数出现的又比较多，这样可以大幅减少跑的次数，Pollard-Rho 和莫队就快飞了。
事实上，筛出来 \(100\) 以内的质数比 \(1000\) 快得多，可能因为 \(100\) 以上的出现次数没那么多。
Day1T1 我回来了
有点综合的题。
首先，发现触发技能的血量区间是一个关于 \(d\) 的调和级数。\(d \leq n\)，所以区间有 \(O(n \log n)\) 个。
然后我们考虑维护每个区间在什么时候有随从。因为随从血量也 \(\leq n\)，所以可以开一个 ST 表维护出现血量 \(i\) 随从的最小时刻。查的时候 ST 表查即可。
记 \(r(d,i)\) 表示参数 \(d\) 触发 \(i\) 次对应的血量最高随从的血量区间。
这部分也解决了，那么参数为 \(d\) 触发 \(i\) 次的最小时刻是什么时候呢？
-
能够触发 \(i-1\) 次之后来了个血在区间 \(r(d,i)\) 内的随从，那么时间是这个随从来的时间。
-
先来了 \(r(d,i)\) 的随从然后能够触发 \(i-1\) 次，那么此时也就直接能够触发 \(i\) 次。时间是能够触发 \(i-1\) 次的时间。
于是我们就会算 \(r(d,i)\) 能在什么时候产生贡献了。树状数组维护即可。
Day1T2 纵使日薄西山
主要练习点：线段树、分类讨论。
考虑答案的计算。相等是容易判的，所以分析的时候不考虑。
有性质：如果 \(a_i > a_{i-1}\) 且 \(a_i > a_{i+1}\)，那么这个大小关系不会改变。因为不存在 \(a_{i-1} > a_i\) 或者 \(a_{i+1}>a_i\) 能够使得 \(a_i\) 被某一边带着减掉使得另一边更大。
进一步发现这些 \(a_i\) 的和就是答案。
到这里，思路就明朗了：用线段树把这些 \(a_i\) 维护出来。
怎么维护呢？记一个 \(vl[0/1/2/3]\) 维护端点选不选：左右都选/左边不选/右边不选/左右都不选，再维护一下这些状态没被记录的端点有没有被选上。
每一个状态都有 \(3\) 种合并的可能，分别进行讨论，一共 \(12\) 种分类。复制粘贴是好的，如果没有漏改会很爽。
为什么加了没有漏改四个字呢，这是一个悲伤的故事。
单点修改全局查询就好了，所以 pushup 函数占到了总码长的 \(\dfrac{3}{4}\) 左右。憋笑。
Day2T2 盼君勿忘
主要练习点：复杂度平衡、根号分治。
首先，一眼莫队，然后不会做了。
思考，如果对于一段长度为 \(x\) 的区间，某个数 \(p\) 出现了 \(k\) 次，贡献是怎么样的。
总方案数显然是 \(2^x\)，不选 \(p\) 的方案数即为 \(2^{x-k}\)。那么 \(p\) 的贡献就是 \(p(2^x-2^{x-k})\)。
那么我们就需要统计每个数的出现次数。
但是问题在于，\(p\) 是不同的。这很要命。这意味着我们统计答案必须得枚举。
复杂度会爆掉，尝试根号分治。
对于出现次数 \(< \sqrt{n}\) 的，记录每一个出现次数，所有数的和，根据分配律是可以算出来这部分贡献的。
对于 \(\geq \sqrt{n}\) 的，记录有哪几个数，出现了多少次，显然这部分不会超过 \(\sqrt{n}\) 个数。用 unordered_set 可以实现 \(O(1)\) 维护。
最后考虑 \(p\) 的幂次怎么求。只要把 \(p^1,p^2,\dots p^{\sqrt{n}}\) 和 \(p^{2\sqrt{n}},p^{3\sqrt{n}},\dots p^{n}\) 处理掉就可以合并出每一个幂次了。复杂度 \(O(\sqrt{n})\)。
这样子，莫队的复杂度是 \(O(n\sqrt{m})\)，每组询问进行求幂次和统计的复杂度是 \(O(\sqrt{n})\)。总复杂度 \(O(n\sqrt{m}+m\sqrt{n})\)。
Day1T3 即便看不到未来
\(k\) 很小，可以暴力查 \(k\)。
然后考虑具体怎么维护。
可以发现，一个位置只能够对 \(O(k)\) 个位置做出贡献。可以在前面加，也可以在后面加，还可以合并两部分。
考虑如何加位置。直接对 \(r\) 扫描线，记录对于每个 \(l\) 的贡献，具体维护方法为，枚举每一个可以扩展的位置，依次加入，以 \(a_i\) 为中心向左右扩展区间。开 \(k\) 棵树状数组，在这些树状数组上更新答案即可。