#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 200017 
#define ll long long
using namespace std;

int n;ll a[N],sum[N]; 

int binary_search(int l,int r){//找到第一个比 avg 大的 pos 
	ll avg = (sum[r]-sum[l-1])/2;
	int st = l-1,opt = -1;
	while(l <= r){
		int mid = (l+r)>>1;
		if(mid == opt)break;opt = mid;
		if(sum[mid]-sum[st] >= avg)r = mid;
		else l = mid+1;
	}
	if(sum[min(l,r)]-sum[st] >= avg)return min(l,r);
	else return max(l,r);
}

int main()
{
	cin >> n;
	for(int i = 1;i <= n;i += 1){
		cin >> a[i];
		sum[i] = sum[i-1] + a[i];
	}
	int q,l,r;cin >> q;
	for(int i = 1;i <= q;i += 1){
		cin >> l >> r;
		int p = binary_search(l,r);
		ll res = 0;
		if(p-1 >= l)res = max(res,(sum[p-1]-sum[l-1])*(sum[r]-sum[p-1]));
		if(p < r)res = max(res,(sum[p]-sum[l-1])*(sum[r]-sum[p]));
		cout << res << '\n';
	}
	return 0;
}

Solution

$sum = a+b$，要想使得$a*b$尽可能大，则$a,b$应该尽可能靠近

$avg = \frac{\sum_{li}^{ri}}{2}$，那么 $\sum_{l}^{p} a_i$ 应该尽量靠近$avg$

我们设从$pos$开始第一次 $\geq avg$

由于$\sum$具有单调性，不妨采用二分查找$pos$

注意：

1.第一个比$avg$小的和第一个比$avg$大的都有可能是答案

2.注意$p$不要超过$[l,r]$的限制