给出了序列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个查询，程序必须输出这些查询的结果。
这就是一个最大子段和，用线段树就能直接搞掉
然后这里学习了一下一个叫做猫树的神奇东西->这里
能做到预处理之后查询$O(1)$
//minamoto
#include<iostream>
#include<cstdio>
using namespace std;
#define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
int read(){
#define num ch-'0'
char ch;bool flag=;int res;
while(!isdigit(ch=getc()))
(ch=='-')&&(flag=true);
for(res=num;isdigit(ch=getc());res=res*+num);
(flag)&&(res=-res);
#undef num
return res;
}
char sr[<<],z[];int C=-,Z;
inline void Ot(){fwrite(sr,,C+,stdout),C=-;}
void print(int x){
if(C><<)Ot();if(x<)sr[++C]=,x=-x;
while(z[++Z]=x%+,x/=);
while(sr[++C]=z[Z],--Z);sr[++C]='\n';
}
const int N=5e+;
int n,m,a[N],len,log[N],pos[N],p[][N],s[][N];
void build(int pp,int l,int r,int d){
if(l==r) return (void)(pos[l]=pp);
int mid=(l+r)>>,prep,sm;
p[d][mid]=s[d][mid]=sm=prep=a[mid];
if(sm<) sm=;
for(int i=mid-;i>=l;--i){
prep+=a[i],sm+=a[i];
s[d][i]=max(s[d][i+],prep),
p[d][i]=max(p[d][i+],sm);
if(sm<) sm=;
}
p[d][mid+]=s[d][mid+]=sm=prep=a[mid+];
if(sm<) sm=;
for(int i=mid+;i<=r;++i){
prep+=a[i],sm+=a[i];
s[d][i]=max(s[d][i-],prep),
p[d][i]=max(p[d][i-],sm);
if(sm<) sm=;
}
build(pp<<,l,mid,d+);
build(pp<<|,mid+,r,d+);
}
int query(int l,int r){
if(l==r) return a[l];
int d=log[pos[l]]-log[pos[l]^pos[r]];
return max(max(p[d][l],p[d][r]),s[d][l]+s[d][r]);
}
int main(){
// freopen("testdata.in","r",stdin);
n=read();for(int i=;i<=n;++i) a[i]=read();
len=;while(len<n) len<<=;
for(int i=,l=len<<;i<=l;++i) log[i]=log[i>>]+;
build(,,len,);
m=read();
while(m--){
int l=read(),r=read();
print(query(l,r));
}
return Ot(),;
}