题解 gym102586B 【Evacaution】

我们已经知道记忆去。

显然最劣情况为：选定一个 $x \in [l, r]$，把人初始全放在 $x$。

注意到我们一定是沿着 $i \geq 0$，$x \pm i$ 向外扩展，于是：

• 当 $x \leq mid = \lfloor \frac{l + r}{2} \rfloor$，最终要么扩展到了 $< l$ 的位置、要么在 $[l, x]$ 中停下。
• 当 $x > mid$，最终要么扩展到了 $> r$ 的位置、要么在 $[x, r]$ 中停下。

两种情况本质相同，下面讨论 $x \leq mid$ 的情况。

设 $f(l, x)$ 表示选择 $x$ 开始扩展，左端点为 $l$ 的答案。

不难发现 $f(l, x)$ 关于 $l$ 的最优 $x$ 是关于 $l$ 单调递增的，但是 $x$ 的范围 $[l, mid]$ 不一定相同。

考虑线段树，把一个区间拆分到若干个线段树上的整区间，离线下来整体二分即可。

$f$ 是不难在 $O(n \log n)$ 预处理后 $O(1)$ 计算的，于是时间复杂度为 $O((n + q) \log^2 n)$。

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct {
	int l;
	int r;
	vector<int> v1;
	vector<int> v2;
} Node;

int pos[200007], l[200007], r[200007];
ll a[200007], sum1[200007], sum2[200007], val[200007], ans[200007];
Node tree[800007];

void build(int x, int l, int r){
	tree[x].l = l;
	tree[x].r = r;
	if (l == r) return;
	int mid = (l + r) >> 1;
	build(x * 2, l, mid);
	build(x * 2 + 1, mid + 1, r);
}

void insert1(int x, int l, int r, int k){
	if (l <= tree[x].l && tree[x].r <= r){
		tree[x].v1.push_back(k);
		return;
	}
	int mid = (tree[x].l + tree[x].r) >> 1;
	if (l <= mid) insert1(x * 2, l, r, k);
	if (r > mid) insert1(x * 2 + 1, l, r, k);
}

void insert2(int x, int l, int r, int k){
	if (l <= tree[x].l && tree[x].r <= r){
		tree[x].v2.push_back(k);
		return;
	}
	int mid = (tree[x].l + tree[x].r) >> 1;
	if (l <= mid) insert2(x * 2, l, r, k);
	if (r > mid) insert2(x * 2 + 1, l, r, k);
}

bool cmp1(const int a, const int b){
	return l[a] < l[b];
}

bool cmp2(const int a, const int b){
	return r[a] < r[b];
}

inline ll get(int x, int k, ll s){
	return ((sum2[x + k] - sum2[x]) - x * (sum1[x + k] - sum1[x])) + (x * (sum1[x - 1] - sum1[x - k - 1]) - (sum2[x - 1] - sum2[x - k - 1])) + (k + 1) * (s - (sum1[x + k] - sum1[x - k - 1]));
}

inline ll f(int l, int x, ll s){
	if (l <= x - pos[x]) return val[x];
	return get(x, x - l, s);
}

void solve1(int L, int R, ll s, vector<int> v1){
	if (v1.empty()) return;
	int size = v1.size();
	if (L == R){
		for (register int i = 0; i < size; i++){
			ans[v1[i]] = max(ans[v1[i]], f(l[v1[i]], L, s));
		}
		return;
	}
	int mid = size >> 1, max_pos;
	ll max_val = -1;
	vector<int> v2, v3;
	for (register int i = 0; i < mid; i++){
		v2.push_back(v1[i]);
	}
	for (register int i = mid + 1; i < size; i++){
		v3.push_back(v1[i]);
	}
	for (register int i = L; i <= R; i++){
		ll cur_val = f(l[v1[mid]], i, s);
		if (max_val < cur_val){
			max_val = cur_val;
			max_pos = i;
		}
	}
	ans[v1[mid]] = max(ans[v1[mid]], max_val);
	solve1(L, max_pos, s, v2);
	solve1(max_pos, R, s, v3);
}

inline ll g(int x, int r, ll s){
	if (r >= x + pos[x]) return val[x];
	return get(x, r - x, s);
}

void solve2(int L, int R, ll s, vector<int> v1){
	if (v1.empty()) return;
	int size = v1.size();
	if (L == R){
		for (register int i = 0; i < size; i++){
			ans[v1[i]] = max(ans[v1[i]], g(L, r[v1[i]], s));
		}
		return;
	}
	int mid = size >> 1, max_pos;
	ll max_val = -1;
	vector<int> v2, v3;
	for (register int i = 0; i < mid; i++){
		v2.push_back(v1[i]);
	}
	for (register int i = mid + 1; i < size; i++){
		v3.push_back(v1[i]);
	}
	for (register int i = L; i <= R; i++){
		ll cur_val = g(i, r[v1[mid]], s);
		if (max_val < cur_val){
			max_val = cur_val;
			max_pos = i;
		}
	}
	ans[v1[mid]] = max(ans[v1[mid]], max_val);
	solve2(L, max_pos, s, v2);
	solve2(max_pos, R, s, v3);
}

void dfs(int x, ll s){
	if (!tree[x].v1.empty()){
		sort(tree[x].v1.begin(), tree[x].v1.end(), cmp1);
		solve1(tree[x].l, tree[x].r, s, tree[x].v1);
	}
	if (!tree[x].v2.empty()){
		sort(tree[x].v2.begin(), tree[x].v2.end(), cmp2);
		solve2(tree[x].l, tree[x].r, s, tree[x].v2);
	}
	if (tree[x].l < tree[x].r){
		dfs(x * 2, s);
		dfs(x * 2 + 1, s);
	}
}

int main(){
	int n, ni, q;
	ll s;
	scanf("%d %lld", &n, &s);
	ni = n + 1;
	a[0] = a[ni] = s;
	for (register int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
	}
	sum1[0] = s;
	for (register int i = 1; i <= ni; i++){
		sum1[i] = sum1[i - 1] + a[i];
		sum2[i] = sum2[i - 1] + i * a[i];
	}
	for (register int i = 1; i <= n; i++){
		int l = 0, r = min(i, ni - i);
		while (l <= r){
			int mid = (l + r) >> 1;
			if (sum1[i + mid] - (mid == i ? 0 : sum1[i - mid - 1]) >= s){
				r = mid - 1;
				pos[i] = mid;
			} else {
				l = mid + 1;
			}
		}
		val[i] = get(i, pos[i] - 1, s);
	}
	build(1, 1, n);
	scanf("%d", &q);
	for (register int i = 1; i <= q; i++){
		int mid;
		scanf("%d %d", &l[i], &r[i]);
		mid = (l[i] + r[i]) / 2;
		insert1(1, l[i], mid, i);
		if (mid < r[i]) insert2(1, mid + 1, r[i], i);
	}
	dfs(1, s);
	for (register int i = 1; i <= q; i++){
		cout << ans[i] << endl;
	}
	return 0;
}