总之就是一道非常板子的题，可以用各种常见的具有分治结构的数据结构莽过去。 这里讲一下分块做法：不难发现扫过一段区间后 sss 改变量只与位于段首时 sss 模三的余数有关，则我们先将序列分成 n0.5n^{0.5}n0.5 个块，在各块首设 s=0,1,2s=0,1,2s=0,1,2 分别统计末位置的 sss，再分别减去 1,2,31,2,31,2,3 即可得到块的改变量。统计答案时遇到完整的块就用改变量统计贡献，遇到残块就暴力统计，预处理 O(n)O(n)O(n)，单次统计答案 O(n0.5)O(n^{0.5})O(n0.5)，总时间复杂度 O(q⋅n0.5)O(q·n^{0.5})O(q⋅...