515E - Drazil and Park - CodeForces Solution

#include<bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5, SQ = 450;
long long d[N], ans[SQ], mn[SQ], mx[SQ];
int n, m, h[N];

inline long long get(int st, int en) {
	int l = en + 1, r = n + st;
	long long res = 0, x = 1e18;
	for (; l < r && l % SQ; x = min(x, d[l] - 2 * h[l]), l++)
		res = max(res, d[l] + 2 * h[l] - x);
	for (int i = l / SQ; i < r / SQ; x = min(x, mn[i++]), l += SQ)
		res = max(res, max(ans[i], mx[i] - x));
	for (; l < r; x = min(x, d[l] - 2 * h[l]), l++)
		res = max(res, d[l] + 2 * h[l] - x);
	return res;
}

inline void read_input() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> d[i];
		d[n + i] = d[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> h[i];
		h[n + i] = h[i];
	}
}

inline void solve() {
	memset(mn, 63, sizeof mn);
	partial_sum(d, d + n + n, d);
	for (int i = 0; i < SQ; i++)
		for (int j = i * SQ; j < min(i * SQ + SQ, n + n); j++) {
			mx[i] = max(mx[i], d[j] + 2 * h[j]);
			ans[i] = max(ans[i], d[j] + 2 * h[j] - mn[i]);
			mn[i] = min(mn[i], d[j] - 2 * h[j]);
		}
}

inline void write_output() {
	while (m--) {
		int a, b;
		cin >> a >> b;
		if (--a > --b)
			b += n;
		cout << get(a, b) << endl;
	}
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve(), write_output();
	return 0;
}