2462. 最要强的内格
1000ms
256MB
简单
前缀和与差分
题目描述
在一次电子模拟作战中，假设敌方设置了一条防线，防线上依次有 $n$ 个据点。每个据点都有一个牢固值，数值越大表示越牢固。
司令部计划对 $n$ 个据点进行 $m$ 轮攻击，每轮攻击一段连续范围的据点 $[L, R]$。每一段范围上的据点都存在一个**总牢固值**（即该范围内所有据点牢固值之和）。
有一位最强的飞行员**内格**，申请在总牢固值最大的一轮出战。请你编写程序，帮助司令部找到这 $m$ 轮攻击中最大的总牢固值是多少。
输入格式
- 第一行包含两个正整数 $n$ 和 $m$ ($1 \le n, m \le 500,000$)。
- 第二行包含 $n$ 个整数，依次表示 $n$ 个据点的牢固值 ($1 \le ext{牢固值} \le 100$)。
- 接下来 $m$ 行，每行两个正整数 $L$ 和 $R$，表示每一轮攻击的范围 ($1 \le L \le R \le n$)。
输出格式
- 输出一个整数，表示所有攻击轮次中最大的总牢固值。
样例 1
输入 (Input)
输出 (Output)
样例说明
- 第 1 轮攻击范围 3~5，总牢固值：$5+3+6=14$。
- 第 2 轮攻击范围 6~7，总牢固值：$4+9=13$。
- 两轮中最大总牢固值为 14。
- $1 \le n, m \le 500,000$。
- 据点牢固值 $\le 100$。
› 输入 stdin
CtrlShiftEnter
‹ 输出 stdout
错误 stderr
操作成功