SP1043 GSS1

题目描述

给出了序列\(A[1]，A[2]，…，A[N]。 (a[i]≤15007，1≤N≤50000)\)。查询定义如下： 查询\((x，y)=max{a[i]+a[i+1]+...+a[j]；x≤i≤j≤y}\)。 给定\(M\)个查询，程序必须输出这些查询的结果。

输入输出格式

输入格式：

• 输入文件的第一行包含整数\(N\)。
• 在第二行，\(N\)个数字跟随。
• 第三行包含整数\(M\)。
• \(M\)行跟在后面，其中第\(1\)行包含两个数字\(x_i\)和\(y_i\)。

输出格式：

您的程序应该输出\(M\)查询的结果，每一行一个查询。

输入输出样例

输入样例#1：

3 
-1 2 3
1
1 2

输出样例#1：

2

思路：一道线段树维护区间最大字段和的裸题，就是分三种情况讨论，完全在左子树，完全在右子树，或在左右子树之间。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 50007
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
int n,m;
struct Tree {
  int lmax,rmax,sum,maxx;
}tree[maxn<<2];
inline void pushup(int rt) {
  tree[rt].lmax=max(tree[ls].lmax,tree[ls].sum+tree[rs].lmax);
  tree[rt].rmax=max(tree[rs].rmax,tree[rs].sum+tree[ls].rmax);
  tree[rt].maxx=max(tree[ls].rmax+tree[rs].lmax,max(tree[ls].maxx,tree[rs].maxx));
  tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int rt, int l, int r) {
  if(l==r) {
    tree[rt].lmax=tree[rt].rmax=tree[rt].sum=tree[rt].maxx=qread();
    return;
  }
  int mid=(l+r)>>1;
  build(ls,l,mid);
  build(rs,mid+1,r);
  pushup(rt);
}
Tree query(int rt, int l, int r, int L, int R) {
  if(L==l&&r==R) return tree[rt];
  int mid=(l+r)>>1;
  if(L>mid) return query(rs,mid+1,r,L,R);
  else if(R<=mid) return query(ls,l,mid,L,R);
  else {
    Tree a=query(ls,l,mid,L,mid),b=query(rs,mid+1,r,mid+1,R),c;
    c.lmax=max(a.lmax,a.sum+b.lmax);
    c.rmax=max(b.rmax,b.sum+a.rmax);
    c.sum=a.sum+b.sum;
    c.maxx=max(a.rmax+b.lmax,max(a.maxx,b.maxx));
    return c;
  }
}
int main() {
  n=qread();
  build(1,1,n);
  m=qread();
  for(int i=1,x,y;i<=m;++i) {
    x=qread(),y=qread();
    printf("%d\n",query(1,1,n,x,y).maxx);
  }
  return 0;
}