[vijos1459]车展
试题描述
遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办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）。
输出
一个正整数，调整展台总用时的最小值。
输入示例
6 4 4 1 2 13 0 9 1 5 2 6 3 4 2 2
输出示例
48
数据规模及约定
对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000；
答案在2^64以内。
题解
预处理一波。参见[BZOJ1112][POI2008]砖块Klo。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 1010
#define LL long long
struct Node {
int r, siz;
LL v, sum;
Node() {}
Node(int _, int __): v(_), r(__) {}
} ns[maxn];
int rt, ToT, fa[maxn], ch[2][maxn];
void maintain(int o) {
ns[o].siz = 1; ns[o].sum = ns[o].v;
for(int i = 0; i < 2; i++) if(ch[i][o])
ns[o].siz += ns[ch[i][o]].siz,
ns[o].sum += ns[ch[i][o]].sum;
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(z) ch[ch[1][z]==y][z] = u;
if(ch[1][y] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;
ch[l][y] = ch[r][u]; ch[r][u] = y;
maintain(y); maintain(u);
return ;
}
void insert(int& o, LL v) {
if(!o) {
ns[o = ++ToT] = Node(v, rand());
return maintain(o);
}
bool d = v > ns[o].v;
insert(ch[d][o], v); fa[ch[d][o]] = o;
if(ns[ch[d][o]].r > ns[o].r) {
int t = ch[d][o];
rotate(t); o = t;
}
return maintain(o);
}
LL Find(int o, int k) {
if(!o) return 0;
int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;
LL lsum = ch[0][o] ? ns[ch[0][o]].sum : 0;
if(k >= ls + 1) return lsum + ns[o].v + Find(ch[1][o], k - ls - 1);
return Find(ch[0][o], k);
}
LL Findn(int o, int k) {
if(!o) return -1;
int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;
if(k == ls + 1) return ns[o].v;
if(k > ls + 1) return Findn(ch[1][o], k - ls - 1);
return Findn(ch[0][o], k);
}
LL ans[maxn][maxn], H[maxn];
int main() {
int n = read(), q = read();
for(int i = 1; i <= n; i++) H[i] = read();
for(int l = 1; l <= n; l++) {
rt = ToT = 0;
memset(fa, 0, sizeof(fa));
memset(ch, 0, sizeof(ch));
for(int r = l; r <= n; r++) {
insert(rt, H[r]);
int k = r - l + 2 >> 1;
LL tmp = Findn(rt, k), sum = Find(rt, k);
ans[l][r] = tmp * k - sum;
k = r - l + 1 - k; sum = ns[rt].sum - sum;
ans[l][r] += sum - tmp * k;
}
}
LL Ans = 0;
while(q--) {
int l = read(), r = read();
Ans += ans[l][r];
}
printf("%lld
", Ans);
return 0;
}