二楼代码好习惯
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=100001;
struct tree{
int lmax,rmax,l,r,sum,max;
}segment[maxn<<2];
int n,m,l,r;
inline void build_tree(int rt,int l,int r);
inline void update(int rt);
inline tree query(int rt,int l,int r);
int main()
{
cin>>n;
build_tree(1,1,n);
cin>>m;
for (register int i=1;i<=m;i++)
{
cin>>l>>r;
cout<<query(1,l,r).max<<endl;
}
}
inline void update(int rt)
{
const int lson=rt*2,rson=rt*2+1;
segment[rt].sum=segment[lson].sum+segment[rson].sum;
segment[rt].lmax=max(segment[lson].lmax,segment[lson].sum+segment[rson].lmax);
segment[rt].rmax=max(segment[rson].rmax,segment[rson].sum+segment[lson].rmax);
segment[rt].max=max(segment[lson].rmax+segment[rson].lmax,max(segment[lson].max,segment[rson].max));
segment[rt].max=max(segment[rt].max,max(segment[rt].lmax,segment[rt].rmax));
}
inline void build_tree(int rt,int l,int r)
{
segment[rt].l=l,segment[rt].r=r;
if (l==r)
{
int data;cin>>data;
segment[rt].sum=segment[rt].lmax=segment[rt].rmax=segment[rt].sum;
return ;
}
int mid=(r+l)>>1;
build_tree(rt*2,l,mid);
build_tree(rt*2+1,mid+1,r);
update(rt);
}
inline tree query(int rt,int l,int r)
{
if (l==r)
{
return segment[rt];
}
int mid=(r+l)>>1,lson=rt*2,rson=rt*2+1;
if (l>mid)
{
return query(rson,l,r);
}
else if (r<=mid)
{
return query(lson,l,r);
}
else
{
tree ltree=query(lson,l,mid);
tree rtree=query(rson,mid+1,r);
tree temp;
temp.sum=ltree.sum+rtree.sum;
temp.lmax=max(ltree.lmax,ltree.sum+rtree.lmax);
temp.rmax=max(rtree.rmax,rtree.sum+ltree.rmax);
temp.max=max(ltree.rmax+rtree.lmax,max(ltree.max,rtree.max));
temp.max=max(temp.max,max(temp.lmax,temp.rmax));
return temp;
}
}
```
by Jelly_Goat @ 2019-02-16 17:16:22
切紫题的大佬%%%
by 绝顶我为峰 @ 2019-02-16 17:38:44