描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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）。
输出格式
一个正整数，调整展台总用时的最小值。
限制
各个测试点1s
提示
对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。
来源
birdor
分析可知，将高度都调整成区间中位数时，代价最小。
枚举i作为中心，向两边扩展序列。
先扩展左边，用链表记录每个“大于a[i]的数比小于a[i]的数多x”的位置po1。
再扩展右边，用右边的每个“大于a[i]的数比小于a[i]的数少x”的位置po2，匹配之前左边记录的位置，则mid[po1][po2]=i
之后O(n^2)暴力累加调整高度的花费。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
int pre[mxn],id[mxn],m[mxn<<];
int mid[mxn][mxn];
int a[mxn];
int n,Q;
int main(){
n=read();Q=read();
int i,j;
for(i=;i<=n;i++){a[i]=read();}
for(i=;i<=n;i++){
memset(id,,sizeof id);
memset(m,-,sizeof m);
memset(pre,,sizeof pre);
int x=,d=,cnt=;
for(j=i;j;j--){
if(a[j]>a[i])d++;
else x++;
id[cnt]=j;
pre[cnt]=m[d-x+mxn];
m[d-x+mxn]=cnt++;
}
d=;x=-;
for(j=i;j<=n;j++){
if(a[j]>a[i])d++;
else x++;
for(int k=m[x-d+mxn];k!=-;k=pre[k]){
if( (j-id[k]+)%== )mid[id[k]][j]=a[i];
}
for(int k=m[x-d-+mxn];k!=-;k=pre[k]){
if( (j-id[k])%== )mid[id[k]][j]=a[i];
}
}
}
int st,ed;
long long ans=;
while(Q--){
st=read();ed=read();
long long res=;
// printf("mid:%d\n",mid[st][ed]);
for(i=st;i<=ed;i++)res+=abs(a[i]-mid[st][ed]);
// printf("%d\n",res);
ans+=res;
}
printf("%lld\n",ans);
return ;
}