[vijos1459]车展

时间：2022-06-23 16:33:20

[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）。

输出

一个正整数，调整展台总用时的最小值。

输入示例





输出示例








数据规模及约定


对于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\n", Ans);

	return 0;

}



相关文章