Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std;
const int N = 50100;
typedef long long ll;
ll sum[N << 2],pre_sum[N << 2],suf_sum[N << 2],sub_sum[N << 2],n,m;
inline ll read()
{
ll res = 0,flag = 1;
char ch = getchar();
while(ch < '0' || ch > '9')
{
if(ch == '-') flag = -1;
ch = getchar();
}
while(ch <= '9' && ch >= '0')
{
res = res*10 + ch - '0';
ch = getchar();
}
return res*flag;
}
void update(int rt)
{
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
pre_sum[rt] = max(pre_sum[rt<<1],sum[rt<<1] + pre_sum[rt<<1|1]);
suf_sum[rt] = max(suf_sum[rt<<1|1],suf_sum[rt<<1] + sum[rt<<1|1]);
sub_sum[rt] = max(suf_sum[rt<<1] + pre_sum[rt<<1|1],max(sub_sum[rt<<1],sub_sum[rt<<1|1]));
}
void build(int l,int r,int rt)
{
if(l == r)
{
pre_sum[rt] = suf_sum[rt] = sub_sum[rt] = sum[rt] = read();
return;
}
int mid = (l+r)>>1;
build(lson);
build(rson);
update(rt);
}
ll query_pre(int l,int r,int rt,int ql,int qr)
{
if(ql <= l && r <= qr) return pre_sum[rt];
int mid = (l+r)>>1;
if(qr <= mid) return query_pre(lson,ql,qr);
return max(query_pre(lson,ql,qr),sum[rt<<1] + query_pre(rson,ql,qr));
}
ll query_suf(int l,int r,int rt,int ql,int qr)
{
if(ql <= l && r <= qr) return suf_sum[rt];
ll mid = (l+r)>>1;
if(mid < ql) return query_suf(rson,ql,qr);
return max(query_suf(rson,ql,qr),sum[rt<<1|1] + query_suf(lson,ql,qr));
}
ll query_sub(int l,int r,int rt,int ql,int qr)
{
if(ql <= l && r <= qr) return sub_sum[rt];
ll res = -9999999;
ll mid = (l+r)>>1;
if(ql <= mid) res = max(res,query_sub(lson,ql,qr));//
if(mid < qr) res = max(res,query_sub(rson,ql,qr));//
if(ql <= mid && mid < qr) res = max(res,query_suf(lson,ql,qr) + query_pre(rson,ql,qr));
return res;
}
int main()
{
n = read();
build(1,n,1);
m = read();
for(int i = 1;i <= m;++i)
{
ll l,r;
l = read();
r = read();
printf("%lld
",query_sub(1,n,1,l,r));
}
return 0;
}