SPOJ 1043 1043. Can you answer these queries I

思路：用TREE记录节点的最大连续和，LEF记录左边开始的最大连续和，RIG记右边开始的最大连续和

然后处理的时候就是比较左边最大，右边最大中间区间的问题

其中这个query 只能膜拜了。。。

大大缩减了时间。放弃治疗的我只会用三个函数

传参就要传出翔。

flag == -1表示要左边最大

flag == 1 表示要右边最大

然后ans在找到的区间的同时进行比较。

我已可入灵魂

#include <iostream>

#include <cstdio>

#include <algorithm>

#define MAXN 50005

#define lson num<<1,s,mid

#define rson num<<1|1,mid+1,e

using namespace std;

int tree[MAXN<<2];

int lef[MAXN<<2];

int rig[MAXN<<2];

int X[MAXN]={0};

int n;

int cnt;

inline void pushup(int num,int s,int e)

{

    int mid=(s+e)>>1;

    lef[num]=max(lef[num<<1],X[mid]-X[s-1]+lef[num<<1|1]);

    rig[num]=max(rig[num<<1|1],X[e]-X[mid]+rig[num<<1]);

    tree[num]=max(lef[num<<1|1]+rig[num<<1],max(tree[num<<1],tree[num<<1|1]));

}

void build(int num,int s,int e)

{

    if(s==e)

    {

        scanf("%d",&tree[num]);

        lef[num]=rig[num]=tree[num];

        X[cnt]=X[cnt-1]+tree[num];

        cnt++;

        return;

    }

    int mid=(s+e)>>1;

    build(num<<1,s,mid);

    build(num<<1|1,mid+1,e);

    pushup(num,s,e);

}

int query(int num, int s, int e, int l, int r, int flag, int &ans)

{

    int mid = (s+e)>>1;

    if(s >= l && e <= r)

    {

        ans = max(ans, tree[num]);

        return flag == -1 ? lef[num] : rig[num];

    }

    if(mid >= r)

        return query(num<<1, s, mid, l, r, -1, ans);

    else if(mid  < l)

        return query(num<<1|1, mid + 1, e, l, r, 1, ans);

    else

    {

        int ln, rn;

        ln = query(num<<1, s, mid, l, r, 1, ans);

        rn = query(num<<1|1, mid + 1, e, l, r, -1, ans);

        ans = max(ans, ln + rn);

        if(flag == -1)

            return max(lef[num<<1], X[mid] - X[s - 1] + rn);

        else

            return max(rig[num<<1|1], X[e] - X[mid] + ln);

    }

}

int main()

{

    while(scanf("%d",&n)!=EOF)

    {

        cnt=1;

        X[0]=0;

        build(1,1,n);

        int m;

        scanf("%d",&m);

        while(m--)

        {

            int aa,bb;

            scanf("%d%d",&aa,&bb);

            int ans=X[aa]-X[aa-1];

            query(1,1,n,aa,bb,-1,ans);

            printf("%d\n",ans);

        }

    }

    return 0;

}

/*

8

-1 5 -6 7 -4 8 -2 7

999

*/

巴特西

SPOJ 1043 1043. Can you answer these queries I

最新文章

热门文章