线段树--SP2916 GSS5 - Can you answer these queries V

本文主要是介绍线段树--SP2916 GSS5 - Can you answer these queries V，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
以前讲过的题，会最大子段和然后分类讨论一下就好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define N 10005
#define ls cur<<1
#define rs cur<<1|1
#define int long long
using namespace std;inline int rd(){int x=0,f=1;char c=' ';while(c<'0' || c>'9') f=c=='-'?-1:1,c=getchar();while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*f;
}int t,n,m,a[N];struct Node{int l,r,sum,mx,lmx,rmx;Node(){l=r=sum=mx=lmx=rmx=0;}
}node[N<<2];inline void pushup(int cur){node[cur].sum=node[ls].sum+node[rs].sum;node[cur].lmx=max(node[ls].lmx,node[ls].sum+node[rs].lmx);node[cur].rmx=max(node[rs].rmx,node[rs].sum+node[ls].rmx);node[cur].mx=max(max(node[ls].mx,node[rs].mx),node[ls].rmx+node[rs].lmx);
}void build(int cur,int L,int R){if(L==R){node[cur].l=node[cur].r=L;node[cur].sum=node[cur].mx=node[cur].lmx=node[cur].rmx=a[L];return;}int mid=(L+R)>>1;build(ls,L,mid); build(rs,mid+1,R);node[cur].l=node[ls].l,node[cur].r=node[rs].r;pushup(cur); return;
}Node query(int cur,int L,int R){if(L<=node[cur].l && node[cur].r<=R) return node[cur];int mid=(node[cur].l+node[cur].r)>>1;if(R<=mid) return query(ls,L,R);if(L>mid) return query(rs,L,R);Node x,y,res;x=query(ls,L,R); y=query(rs,L,R);res.sum=x.sum+y.sum;res.lmx=max(x.lmx,x.sum+y.lmx);res.rmx=max(y.rmx,y.sum+x.rmx);res.mx=max(max(x.mx,y.mx),x.rmx+y.lmx);return res;
}signed main(){t=rd();int x1,x2,y1,y2;while(t--){n=rd();for(int i=1;i<=n;i++) a[i]=rd();build(1,1,n);m=rd();while(m--){x1=rd(),y1=rd(),x2=rd(),y2=rd();if(y1+1<x2) printf("%lld\n",query(1,x1,y1).rmx+query(1,y1+1,x2-1).sum+query(1,x2,y2).lmx);else if(x1==x2 && y1==y2) printf("%lld\n",query(1,x2,y2).mx);else if(x1<=x2 && y1>=y2){Node x=x1<x2?query(1,x1,x2-1):x,y=query(1,x2,y2);printf("%lld\n",max(x.rmx+y.lmx,y.mx));}else if(x1>=x2 && y1<=y2){Node x=query(1,x1,y1),y=y1<y2?query(1,y1+1,y2):y;printf("%lld\n",max(x.rmx+y.lmx,x.mx));}else{Node x,y,z; int ans=0;if(x1<x2) x=query(1,x1,x2-1);else x.rmx=0;y=query(1,x2,y2); ans=x.rmx+y.lmx;x=query(1,x1,y1); if(x2<=y1) y=query(1,x2,y1),ans=max(ans,y.mx);if(y1<y2) z=query(1,y1+1,y2);else z.lmx=0;ans=max(ans,x.rmx+z.lmx);printf("%lld\n",ans);}}}return 0;
}

这篇关于线段树--SP2916 GSS5 - Can you answer these queries V的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---