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表做法。
#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;
}