F 小红的数组
直接用线段树来写,因为本道题如果没有abs的话,我们可以类似之前做过的 你能回答这些问题吗 这道题异曲同工之妙,相比更简单,但本道题多了abs,我们该怎么做呢,你不就多了个abs,我们此时尝试取个反,这样不久满足abs了,abs(x),此时x=±x,那么,我们的答案就是max(取反前,取反后)。
//建立线段树
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
#define int long long
const int N = 5e5+10;
struct E{
int l,r;
int ms1,ms2;
int ls1,ls2;
int rs1,rs2;
int sum1,sum2;
}tr[N<<2];
int n,m;
int a[N],b[N];
void pushup(E& root,E& left,E& right){
root.sum1=left.sum1+right.sum1;
root.ls1=max(left.ls1, left.sum1+right.ls1);
root.rs1=max(right.rs1, right.sum1+left.rs1);
root.ms1=max(max(left.ms1, right.ms1), left.rs1+right.ls1);
root.sum2=left.sum2+right.sum2;
root.ls2=max(left.ls2, left.sum2+right.ls2);
root.rs2=max(right.rs2, right.sum2+left.rs2);
root.ms2=max(max(left.ms2, right.ms2), left.rs2+right.ls2);
}
void pushup(int u){
pushup(tr[u],tr[u<<1],tr[u<<1|1]);
}
void build(int u,int l,int r){
if(l==r){
tr[u]={l,r,a[l],b[l],a[l],b[l],a[l],b[l],a[l],b[l]};
return;
}
tr[u]={l,r};
int mid=l+r>>1;
build(u<<1,l,mid),build(u<<1|1,mid+1,r);
pushup(u);
}
E query(int u,int l,int r){
if(tr[u].l>=l&&tr[u].r<=r){
return tr[u];
}
int mid=tr[u].l+tr[u].r>>1;
if(l>mid)return query(u<<1|1,l,r);
if(r<=mid)return query(u<<1,l,r);
E L=query(u<<1,l,r);
E R=query(u<<1|1,l,r);
E res;
pushup(res,L,R);
return res;
}
signed main(){
// cin>>n;
scanf("%lld",&n);
for(int i=1;i<=n;i++){
// cin>>a[i];
scanf("%lld",&a[i]);
b[i]=-a[i];
}
build(1,1,n);
// cin>>m;
scanf("%lld",&m);
while(m--){
int l,r;
// cin>>l>>r;
scanf("%lld%lld",&l,&r);
E c=query(1,l,r);
int res=max(c.ms1,c.ms2);
// cout<<res<<endl;
printf("%lld\n",res);
}
return 0;
}