[Luogu] CF515E Drazil and Park

\(Link\)

Description

There is a monkey. He lives in a circular park. There are \ (n \) trees around the park. The distance between the \ (I \) th tree and the \ (i+1 \) th tree is \ (d_i \), while the distance between the \ (n \) th tree and the first tree is \ (d_n \). The height of the \ (I \) th tree is \ (h_i \).

The monkey runs every morning. The steps of morning running are as follows:

  • He chose two trees first;
  • Then climb the first tree;
  • Then get down from the first tree, then run around the park (there are two possible directions) to the second tree, and then climb the second tree;
  • Finally, he came down from the second tree.

But some children will play on some continuous trees. So monkeys can't pass through these trees.

For example, if the monkey chooses the \ (x \) and \ (Y \) trees, the energy he consumes that morning is \ (2(h_x+h_y)+dist(x,y) \). Since one path is occupied by a child, he can only run another one, so \ (dist(x,y) \) is certain.

Now given the \ (I \) day, the children will play between the \ (a_i \) tree and the \ (b_i \) tree. Specifically, if \ (a_i ≤ b_i \), the child's play interval is \ ([a_i,b_i] \), otherwise the child's play interval is \ ([ai,n] ⋃ [1,bi] \).

Please help the monkey find two trees so that he can use up the most energy when he runs in the morning.

Solution

You may think of maximizing separately, but the \ ((x,y) \) obtained at this time may not be the same pair.

So first break the ring into a chain, and then prefix and sum \ (d_i \). At this time, the topic is transformed into maximization \ (2h_x+2h_y+sum_y-sum_x \). Routine: handle the items of \ (x \) and \ (Y \) respectively. At this time, make \ (2h_y+sum_y \) the largest and \ (sum_x-2h_x \) the smallest. Just preprocess the \ (ST \) table.

It should be noted that first, according to the meaning of the question, the supplementary set of the query interval should be obtained, and then the calculated \ (x \), \ (y \) may be the same, which does not meet the meaning of the question. At this time, just query the maximum value in \ ([l,pos-1] \) and \ ([pos+1,r] \) respectively, and compare them in calculation. Therefore, the \ (ST \) table maintains the subscript of the maximum value.

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

int n, m, lg[200005], d[200005], h[200005];

ll s1[200005], s2[200005], sum[200005], mn[200005][20], mx[200005][20];

int read()
{
	int x = 0, fl = 1; char ch = getchar();
	while (ch < '0' || ch > '9') { if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') {x = (x << 1) + (x << 3) + ch - '0'; ch = getchar();}
	return x * fl;
}

int query1(int x, int y)
{
	if (x > y) return 0;
	int k = lg[y - x + 1];
	ll p = s1[mx[x][k]], q = s1[mx[y - (1 << k) + 1][k]];
	if (p > q) return mx[x][k];
	else return mx[y - (1 << k) + 1][k];
}

int query2(int x, int y)
{
	if (x > y) return 0;
	int k = lg[y - x + 1];
	ll p = s2[mn[x][k]], q = s2[mn[y - (1 << k) + 1][k]];
	if (p < q) return mn[x][k];
	else return mn[y - (1 << k) + 1][k];
}

int main()
{
	n = read(); m = read();
	for (int i = 1; i <= n; i ++ )
	{
		d[i % n + 1] = read();
		d[i % n + n + 1] = d[i % n + 1];
	}
	for (int i = 1; i <= n; i ++ )
	{
		h[i] = read();
		h[i] <<= 1;
		h[i + n] = h[i];
	}
	for (int i = 1; i <= (n << 1); i ++ )
		sum[i] = sum[i - 1] + (ll)(d[i]), lg[i] = (int)(log2((double)(i)));
	s1[0] = -2e15; s2[0] = 2e15;  
	for (int i = 1; i <= (n << 1); i ++ )
	{
		s1[i] = sum[i] + h[i];
		s2[i] = sum[i] - h[i];
		mn[i][0] = mx[i][0] = i; 
	}
	for (int j = 1; j <= 19; j ++ )
	{
		for (int i = 1; i + (1 << j) <= (n << 1); i ++ )
		{
			ll x, y;
			x = s1[mx[i][j - 1]], y = s1[mx[i + (1 << (j - 1))][j - 1]];
			if (x > y) mx[i][j] = mx[i][j - 1]; else mx[i][j] = mx[i + (1 << (j - 1))][j - 1];
			x = s2[mn[i][j - 1]], y = s2[mn[i + (1 << (j - 1))][j - 1]];
			if (x < y) mn[i][j] = mn[i][j - 1]; else mn[i][j] = mn[i + (1 << (j - 1))][j - 1];
		}
	}
	while (m -- )
	{
		int l = read(), r = read(), pos1, pos2;
		if (l <= r) pos1 = query1(r + 1, l + n - 1), pos2 = query2(r + 1, l + n - 1);
		else pos1 = query1(r + 1, l - 1), pos2 = query2(r + 1, l - 1);
		if (pos1 != pos2) printf("%lld\n", s1[pos1] - s2[pos2]);
		else
		{
			int pos3, pos4; ll res1, res2;
			if (l <= r)
			{
				pos3 = query1(r + 1, pos1 - 1), pos4 = query1(pos1 + 1, l + n - 1), res1 = max(s1[pos3], s1[pos4]) - s2[pos2];
				pos3 = query2(r + 1, pos2 - 1), pos4 = query2(pos2 + 1, l + n - 1), res2 = s1[pos1] - min(s2[pos3], s2[pos4]);
			}
			else
			{
				pos3 = query1(r + 1, pos1 - 1), pos4 = query1(pos1 + 1, l - 1), res1 = max(s1[pos3], s1[pos4]) - s2[pos2];
				pos3 = query2(r + 1, pos2 - 1), pos4 = query2(pos2 + 1, l - 1), res2 = s1[pos1] - min(s2[pos3], s2[pos4]);
			}
			printf("%lld\n", max(res1, res2));
		}
	}
	return 0;
}

Posted by Calahan on Sat, 07 May 2022 22:20:16 +0300