Increasing Array Queries

题目描述

给你一个由 n 个整数组成的数组。数组元素的下标为 1,2,\dots,n。 你可以使用以下操作修改数组：选择一个数组元素并将其值增加一。 你的任务是处理 q 个查询，查询形式为：当我们考虑从位置 a 到位置 b 的子数组时，使该子数组变为非降（即每个元素大于或等于前一个元素）所需的最少操作次数是多少？ 数组是非降的，当且仅当每个元素都大于或等于前一个元素。

输入格式

第一行包含两个整数 n 和 q：数组的大小和查询的数量。 下一行包含 n 个整数 $x_1,x_2,\dots,x_n$：数组的元素。 接下来有 q 行描述查询。每行包含两个整数 a 和 b：子数组的起始和结束位置。

输出格式

对于每个查询，输出所需的最少操作次数。

5 3
2 10 4 2 5
3 5
2 2
1 4

2
0
14

提示

$1 \le n,q \le 2\cdot10^5$ $1 \le x_i \le 10^9$ $1 \le a \le b \le n$

标签: CSES2416|区间查询

来源

CSES2416|区间查询