CF515E Drazil and Park

博主： tony102
发布时间：2020 年 10 月 20 日
1070 次浏览
暂无评论
1871字数
分类：题解

[Link](https://www.luogu.com.cn/problem/CF515E)

## Description

给定 $n$ 个点 $i$ 到点 $i+1$ 的距离 $d[i]$，每个点有一个权值 $h[i]$。现在有 $m$ 组询问，每次询问 $[l,r]$ 内两点 $x, y$， 使得$2*(h_x + h_y) + dis(x,y)$ 最大。其中 $dis(x,y)$ 表示 $x$ 到 $y$ 的距离。

## Sol

**墙裂推荐的好题**

首先它给你的个点之间的距离是个环状的，你要断环成链。

接下来你要考虑如何将 $2*(h_x + h_y) + dis(x,y)$ 最大化。先考虑将 $2*(h_x + h_y) $ 和 $dis(x,y)$ 分别最大化。

显然将他们两个分别最大化的情况下，最大化的结果的 $x,y$ 坐标很有可能不是同一对。

**假如两个最大值你不好同时查，就换成把最大化一个东西，再最小化另外一个并把加法做成减法**

绝活。

考虑 $dis(x, y)$ 怎么计算，设 $sum[]$ 是$d[]$ 的前缀和，那么 $dis(x,y) = sum[y] - sum[x]$

这个时候我们就是要让 $sum_y - sum_x + 2 * h_x + 2 * h_y$ 最大

套路：把跟同一个东西相关的东西一起处理

现在变成了：$sum_y + 2 * h_y - sum_x + 2 * h_x$ 最大。那就让 $sum_y + 2 * h_y$ 最大，$sum_x + 2 * h_y$ 最小

因为没有修改操作，RMQ问题就可以用ST表，也可以用线段树之类的。

但是考虑一个问题，这样子做有可能查到的这两个的最大最小的位置是同一个位置，这样不符合要求。所以当我们查到了两个相同的位置的时候，就在 $[l, pos - 1] $ 和 $[pos + 1, r]$ 中查一下最大最小的位置就可以了。其中 $pos$ 是第一查到的最大最小位置。

同时注意到刚才我们要查的是位置，所以维护RMQ信息的时候要维护的是RMQ的下标。

## Code

我实现用的线段树，比较好懂。用魔力`ae86`快读以后吊打ST表做法。

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 2e5 + 5;
const int inf = 1e18;

int n, m;
int d[SIZE], h[SIZE], sumMin[SIZE], sumMax[SIZE];

struct node {
	int l, r, maxx, minn;
} tree[SIZE << 2];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

inline int getMax(int x, int y)
{
	return sumMax[x] > sumMax[y] ? x : y;
}

inline int getMin(int x, int y)
{
	return sumMin[x] < sumMin[y] ? x : y;
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p)
{
	tree[p].maxx = getMax(tree[lson(p)].maxx, tree[rson(p)].maxx);
	tree[p].minn = getMin(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline void build(int p, int l, int r)
{
	tree[p].l = l, tree[p].r = r;
	if (l == r) {
		tree[p].maxx = tree[p].minn = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(lson(p), l, mid); build(rson(p), mid + 1, r);
	pushUp(p);
}

inline int queryMax(int p, int l, int r)
{
	if (l <= tree[p].l && tree[p].r <= r) {
		return tree[p].maxx;
	}
	int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
	if (l <= mid) ans = queryMax(lson(p), l, r);
	if (r > mid) ans = getMax(queryMax(rson(p), l, r), ans);
	return ans;
}

inline int queryMin(int p, int l, int r)
{
	if (l <= tree[p].l && tree[p].r <= r) {
		return tree[p].minn;
	}
	int mid = (tree[p].l + tree[p].r) >> 1, ans = 0;
	if (l <= mid) ans = queryMin(lson(p), l, r);
	if (r > mid) ans = getMin(queryMin(rson(p), l, r), ans);
	return ans;
}

inline int calcMin(int l, int r)
{
	if (l > r) return 0;
	return queryMin(1, l, r);
}

inline int calcMax(int l, int r)
{
	if (l > r) return 0;
	return queryMax(1, l, r);
}

inline int solve(int l, int r)
{
	int minn = calcMin(l, r), maxx = calcMax(l, r);
	if (minn != maxx) return sumMax[maxx] - sumMin[minn];
	int minn2 = getMin(calcMin(l, minn - 1), calcMin(minn + 1, r));
	int maxx2 = getMax(calcMax(l, maxx - 1), calcMax(maxx + 1, r));
	return std::max(sumMax[maxx2] - sumMin[minn], sumMax[maxx] - sumMin[minn2]);
}

signed main()
{
	// freopen("code.in", "r", stdin);
	// freopen("code.out", "w", stdout);
	n = read(), m = read();
	for (register int i = 1; i <= n; ++ i) {
		d[i % n + 1] = d[i % n + 1 + n] = read();
	}
	for (register int i = 1; i <= n; ++ i) {
		h[i] = h[i + n] = read();
	}	
	int sum = 0; sumMax[0] = -inf, sumMin[0] = inf;
	for (register int i = 1; i <= (n << 1); ++ i) {
		sum += d[i];
		sumMax[i] = sum + 2 * h[i];
		sumMin[i] = sum - 2 * h[i];
	}
	build(1, 1, 2 * n + 1);
	while (m --) {
		int l = read(), r = read();
		if (l <= r) printf("%lld\n", solve(r + 1, n + l - 1));
		else printf("%lld\n", solve(r + 1, l - 1));
	}
	return 0;
}
```

最后修改：2021 年 09 月 04 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

CF515E Drazil and Park

tony102 • 2020 年 10 月 20 日

[Link](https://www.luogu.com.cn/problem/CF515E)

## Description

## Sol

**墙裂推荐的好题**

首先它给你的个点之间的距离是个环状的，你要断环成链。

接下来你要考虑如何将 $2*(h_x + h_y) + dis(x,y)$ 最大化。先考虑将 $2*(h_x + h_y) $ 和 $dis(x,y)$ 分别最大化。

显然将他们两个分别最大化的情况下，最大化的结果的 $x,y$ 坐标很有可能不是同一对。

**假如两个最大值你不好同时查，就换成把最大化一个东西，再最小化另外一个并把加法做成减法**

绝活。

考虑 $dis(x, y)$ 怎么计算，设 $sum[]$ 是$d[]$ 的前缀和，那么 $dis(x,y) = sum[y] - sum[x]$

这个时候我们就是要让 $sum_y - sum_x + 2 * h_x + 2 * h_y$ 最大

套路：把跟同一个东西相关的东西一起处理

现在变成了：$sum_y + 2 * h_y - sum_x + 2 * h_x$ 最大。那就让 $sum_y + 2 * h_y$ 最大，$sum_x + 2 * h_y$ 最小

因为没有修改操作，RMQ问题就可以用ST表，也可以用线段树之类的。

同时注意到刚才我们要查的是位置，所以维护RMQ信息的时候要维护的是RMQ的下标。

## Code

我实现用的线段树，比较好懂。用魔力`ae86`快读以后吊打ST表做法。

```cpp
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int SIZE = 2e5 + 5;
const int inf = 1e18;

int n, m;
int d[SIZE], h[SIZE], sumMin[SIZE], sumMax[SIZE];

struct node {
	int l, r, maxx, minn;
} tree[SIZE << 2];

inline int getMax(int x, int y)
{
	return sumMax[x] > sumMax[y] ? x : y;
}

inline int getMin(int x, int y)
{
	return sumMin[x] < sumMin[y] ? x : y;
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1

inline void pushUp(int p)
{
	tree[p].maxx = getMax(tree[lson(p)].maxx, tree[rson(p)].maxx);
	tree[p].minn = getMin(tree[lson(p)].minn, tree[rson(p)].minn);
}

inline int calcMin(int l, int r)
{
	if (l > r) return 0;
	return queryMin(1, l, r);
}

inline int calcMax(int l, int r)
{
	if (l > r) return 0;
	return queryMax(1, l, r);
}

CF515E Drazil and Park

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

CF1327F AND Segments

51nod 1480 打广告

APIO2021 机房游记

Luogu3251 [JLOI2012]时间流逝

Luogu1286 两数之和

CF515E Drazil and Park

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

CF515E Drazil and Park

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款