题解 | 数不清的1 (困难版本)

讲一种不用脑子的做法。

简单版本直接打表就行，不需要脑子吧。

困难版本（简单版本都不会推还能会困难版吗？）

所以我们考虑带脑子的打表。

这个显然是可以线下预处理出来的。

我们采用分块打表的方式，将 分成 长度的块，每一块求和然后打成表。

对于一次查询，我们可以这样处理，对于在整块的部分，选择直接加预处理的数组，对于散块的部分，我们采取直接暴力。

复杂度就是块长，但是绝对卡不满，所以能过，嘻嘻。

代码太长了，给个链接：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=65294370