问题 F: 小明的第一份实习任务

问题 F: 小明的第一份实习任务

时间限制: 1 Sec  内存限制: 128 MB
提交: 536  解决: 179
[状态] [讨论版] [提交] [命题人:]
题目描述

日志系统是分布式系统的重要组成部分,决定着系统的成败。工业界一种比较常见的的日志处解决方案是通过消息队列将系统产生的日志信息异步的存储起来,再通过日志分析服务进行相应的日志分析,常用的消息队列如kafka,rabbitMQ等。
   小明作为刚刚入职的实习生,leader交给了它一个任务:统计给定时间段产生的日志数量(时间用类似unix时间戳的方法表示)。可这个对他来说太难了,你能帮帮他吗?

输入

第一行输入两个整数n,m (0 < n < 1e5, 0 < m < 1e6),n表示要统计[0,n)时间内的日志数量,m表示小明统计的次数。
       第二行输入n个整数,第i(0 <= i < n, 0 <= Ai <= 10)个数代表系统在 i 这个时间戳产生的日志数量。
       接下来m行,每行输入两个整数t1,t2 (0 <= t1,t2 < n),表示小明同学要统计的区间。

输出

 对于每个区间[t1,t2],输出在这一时间段产生的日志数量。

样例输入 Copy
5 3
1 2 0 4 7
0 1
2 4
1 3
样例输出 Copy
3
11
6
提示
请注意问题规模:时间段数量n达十万个,而询问次数达一百万次。如果你采用低效率方法,将会超时,请注意优化。