SPOJ 2916 GSS5 - Can you answer these queries V

解题思路

和GSS1相似，但需要巨恶心的分类讨论，对于x1<=y1< x2< =y2 这种情况，最大值应该取[x1,y1]的右端最大+[y1+1,x2-1]的和+[x2,y2]的左端最大。对于x1< =x2< =y1<=y2，用四种情况，第一种是[x1,x2-1]的右端最大+[x2,y2]的左端最大，第二种是[x1,y1]的右端最大+[y1+1,y2]的左端最大，第三种是[x2,y1]的最大值，第四种是[x1,x2-1]的右端最大+[x2,y1]的和+[y1+1,y2]的左端最大。这四种情况取max即为答案。可以画图帮助理解。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN = 10005;

inline int rd(){

    int x=0,f=1;char ch=getchar();

    while(!isdigit(ch))  {if(ch=='-')f=-1;ch=getchar();}

    while(isdigit(ch))   {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

    return x*f;

}

int n,a[MAXN],T,m;

struct Node{

    int lx,rx,sum,mx;

    Node(){

        lx=rx=sum=mx=0;

    }

}node[MAXN<<2];

inline void pushup(int x){

    node[x].sum=node[x<<1].sum+node[x<<1|1].sum;

    node[x].lx=max(node[x<<1].lx,node[x<<1].sum+node[x<<1|1].lx);

    node[x].rx=max(node[x<<1|1].rx,node[x<<1].rx+node[x<<1|1].sum);

    node[x].mx=max(max(node[x<<1].mx,node[x<<1|1].mx),node[x<<1].rx+node[x<<1|1].lx);

}

inline void build(int x,int l,int r){

    if(l==r){

        node[x].sum=node[x].lx=node[x].mx=node[x].rx=a[l];

        return;

    }

    int mid=l+r>>1;

    build(x<<1,l,mid);

    build(x<<1|1,mid+1,r);

    pushup(x);

}

inline Node query(int x,int l,int r,int L,int R){

    if(L<=l && r<=R) return node[x];

    int mid=l+r>>1;

    if(mid<L) return query(x<<1|1,mid+1,r,L,R);

    else if(mid>=R) return query(x<<1,l,mid,L,R);

    else {

        Node A=query(x<<1,l,mid,L,R);

        Node B=query(x<<1|1,mid+1,r,L,R);

        Node ans;

        ans.sum=A.sum+B.sum;

        ans.lx=max(A.lx,A.sum+B.lx);

        ans.rx=max(B.rx,B.sum+A.rx);

        ans.mx=max(max(A.mx,B.mx),A.rx+B.lx);

        return ans;

    }

}

inline Node solve(int x1,int y1,int x2,int y2){

    Node A=query(1,1,n,x1,y1);

    Node B=query(1,1,n,x2,y2);

    Node ans;

    if(y1<x2) {

        if(x2-1>=y1+1){

            Node C=query(1,1,n,y1+1,x2-1);

            ans.mx=A.rx+C.sum+B.lx;

        }

        else ans.mx=A.rx+B.lx;

    }

    else{

        Node C,D,E;

        if(x1<=x2-1) C=query(1,1,n,x1,x2-1);

        if(y1+1<=y2) D=query(1,1,n,y1+1,y2);

        E=query(1,1,n,x2,y1);

        ans.mx=max(max(E.mx,C.rx+E.sum+D.lx),max(C.rx+B.lx,A.rx+D.lx));

    }

    return ans;

}

int main(){

    T=rd();

    while(T--){

        n=rd();

        for(register int i=1;i<=n;i++) a[i]=rd();

        build(1,1,n);

        m=rd();

        while(m--){

            int x1=rd(),y1=rd(),x2=rd(),y2=rd();

            printf("%d\n",solve(x1,y1,x2,y2).mx);

        }

    }

    return 0;

}

巴特西

SPOJ 2916 GSS5 - Can you answer these queries V

解题思路

代码

最新文章

热门文章