/ OIer TK / 题库 /

车展

车展

测试数据来自 system/1459

描述

遥控车是在是太漂亮了,韵韵的好朋友都想来参观,所以游乐园决定举办m次车展。车库里共有n辆车,从左到右依次编号为1,2,…,n,每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子:
L1 R1
L2 R2

Lm Rm
单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。

为了更加美观,展览时需要调整展台的高度,使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人,所以只好对每个展台依次操作。每次展览结束后,展台高度自动恢复到初始高度。

请告诉管理员为了举办所有展览,他最少需要花多少时间将展台调整好。

格式

输入格式

第一行为两个正整数n、m。

第二行共n个非负整数,表示第i辆车展台的高度h[i]。

接下来m行每行2个整数Li、Ri(Li≤Ri)。

输出格式

一个正整数,调整展台总用时的最小值。

样例1

样例输入1

6 4
4 1 2 13 0 9
1 5
2 6
3 4
2 2

样例输出1

48

限制

各个测试点1s

提示

对于50%的数据 n≤500,m≤1000;
对于80%的数据 n≤1000,m≤100000;
对于100%的数据n≤1000,m≤200000;
答案在2^64以内。

来源

birdor

信息

ID
1430
难度
(无)
分类
数据结构 | 平衡树数据结构 | 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者