SPOJ 2916 GSS5

https://www.spoj.pl/problems/GSS5/
这道题不难关键是我这个写法。。
实在是太NB了。。(这个烧饼疯了。。)
首先很明显如果y1<x2的话。。
设S为部分和序列。。那么ans=Max(S,x2..y2)-Min(S,x1-1..y1-1..)。。
如果有重叠的话。。分三种情况讨论。。设答案是Ai..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 转化成经典问题了。。。
如果直接写3个线段树会很BT。。只写一个的话又浪费时间。。
我的Code中写了个线段树的模板。。然后根据信息直接弄出3个线段树。。NB阿(。。。)

#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("%dn",ans);
}
}
int main()
{
int t;cin>>t;
while(t–) solve();
}

One thought on “SPOJ 2916 GSS5

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>