P1459车展
描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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以内。
【思路】
Treap。
每次展览都是L..R内的中位数作为基准为最优，用Treap提前将所有LR预处理出来。时间为O(n^2logn)
代码奇慢无比 /w\
【代码】
#include<cstdio>
#include<ctime>
#include<cstring>
#include<cstdlib>
#include<iostream>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; typedef long long LL;
const int N = 1e3+;
const int INF = 1e8; int n,m,h[N],num;
LL ans[N][N],tot,cnt,tmp; struct Node {
Node* ch[];
int v,r,s,w,sum;
Node(int x):v(x) {ch[]=ch[]=NULL; s=w=;sum=x;}
int cmp(int x) {
if(x==v) return -; else return x<v? :;
}
void maintain() {
s=w; sum=w*v;
if(ch[]!=NULL) s+=ch[]->s,sum+=ch[]->sum;
if(ch[]!=NULL) s+=ch[]->s,sum+=ch[]->sum;
}
};
Node* root;
void rotate(Node* &o,int d) {
Node* k=o->ch[d^]; o->ch[d^]=k->ch[d],k->ch[d]=o;
o->maintain(),k->maintain(); o=k;
}
void insert(Node* &o,int x) {
if(o==NULL) o=new Node(x);
else {
int d=o->cmp(x);
if(d==-) {o->w++;o->maintain();return ;}
insert(o->ch[d],x);
if(o->ch[d]->r > o->r) rotate(o,d^);
}
o->maintain();
}
int query(Node* o,int x) {
int sum,s;
if(o->ch[]==NULL) s=sum=; else s=o->ch[]->s,sum=o->ch[]->sum;
if(x>=s+ && x<=s+o->w) {
tmp+=sum; num+=s;
return o->v;
}
else {
if(x<=s) return query(o->ch[],x);
else {
tmp+=sum+o->v*o->w;
num+=s+o->w;
return query(o->ch[],x-s-o->w);
}
}
} void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)) {if(c=='-')f=-;c=getchar();}
while(isdigit(c)) x=x*+c-'',c=getchar();
x*=f;
}
void init() {
FOR(i,,n) {
tot=;
FOR(j,i,n) {
tot+=h[j]; insert(root,h[j]);
tmp=num=;
int v=query(root,(j-i+)/);
ans[i][j]+=num*v-tmp;
ans[i][j]+=tot-tmp-(j-i+-num)*v;
}
root=NULL;
}
}
int main() {
read(n),read(m);
FOR(i,,n) read(h[i]);
init();
LL anss=;int x,y;
FOR(i,,m) {
read(x),read(y);
anss+=ans[x][y];
}
cout<<anss;
return ;
}