```cpp
#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,p[21][200010],s[21][200010],log[200010],pos[200010],a[200010],m,len=2;
void build_tree(int o,int l,int r,int dep){
if(l==r){
pos[l]=o;
return;
}
int mid=l+r>>1;
p[dep][mid]=s[dep][mid]=a[mid];
int prep=a[mid],sm=a[mid];
if(sm<0)sm=0;
for(int i=mid-1;i>=l;i--){
prep+=a[i];sm+=a[i];
s[dep][i]=max(s[dep][i+1],prep);
p[dep][i]=max(p[dep][i+1],sm);
if(sm<0)sm=0;
}
p[dep][mid+1]=s[dep][mid+1]=a[mid+1];
prep=sm=a[mid+1];
if(sm<0)sm=0;
for(int i=mid+2;i<=r;i++){
prep+=a[i];sm+=a[i];
s[dep][i]=max(s[dep][i-1],prep);
p[dep][i]=max(p[dep][i-1],sm);
if(sm<0)sm=0;
}
build_tree(o<<1,l,mid,dep+1);
build_tree(o<<1|1,mid+1,r,dep+1);
}
int query(int l,int r){
if(l==r)return a[l];
int x=log[pos[l]]-log[pos[l]^pos[r]];
return max(max(p[x][l],p[x][r]),s[x][l]+s[x][r]);
}
int main(){
scanf("%d",&n);
while(len<n)len<<=1;
len<<=1;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=2;i<=len;i++)log[i]=log[i<<1]+1;
build_tree(1,1,len>>1,1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",query(x,y));
}
return 0;
}
```
by Smile_Cindy @ 2019-07-19 20:58:30
%%%
by charliegong @ 2019-07-19 21:01:04
猫树。。。那是啥？
by LightningUZ @ 2019-07-19 21:04:00
写猫树的神仙orz
by 枫初音斗颂皮 @ 2019-07-19 21:06:44
@[LightningUZ](/space/show?uid=106252) 快速合并不支持修改的数据结构
by 枫初音斗颂皮 @ 2019-07-19 21:07:05
tql%%%，我还是太蒻了
by LightningUZ @ 2019-07-19 21:15:18
~~珂是这题您完全珂以用线段树~~
by LightningUZ @ 2019-07-19 21:15:38
~~我就是用线段树过去的~~
by LightningUZ @ 2019-07-19 21:15:49
@[_gifbmp](/space/show?uid=208560) 线段树多好啊
by Kubic @ 2019-07-19 21:30:55
珂我就是想练猫树啊
by _gifbmp @ 2019-07-19 21:37:48