{"id":46,"date":"2009-11-27T21:35:00","date_gmt":"2009-11-27T13:35:00","guid":{"rendered":"http:\/\/localhost\/?p=46"},"modified":"2009-11-27T21:35:00","modified_gmt":"2009-11-27T13:35:00","slug":"spoj_2916_gss5","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/wjmzbmr\/?p=46","title":{"rendered":"SPOJ 2916 GSS5"},"content":{"rendered":"

https:\/\/www.spoj.pl\/problems\/GSS5\/
\u8fd9\u9053\u9898\u4e0d\u96be\u5173\u952e\u662f\u6211\u8fd9\u4e2a\u5199\u6cd5\u3002\u3002
\u5b9e\u5728\u662f\u592aNB\u4e86\u3002\u3002\uff08\u8fd9\u4e2a\u70e7\u997c\u75af\u4e86\u3002\u3002\uff09
\u9996\u5148\u5f88\u660e\u663e\u5982\u679cy1<x2\u7684\u8bdd\u3002\u3002
\u8bbeS\u4e3a\u90e8\u5206\u548c\u5e8f\u5217\u3002\u3002\u90a3\u4e48ans=Max(S,x2..y2)-Min(S,x1-1..y1-1..)\u3002\u3002
\u5982\u679c\u6709\u91cd\u53e0\u7684\u8bdd\u3002\u3002\u5206\u4e09\u79cd\u60c5\u51b5\u8ba8\u8bba\u3002\u3002\u8bbe\u7b54\u6848\u662fAi..Aj
i<x2,ans=Max(S,x2..y2)-Min(S,x1-1..x2-1)
j>y1,ans=Max(S,y1+1..y2)-Min(S,x1-1..y1-1..)
i>=x2&&j<=y \u8f6c\u5316\u6210\u7ecf\u5178\u95ee\u9898\u4e86\u3002\u3002\u3002
\u5982\u679c\u76f4\u63a5\u51993\u4e2a\u7ebf\u6bb5\u6811\u4f1a\u5f88BT\u3002\u3002\u53ea\u5199\u4e00\u4e2a\u7684\u8bdd\u53c8\u6d6a\u8d39\u65f6\u95f4\u3002\u3002
\u6211\u7684Code\u4e2d\u5199\u4e86\u4e2a\u7ebf\u6bb5\u6811\u7684\u6a21\u677f\u3002\u3002\u7136\u540e\u6839\u636e\u4fe1\u606f\u76f4\u63a5\u5f04\u51fa3\u4e2a\u7ebf\u6bb5\u6811\u3002\u3002NB\u963f\uff08\u3002\u3002\u3002\uff09<\/p>\n

#include<cstdio>
#include<iostream>
#define Renew(x,c) x=max(x,c)
using namespace std;
struct MinNum
{
int Min;
MinNum(int a=0):Min(a){}
MinNum operator+(const MinNum&Rch)
{
MinNum f;
f.Min=min(Min,Rch.Min);
return f;
}
};
struct MaxNum
{
int Max;
MaxNum(int a=0):Max(a){}
MaxNum operator+(const MaxNum&Rch)
{
MaxNum f;
f.Max=max(Max,Rch.Max);
return f;
}
};
struct ContMax
{
int Max,Lmax,Rmax,Sum;
ContMax(int a=0):Max(a),Lmax(a),Rmax(a),Sum(a){}
ContMax operator+(const ContMax&Rch)
{
ContMax f;
f.Lmax=max(Lmax,Sum+Rch.Lmax);
f.Rmax=max(Rch.Rmax,Rch.Sum+Rmax);
f.Sum=Sum+Rch.Sum;
f.Max=max(Max,Rch.Max);
f.Max=max(f.Max,Rmax+Rch.Lmax);
return f;
}
};
template<class info>
class Tree
{
int*A;int L,R;
struct tree
{
tree*Lch,*Rch;
info Ans;
tree(int a=0):Ans(a){}
}*root;
tree* build(int l,int r)
{
if(l==r) return new tree(A[l]);
int mid=(l+r)\/2;
tree* T=new tree;
T->Lch=build(l,mid);
T->Rch=build(mid+1,r);
T->Ans=T->Lch->Ans+T->Rch->Ans;
return T;
}
info ask(tree*T,int l,int r,int ll,int rr)
{
if(l==ll and r==rr) return T->Ans;
int mid=(l+r)\/2;
if(ll>mid) return ask(T->Rch,mid+1,r,ll,rr);
if(rr<=mid) return ask(T->Lch,l,mid,ll,rr);
return ask(T->Lch,l,mid,ll,mid)+ask(T->Rch,mid+1,r,mid+1,rr);
}
public:
Tree(int A[],int L,int R):A(A),L(L),R(R)
{
root=build(L,R);
}
info operator()(int l,int r)
{
return ask(root,L,R,l,r);
}
};
const int maxn=10000+100,inf=~0U>>1;
void solve()
{
int A[maxn],S[maxn],n;S[0]=0;
cin>>n;for(int i=1;i<=n;i++) scanf("%d",A+i),S[i]=A[i]+S[i-1];
Tree<MaxNum> RMQMax(S,0,n);
Tree<MinNum> RMQMin(S,0,n);
Tree<ContMax> SegTree(A,1,n);
int m,x1,y1,x2,y2;cin>>m;
while(m–)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);int ans=-inf;
if(x2>y1)
ans=RMQMax(x2,y2).Max-RMQMin(x1-1,y1-1).Min;
else
{
if(y1<y2) Renew(ans,RMQMax(y1+1,y2).Max-RMQMin(x1-1,y1-1).Min);
if(x1<x2) Renew(ans,RMQMax(x2,y2).Max-RMQMin(x1-1,x2-1).Min);
Renew(ans,SegTree(x2,y1).Max);
}
printf<\/a>("%dn",ans);
}
}
int main()
{
int t;cin>>t;
while(t–) solve();
} <\/p>\n","protected":false},"excerpt":{"rendered":"

