You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Input
The first line of the input file contains the integer N.
In the second line, N numbers follow.
The third line contains the integer M.
M lines follow, where line i contains 2 numbers xi and yi.
Output
Your program should output the results of the M queries, one query per line.
Sample Input
3
-1 2 3
1
1 2
Sample Output
2
题意：
裸题，没有更新，只有查询。
思路：
区间中维护一下值：
从左端点开始的连续的最大值lm
从右端点开始的连续最大值rm
区间的和sum。
区间中的连续最大值num。
那么更新操作为：
lm=max（左儿子的lm，左儿子的sum+右儿子的lm）
rm=max（右儿子的rm，右儿子的sum+左儿子的rm）
num=max（左儿子的num，右儿子的num，左儿子的rm+右儿子的lm）
询问操作也返回区间，对区间进行合并处理操作。
细节见代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <vector>
#include <iomanip>
#define ALL(x) (x).begin(), (x).end()
#define sz(a) int(a.size())
#define all(a) a.begin(), a.end()
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define eps 1e-6
#define gg(x) getInt(&x)
#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}
ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}
ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}
inline void getInt(int* p);
const int maxn = 50000+7;
const int inf = 0x3f3f3f3f;
/*** TEMPLATE CODE * * STARTS HERE ***/
struct node
{
int l;
int r;
ll num;
ll lm;
ll sum;
ll rm;
}segment_tree[maxn<<2];
int n;
void pushup(int rt)
{
segment_tree[rt].sum=segment_tree[rt<<1].sum+segment_tree[rt<<1|1].sum;
segment_tree[rt].lm=max(segment_tree[rt<<1].lm,segment_tree[rt<<1].sum+segment_tree[rt<<1|1].lm);
segment_tree[rt].rm=max(segment_tree[rt<<1|1].rm,segment_tree[rt<<1|1].sum+segment_tree[rt<<1].rm);
segment_tree[rt].num=max(segment_tree[rt<<1].num,segment_tree[rt<<1|1].num);
segment_tree[rt].num=max(segment_tree[rt].num,segment_tree[rt<<1].rm+segment_tree[rt<<1|1].lm);
}
void build(int rt,int l,int r)
{
segment_tree[rt].l=l;
segment_tree[rt].r=r;
if(l==r)
{
scanf("%lld",&segment_tree[rt].num);
segment_tree[rt].lm=segment_tree[rt].rm=segment_tree[rt].num;
segment_tree[rt].sum=segment_tree[rt].num;
return ;
}
int mid=(l+r)>>1;
build(rt<<1,l,mid);
build(rt<<1|1,mid+1,r);
pushup(rt);
}
node ask(int rt,int l,int r)
{
if(segment_tree[rt].l==l&&segment_tree[rt].r==r)
{
return segment_tree[rt];
}
int mid=(segment_tree[rt].r+segment_tree[rt].l)>>1;
if(l>mid)
{
return ask(rt<<1|1,l,r);
}else if(r<=mid)
{
return ask(rt<<1,l,r);
}else
{
node res1=ask(rt<<1,l,mid);
node res2=ask(rt<<1|1,mid+1,r);
node res;
res.sum=res1.sum+res2.sum;
res.lm=max(res1.lm,res1.sum+res2.lm);
res.rm=max(res2.rm,res2.sum+res1.rm);
res.num=max(res1.num,res2.num);
res.num=max(res.num,res1.rm+res2.lm);
return res;
}
}
int main()
{
//freopen("D:\\code\\text\\input.txt","r",stdin);
//freopen("D:\\code\\text\\output.txt","w",stdout);
scanf("%d",&n);
build(1,1,n);
int m;
scanf("%d",&m);
while(m--)
{
int x,y;
scanf("%d %d",&x,&y);
printf("%lld\n",ask(1,x,y).num);
}
return 0;
}
inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '0');
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 - ch + '0';
}
}
else {
*p = ch - '0';
while ((ch = getchar()) >= '0' && ch <= '9') {
*p = *p * 10 + ch - '0';
}
}
}