1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105
| #include <bits/stdc++.h> #define MAXN 50005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } int a[MAXN]; namespace SegmentTree{ struct node{ int l,r; int lmax,rmax,maxn; int val; }tree[MAXN<<2]; node empty_node(){ node temp; temp.l=temp.r=temp.lmax=temp.rmax=temp.maxn=temp.val=0; return temp; } void Init(){ memset(tree,0,sizeof(tree)); } #define lc i<<1 #define rc i<<1|1 node operator + (node A,node B){ node temp; temp.lmax=max(B.lmax+A.val,A.lmax); temp.rmax=max(A.rmax+B.val,B.rmax); temp.maxn=max(max(A.maxn,B.maxn),A.rmax+B.lmax); temp.val=A.val+B.val; temp.l=A.l,temp.r=B.r; return temp; } void pushup(int i){ tree[i]=tree[lc]+tree[rc]; } void Build(int l,int r,int i){ if (l==r){ tree[i].lmax=tree[i].rmax=tree[i].maxn=tree[i].val=a[l]; tree[i].l=tree[i].r=l; return ; } int mid=(l+r)>>1; Build(l,mid,lc); Build(mid+1,r,rc); pushup(i); } node TEMPQuery(int L,int R,int i){ if (L>R) return empty_node(); if (L<=tree[i].l&&tree[i].r<=R){ return tree[i]; } int mid=(tree[i].l+tree[i].r)>>1; if (L>mid) return TEMPQuery(L,R,rc); else if (R<=mid) return TEMPQuery(L,R,lc); else return TEMPQuery(L,R,lc)+TEMPQuery(L,R,rc); } node Query(int L,int R){ return TEMPQuery(L,R,1); } }; using namespace SegmentTree; inline int Get_Ans(int l1,int r1,int l2,int r2){ if (r1==l2) return Query(l1,r1).rmax+Query(l2,r2).lmax-a[r1]; return Query(l1,r1).rmax+Query(r1+1,l2-1).val+Query(l2,r2).lmax; } inline int Solve(int l1,int r1,int l2,int r2){ if (l1==l2&&r1==r2){ return Query(l1,r1).maxn; } if (r1<l2){ return Get_Ans(l1,r1,l2,r2); } else { int ans=Query(l2,r1).maxn; ans=max(ans,Get_Ans(l1,l2,l2,r2)); ans=max(ans,Get_Ans(l1,r1,r1,r2)); return ans; } } int main(){ int Case=read(); for (register int k=1;k<=Case;++k){ int n=read(); for (register int i=1;i<=n;++i){ a[i]=read(); } Init(); Build(1,n,1); int q=read(); while (q--){ int l1=read(),r1=read(),l2=read(),r2=read(); printf("%d\n",Solve(l1,r1,l2,r2)); } } }
|