原题链接
严肃发布在灌水池塘
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
看见“区间和”这三个字,你想到了什么?
当然是 前缀和 线段树啊。
再来看数据,高达 10410^4104,说明暴力肯定做不了了,我们只能老老实实的打线段树了。
代码:
时间复杂度 O(n+mlogn)\mathcal{O}(n+m\log n)O(n+mlogn)。
线段树板子,建议升绿(
(效率还不如前缀和
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
严肃再用莫队做一遍
时间复杂度 O((n+m)n)\mathcal{O}((n+m)\sqrt{n})O((n+m)n )。