日期: 2018 年 8 月 23 日

这个题的官方题解简直玄学，根号5取模，然后转化成等比数列，服气。

还好评论区有人给了更简便的做法：广义斐波那契数列。任意两个广义斐波那契数列相加仍然是斐波那契数列，而且只要知道了前两项的和就可以知道任意一项的和和任意一项的开始的前缀和。比如若第一二项为a,b,那么手推几下就可以发现，fab[n]=af[n-2]+bf[n-1]，然后前缀和是fsum[n]=f[n+2]-f[2]（这个也很容易推出来，甚至奇数项偶数项分别的和都能推出来）,然后这时候就很简单了，对于每一个区间只需要保存其左端点处的a，b就可以了，把ab做成lazy tag就可以实现区间修改了。注意这时候pushdown的时候，对于右孩子要计算出来fibab到这个点是多大才可以。一如既往的，add操作需要在maintain里加单节点特判（我也不知道为什么但是已经习惯了）还有一点注意ta一定是+的第一个，tb一定是+的第二个。

准备再用等比数列方法做一遍吧，看看是怎么个操作。。今天写了一下等比数列的操作方法，感觉比原来的方法简单emmm
继续阅读“[线段树][区间等比/等差数列修改] CodeForces – 446C DZY Loves Fibonacci Numbers”

Huh，比赛的时候花了三个小时把这个正解是用后缀自动机的题肝了出来，我也不知道我怎么做到的。

想了很多策略之后发现自己是错的就很难受，最后终于想到正确策略：在height数组上做一个长度为k的滑窗，每次检查滑窗两端点之外的height是否比这一整段内的最小值大，注意这里面的一整段最小值M就是这一整段的公共最长公共前缀的长度，这个东西和他的前缀是在这里出现了k次的，那么怎么知道他是不是在滑窗外面出现呢，和两端点的height比较一下就行了，取两端点中的最大值P，这个说明是之外的点与滑窗两个端点的最大公共前缀，而所有的在滑窗内的满足P<len<=M的前缀都是仅出现了一次的子串！！！

wa的话，需要特判k为1的情况，，因为height这个数组是个间隔定义的东西，所以这种只有一个的需要单独处理，这时候实际上区间内的最长公共前缀就是排名在此的后缀本身

继续阅读“[后缀数组][模板] 求正好出现k次子串个数 HDU6194 string string string”

https://cn.vjudge.net/problem/CodeForces-920F

跟上一道HDU的题目很像，也是求快速收敛函数的和，因为有结论n的约数个数期望为sqrt(n)。每次遇到一个数就将其质因数分解然后求约数个数，这里可以开一个1e6的数组把处理过的n存下来，记忆化，就可以省下来很多时间（大概吧呵呵）。另外一个需要注意的点是收敛的终点可能是1也可能是2，我这里的方法是把读入的1全变成2，然后输出的时候减去前缀和差分就行了，因为1是怎么都不会变的，2也是不会变的，这样可以保证正确。

继续阅读“[线段树][收敛函数][区间修改]”

https://cn.vjudge.net/problem/HDU-4027

这个题，本身并没有用到区间修改的什么操作。。如果不加优化就基本可以认为是单点修改区间查询的线段树，但是int64的最大值也只需要6次开根号就会收敛到1，因此我们可以加一个优化就是当子区间每一个都是1的话就不再更新区间（就这一个优化真的可以搞定吗。。。）其他的都跟普通的线段树一样了，只不过初始化建树的时候需要一个单独的点修改函数来操作。
继续阅读“[线段树][优化][特征分析] HDU 4027 Can you answer these queries?”