讲一种不用脑子的做法。

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

困难版本(简单版本都不会推还能会困难版吗?)

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

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

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

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

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

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