# 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 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()
{
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] <<= 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 -- )
{
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