解题思路
问题转化
对于任意子数组，它的权值等于“需要补充多少数字才能变成一个连续区间”。
这个数量可以写成：
权值 = (子数组最大值 − 子数组最小值) − (子数组长度 − 1)。
所以总答案就是：
P3518.第3题-连续数列
题目内容
小美从一个原始的连续数列(各元素互不相同，且恰好是某个区间内的所有整数)中丢失了一些数字，剩余元素按
原顺序形成了一个长度为n 的数组{a1,a2,...,an}。
选定区间[l,r]后，一定可以通过插入若干元素，使得子数组中的元素恰好构成从 min(al,...,ar)到
max(al,...,ar)的连续整数序列。我们称这个子数组的权值为:插入的最少元素数量。
请你计算数组中所有子数组的权值之和。
输入描述
第一行输入一个整数n(1≦n≦2×105)表示数组长度。
第二行输入n个互不相同的整数{a1,a2,...,an}(1≦ai≦106)表示数组元素.
输出描述
输出一个整数，表示数组中所有子数组的权值之和。
样例1
输入
3
3 1 2
输出
1
说明
在第一个样例中，所有子数组及其所需插入数如下:
-
[1,1]={3}, min=3,max=3，需插入0个元素
-
[1,2]={3,1}, min=1,max=3需入1个元素;
-
[1,3]={3,1,2}，需插入0个元素;
-
[2,2]={1}，需插入0个元素;
-
[2,3]={1,2}，需插入0个元素;
-
[3,3]= {2}，需插入0个元素;
权值之和为0+1+0+0+0+0=1
样例2
输入
4
2 5 3 8
输出
14
开通会员即可查看完整视频题解： 1.题目讲解 2.思路分析 3.逐行代码手写
