一道放在分块训练中的分块打表屑题
看了神NaCly_Fish的题解学了间隔打表(话说这么屑的东西有什么学的必要吗)
内容大多摘自大佬的题解
1，答案可递推，才适合间隔打表
什么叫可递推呢？
假设f[n]为区间[1,n]的答案，那么f[n+1]应该可以由很短的时间从f[n]推出来。满足这个条件，就可以愉快地间隔打表辣！
像这一题就是可递推的，递推式可以写成这样：
f[n] = f[n-1] + IsLucky(n);
2，间隔打表用法
个人对于区间统计问题的用法是这样的：
在这题中，记录 [1,106],[1,2*106]....[1,1000*106] 区间的答案，容易看出这是一个前缀和的形式。
当我们要计算区间 [l,r]的答案时，只需要计算 [1,r]-[1,l-1] 即可
对于 [1,a] 的答案，可以拆成两部分计算，一部分是已经搞好的前缀和，一部分暴力计算。
3，打表的间隔
根据上面一段，可以发现打表的间隔越小，运行速度就越快。
但是代码过长的话，是没办法提交的。这题单次递推的时间复杂度是Θ(logn) 的，所以打表间隔用 106 就行了。