Codeforces 515E Drazil and Park （ST表）

题目链接 Drazil and Park

中文题面 传送门

如果他选择了x和y，那么他消耗的能量为d + d + ... + d + 2 * (h + h).

把这个式子写成这个形式

(d + d + ... + d + 2 * h) + (2 * h - (d + d + ... + d))

令(2 * h - (d + d + ... + d)) = L

   (d + d + ... + d + 2 * h) = R

我们在查询的时候，就要在[a, b]内找到u, v 使得L[u] + R[v] 最大

而当 u < v 的时候，总有 L[u] + R[v] > L[v] + R[u]

那我们放心地在[a, b]这个区间内找u和v，使L[u]和R[v]分别为这段区间上的最大值

这个过程用ST表维护即可。

但是我们要注意u = v的情况，也就是说求出来的u和v可能相等。

而题目的要求是u和v必须不相等

那么这个时候我们分类讨论一下，把[a, b]在u这一点分割成两个区间，在[a, u - 1]和[u + 1, b]里去找v

同理把[a, b]在v这一点分割成两个区间，在[a, v - 1]和[v + 1, b]里去找u

问题就这么解决了

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

typedef long long LL;

typedef pair <LL, int> PII;

const int N = 2e5 + 10;

const int A = 19;

int n, m;

LL d[N], h[N], s[N];

PII x[N], y[N], f[N][A], g[N][A];

int L, R;

int et;

void ST(){

	rep(i, 1, n) f[i][0] = x[i];

	rep(j, 1, 18)

		rep(i, 1, n)

			if ((i + (1 << j) - 1) <= n) f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

	rep(i, 1, n) g[i][0] = y[i];

	rep(j, 1, 18)

		rep(i, 1, n)

			if ((i + (1 << j) - 1) <= n) g[i][j] = max(g[i][j - 1], g[i + (1 << (j - 1))][j - 1]);

}

inline PII Xmax(int l, int r){

	if (l > r) return make_pair(-1e18, 0);

	int k = (int)log2((double)(r - l + 1));

	return max(f[l][k], f[r - (1 << k) + 1][k]);

}

inline PII Ymax(int l, int r){

	if (l > r) return make_pair(-1e18, 0);

	int k = (int)log2((double)(r - l + 1));

	return max(g[l][k], g[r - (1 << k) + 1][k]);

}

LL solve(int l, int r){

	PII n1 = Xmax(l, r), n2 = Ymax(l, r);

	if (n1.second != n2.second) return n1.first + n2.first;

	PII n3 = max(Ymax(l, n1.second - 1), Ymax(n1.second + 1, r));

	PII n4 = max(Xmax(l, n2.second - 1), Xmax(n2.second + 1, r));

	return max(n1.first + n3.first, n2.first + n4.first);

}

int main(){

	scanf("%d%d", &n, &m);

	rep(i, 1, n) scanf("%lld", d + i);

	rep(i, 1, n) scanf("%lld", h + i);

	rep(i, n + 1, n << 1) d[i] = d[i - n];

	rep(i, n + 1, n << 1) h[i] = h[i - n];

	rep(i, 2, n << 1) s[i] = s[i - 1] + d[i - 1];

	rep(i, 1, n << 1) x[i] = make_pair(2 * h[i] + s[i], i);

	rep(i, 1, n << 1) y[i] = make_pair(2 * h[i] - s[i], i);

	et = n;

	n <<= 1;

	ST();

	n = et;

	while (m--){

		int l, r;

		scanf("%d%d", &l, &r);

		if (r >= l) L = r + 1, R = l - 1 + n; else L = r + 1, R = l - 1;

		printf("%d %d\n", L, R);

		printf("%lld\n", solve(L, R));

	}

	return 0;

}