题面：
描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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以内。
思路：
参考hzwer 博客
实现代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls t[x].ch[0]
#define rs t[x].ch[1]
const int M = 1e3+;
const int inf = 0x3f3f3f3f;
ll last[M],n,m,root,cnt,tmp,num,tot;
struct node{
ll ch[],cnt,siz,val,rd,sum;
}t[M]; ll a[M],ans[M][M];
void up(ll x){
t[x].sum = t[ls].sum + t[rs].sum + t[x].cnt*t[x].val;
t[x].siz = t[ls].siz + t[rs].siz+t[x].cnt;
} void rotate(ll &x,ll d){
ll son = t[x].ch[d];
t[x].ch[d] = t[son].ch[d^];
t[son].ch[d^] = x; up(x); up(x=son);
} void Insert(ll &x,ll val){
if(!x){
x = ++cnt;
t[x].cnt = t[x].siz = ;
t[x].val = t[x].sum = val,t[x].rd = rand();
ls = ;rs = ; //因为没有清空数组，当前点为新建的点，左右儿子存的是上一次的值，应该清空掉。
return ;
}
t[x].siz ++; t[x].sum += val;
if(t[x].val == val){
t[x].cnt++; return ;
}
ll d = t[x].val < val; Insert(t[x].ch[d],val);
if(t[x].rd > t[t[x].ch[d]].rd) rotate(x,d);
} void del(ll &x,ll val){
if(!x) return ;
if(t[x].val == val){
if(t[x].cnt > ){
t[x].cnt--,t[x].siz--;return ;
}
bool d = t[ls].rd > t[rs].rd;
if(ls == ||rs == ) x = ls+rs;
else rotate(x,d),del(x,val);
}
else t[x].siz--,del(t[x].ch[t[x].val<val],val);
} ll query(ll x,ll val){
if(val <= t[ls].siz) return query(ls,val);
else if(val > t[ls].siz + t[x].cnt){
tmp += t[ls].sum + t[x].cnt*t[x].val;
return query(rs,val-t[ls].siz-t[x].cnt);
}
else{
tmp += t[ls].sum;
return t[x].val;
}
} void solve()
{
for(ll i = ;i <= n;i ++){
cnt = root = tot = ;
for(ll j = i;j <= n;j ++){
tot += a[j];
Insert(root,a[j]);
tmp = ;
num = (j-i+)/;
ll ave = query(root,num);
num--;
ans[i][j] += num*ave - tmp;
ans[i][j] += tot-tmp-(j-i+-num)*ave;
}
}
} int main()
{
ios::sync_with_stdio();
cin.tie(); cout.tie();
ll l,r,ans1= ;
cin>>n>>m;
for(ll i = ;i <= n;i ++) cin>>a[i];
solve();
for(ll i = ;i <= m;i ++){
cin>>l>>r;
ans1 += ans[l][r];
}
cout<<ans1<<endl;
}