https:\/\/www.spoj.pl\/problems\/GSS5\/\u8fd9\u9053\u9898\u4e0d\u96be\u5173\u952e\u662f\u6211\u8fd9\u4e2a\u5199\u6cd5\u3002\u3002\u5b9e\u5728\u662f\u592aNB\u4e86\u3002\u3002\uff08\u8fd9\u4e2a\u70e7\u997c\u75af\u4e86\u3002\u3002\uff09\u9996\u5148\u5f88\u660e\u663e\u5982\u679cy1<x2\u7684\u8bdd\u3002\u3002\u8bbeS\u4e3a\u90e8\u5206\u548c\u5e8f\u5217\u3002\u3002\u90a3\u4e48ans=Max(S,x2..y2)-Min(S,x1-1..y1-1..)\u3002\u3002\u5982\u679c\u6709\u91cd\u53e0\u7684\u8bdd\u3002\u3002\u5206\u4e09\u79cd\u60c5\u51b5\u8ba8\u8bba\u3002\u3002\u8bbe\u7b54\u6848\u662fAi..Aji<x2,ans=Max(S,x2..y2)-Min(S,x1-1..x2-1)j>y1,ans=Max(S,y1+1..y2)-Min(S,x1-1..y1-1..)i>=x2&&j<=y \u8f6c\u5316\u6210\u7ecf\u5178\u95ee\u9898\u4e86\u3002\u3002\u3002\u5982\u679c\u76f4\u63a5\u51993\u4e2a\u7ebf\u6bb5\u6811\u4f1a\u5f88BT\u3002\u3002\u53ea\u5199\u4e00\u4e2a\u7684\u8bdd\u53c8\u6d6a\u8d39\u65f6\u95f4\u3002\u3002\u6211\u7684Code\u4e2d\u5199\u4e86\u4e2a\u7ebf\u6bb5\u6811\u7684\u6a21\u677f\u3002\u3002\u7136\u540e\u6839\u636e\u4fe1\u606f\u76f4\u63a5\u5f04\u51fa3\u4e2a\u7ebf\u6bb5\u6811\u3002\u3002NB\u963f\uff08\u3002\u3002\u3002\uff09 #include<cstdio>#include<iostream>#define Renew(x,c) x=max(x,c)using namespace std;struct MinNum{ int Min; MinNum(int a=0):Min(a){} MinNum operator+(const MinNum&Rch) { MinNum f; f.Min=min(Min,Rch.Min); return f; }};struct MaxNum{ int Max; MaxNum(int a=0):Max(a){} MaxNum operator+(const MaxNum&Rch) { MaxNum f; f.Max=max(Max,Rch.Max); return f; }};struct ContMax{ int Max,Lmax,Rmax,Sum; ContMax(int a=0):Max(a),Lmax(a),Rmax(a),Sum(a){} ContMax operator+(const ContMax&Rch) { ContMax f; f.Lmax=max(Lmax,Sum+Rch.Lmax); f.Rmax=max(Rch.Rmax,Rch.Sum+Rmax); f.Sum=Sum+Rch.Sum; f.Max=max(Max,Rch.Max); f.Max=max(f.Max,Rmax+Rch.Lmax); return f; […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/46"}],"collection":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=46"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=\/wp\/v2\/posts\/46\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=46"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=46"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/wjmzbmr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=46"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}