UOJ Logo LFYZ Online Judge

LFYZOJ

#10. 【模板】前缀和(幻想月面战争骚动)

统计

问题描述

这是千年之前的事了。紫玩弄着虚与实的境界,飞去入侵照映湖面的月球。虽然聚集了大量妖怪,不过面对月之近代兵器,结果惨败。至此之后,妖怪们就很少再去入侵不属于自己的领域了。因为这骚动,人类之间也知道了这只境界妖怪的力量。

八云紫聚集了一些妖怪,这些妖怪分布在 $n$ 个位置上。她想要攻打月之都,就要给妖怪排好适当的阵型。她要排 $m$ 个阵型,为了排阵型,她要知道从位置 $i$ 到 $j$ 内妖怪的数量。

输入格式

第一行是整数$n$和$m$代表妖怪的位置数目和询问的个数。

第二行是$n$个数,第$i$个代表$i$号位置上妖怪的数目。

下来$m$行一行两个整数$i$与$j$,说明紫想知道从位置$i$到$j$内妖怪的数量和。

输出格式

对于每个询问,输出一个整数,代表那个询问的答案。每输出完一个答案换行。

样例一

input

7 4
1 19 12 5 13 1 2
4 7
2 6
1 3
4 4

output

21
50
32
5

数据范围与约定

对于$10\%$的数据,所有位置的妖怪数目均为1,$n \leq 20$,$m \leq 2$。

对于$20\%$的数据,所有位置的妖怪数目均相等,$n \leq 20$,$m \leq 2$。

对于$30\%$的数据,$n \leq 3000$,$m \leq 700$,所有位置的妖怪数目都$ \leq 200$。

对于$60\%$的数据,$n \leq 3000$,$m \leq 40000$,所有位置的妖怪数目都$ \leq 200$。

对于$100\%$的数据,$n \leq 90000$,$m \leq 100000$,所有位置的妖怪数目都$ \leq 200$。

时间限制: $1\mathrm{s}$

内存限制: $256\mathrm{MB}$

下载

样例数据下载

  • ex_moon1.in/out 对应样例。
  • ex_moon2.in/out 对应$60\%$的数据范围。
  • ex_moon3.in/out 对应$100\%$的数据范围。