描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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
样例输出1
限制
各个测试点1s
提示
对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。
来源
birdor
分析可知将区间高度都调整成中位数时答案最优。
用treap查询中位数。
枚举区间起点，然后从该点一直往右扫描，每次将该位置的数加入到treap中，并查询第size/2大的数，即是这段区间的中位数。
/*by SilverN*/
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<ctime>
#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;
}
struct node{
int l,r;
int size,v,w;
int rnd;
}t[mxn];
int cnt,root;
void update(int rt){
t[rt].size=t[t[rt].l].size+t[t[rt].r].size+t[rt].v;
}
void lturn(int &k){
int now=t[k].r;
t[k].r=t[now].l;
t[now].l=k;
update(k);update(now);k=now;
return;
}
void rturn(int &k){
int now=t[k].l;
t[k].l=t[now].r;
t[now].r=k;
update(k);update(now);k=now;
return;
}
void insert(int &k,int x){
if(!k){
t[++cnt].w=x;
t[cnt].size=;t[cnt].v=;
t[cnt].rnd=rand();
t[cnt].r=t[cnt].l=;
k=cnt;
return;
}
t[k].size++;
if(x==t[k].w)t[k].v++;
else if(x<t[k].w){
insert(t[k].l,x);
if(t[t[k].l].rnd<t[k].rnd)rturn(k);
}
else{
insert(t[k].r,x);
if(t[t[k].r].rnd<t[k].rnd)lturn(k);
}
return;
}
int query(int k,int num){
if(!k)return ; // printf("k:%d num:%d\n",k,num);
// printf("l:%d r:%d v:%d size:%d\n",t[k].l,t[k].r,t[k].v,t[k].size);
if(num<=t[t[k].l].size)return query(t[k].l,num);
if(num>t[t[k].l].size+t[k].v)return query(t[k].r,num-t[t[k].l].size-t[k].v);
return t[k].w;
}
int h[mxn];
int mid[mxn][mxn];
int n,m;
int main(){
srand(time());
n=read();m=read();
int i,j;
for(i=;i<=n;i++) h[i]=read();
for(i=;i<=n;i++){
cnt=root=;
for(j=i;j<=n;j++){
// printf("root:%d ",root);
insert(root,h[j]);
// printf(" %d \n",root);
mid[i][j]=query(root,(j-i+)/);
// printf("root:%d mid %d %d:%d\n",root,i,j,mid[i][j]);
}
}
int st,ed;
long long res=,ans=;
while(m--){
res=;
st=read();ed=read();
for(i=st;i<=ed;i++)res+=abs(h[i]-mid[st][ed]);
// printf("%d %d %d %d\n",st,ed,mid[st][ed],res);
ans+=res;
}
printf("%lld\n",ans);
return ;
}