2359. 开炮
1000ms
256MB
简单
前缀和与差分
题目描述
某国正在测试一种新型火炮，计划对一条战线上的若干个据点进行打击。
战线上共有 $n$ 个据点，每个据点都有一个初始的“牢固值”。已知发射 1 发炮弹可以消耗目标据点 1 点牢固值。
现在共有 $m$ 门火炮参与测试，每门火炮负责摧毁一段连续区间 $[L, R]$ 内的据点。由于各火炮在发射前没有进行沟通，它们会各自独立地对指定区间内的所有据点进行饱和打击，即每门火炮在负责的区间 $[L, R]$ 内发射的炮弹数量等于该区间内所有据点的初始牢固值之和。
请计算出这 $m$ 门火炮总共需要准备多少发炮弹。
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($1 \le n, m \le 100000$)，分别表示据点的数量和参与测试的火炮门数。
- 第二行包含 $n$ 个正整数，依次表示每个据点的初始牢固值 $a_i$ ($1 \le a_i \le 100$)。
- 接下来 $m$ 行，每行包含两个正整数 $L$ 和 $R$ ($1 \le L \le R \le n$)，表示每门火炮负责的打击区间（1-indexed）。
输出格式
- 输出一个整数，表示所有火炮合计需要准备的炮弹总数。
样例 1
输入 (Input)
7 2 2 10 5 3 6 4 9 3 5 6 7
输出 (Output)
27
样例 2
输入 (Input)
5 3 4 2 10 3 7 1 2 4 5 1 3
输出 (Output)
32
- 对于 $100\%$ 的数据：$1 \le n, m \le 100000$，$1 \le a_i \le 100$，$1 \le L \le R \le n$。
- **注意**：累加的总炮弹数量可能会非常大。在最坏情况下，总炮弹数可达 $10^5 \times 10^5 \times 100 = 10^{12}$，这超出了 32 位有符号整型（`int`）的表示范围。因此，保存总数的变量和前缀和数组必须使用 **`long long`** 类型。
- **算法提示**：
本题为经典的**区间和**问题。
1. 预处理：构建前缀和数组 $S$，其中 $S[i] = \sum_{j=1}^{i} a_j$，表示前 $i$ 个据点牢固值的总和。
2. 查询：对于每门火炮的打击区间 $[L, R]$，其所需的炮弹数为 $S[R] - S[L-1]$。
3. 累加：将每次查询的结果累加至总和中即可。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功