传统题 1000ms 256MiB

素材调度

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

素材调度

题目描述

ori学长管理着一排 nn 个仓库,第 ii 个仓库里存有 aia_i 个素材。ori学长会进行 qq 次查询,第 jj 次查询给出 lj,rjl_j,r_j,他想知道第 ljl_j 到第 rjr_j 个仓库一共有多少个素材。

但是挨个查询实在太过于耗费时间,ori学长十分的懒惰,决定用一种省时间的方法:他将每个仓库里的素材数记录下来,编为 1−n1-n 号,对于第 ii 个仓库的素材,ori学长另找地方,在第 ii 位记录下来从 11 号仓库到 ii 号仓库的素材总数。

这样,ori学长只要在每次查询时,计算第二次记录的 brj−blj−1b_{r_j}-b_{l_j-1} 就好了。

具体来说:对于数组 aia_i,bi=∑k=1iakb_i=\sum_{k=1}^i a_k,则每次查询 l,rl,r,若求 ∑k=lrak\sum_{k=l}^{r} a_k,即等价于求 br−bl−1b_r - b_{l-1}

输入格式

第一行两个整数 n,qn,q。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\dots,a_n。

接下来 qq 行,每行两个整数 lj,rjl_j,r_j。

输出格式

输出 qq 行,每行一个整数,表示对应查询的答案。

样例 1

5 3
1 2 3 4 5
1 3
2 5
4 4
6
14
4

样例 1 解释:

  • 第 11 次查询:1+2+3=61+2+3=6;
  • 第 22 次查询:2+3+4+5=142+3+4+5=14;
  • 第 33 次查询:只有第 44 个仓库,答案为 44。

数据范围

  • 1≤n,q≤1051 \le n,q \le 10^5;
  • 0≤ai≤1090 \le a_i \le 10^9;
  • 1≤lj≤rj≤n1 \le l_j \le r_j \le n。

提示

单次查询的答案最大约为 101410^{14},请注意选择足够大的整数类型。 如遇TLE,请考虑是否可以对数据进行处理。

SYUCTACM双周赛#2

未参加
状态
已结束
规则
XCPC
题目
6
开始于
2026-10-23 18:30
结束于
2026-10-23 21:00
持续时间
2.5 小时
主持人
参赛人数
67