描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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以内。
题解
用treap n^2logn预处理中位数参考hzwer
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1e5+, M = 1e3+, MOD = 1e9+, inf = 2e9;
typedef long long ll; struct data{int l,r,v,size,rnd,w;ll sum;}tr[N * ]; int n,siz ,m, a[N],root, ans[M][M] ,Sum,cnt,snt; void update(int k) {
tr[k].size = tr[tr[k].l].size+tr[tr[k].r].size + tr[k].w;
tr[k].sum = tr[tr[k].l].sum + tr[tr[k].r].sum + tr[k].w*tr[k].v;
}
void lturn(int &k) {
int t=tr[k].r;tr[k].r=tr[t].l;tr[t].l=k;update(k);update(t);k=t;
}
void rturn(int &k) {
int t=tr[k].l;tr[k].l=tr[t].r;tr[t].r=k;update(k);update(t);k=t;
}
void insert(int &k,int x) {
if(!k) {
k=++siz;
tr[k].w=tr[k].size=;
tr[k].v=tr[k].sum=x;
tr[k].rnd = rand();
tr[k].l = tr[k].r =;
return ;
}
tr[k].size++;tr[k].sum+=x;
if(tr[k].v==x) tr[k].w++;
else if(x>tr[k].v) {
insert(tr[k].r,x);
if(tr[tr[k].r].rnd<tr[k].rnd) lturn(k);
}else {
insert(tr[k].l,x);
if(tr[tr[k].l].rnd<tr[k].rnd) rturn(k);
}
}
int query(int k,int x) {
if(x<=tr[tr[k].l].size) return query(tr[k].l,x);
else if(x>tr[tr[k].l].size + tr[k].w) {
cnt+=tr[tr[k].l].size + tr[k].w;
snt+=tr[tr[k].l].sum+tr[k].w*tr[k].v;
return query(tr[k].r,x - tr[tr[k].l].size - tr[k].w);
}else {
cnt+=tr[tr[k].l].size;
snt+=tr[tr[k].l].sum;
return tr[k].v;
}
}
int main() {
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) scanf("%d",&a[i]);
for(int i=;i<=n;i++) {
root = siz = ;
Sum = ;
for(int j=i;j<=n;j++) {
Sum += a[j];
insert(root,a[j]);
cnt = snt = ;
int ave = query(root,(j-i+) / );
ans[i][j] = cnt*ave - snt + Sum - snt - (j-i+-cnt)*ave;
}
}
ll all = ;
while(m--) {
int l,r;
scanf("%d%d",&l,&r);
all+=ans[l][r];
}
cout<<all<<endl;
}