# 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; }