很牛的一套题,非常非常综合。做完感觉 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\) 棵树状数组,在这些树状数组上更新答案即可。