Magician - hdu 5316 (区间查询合并)

题意：有一个区间，然后有两种操作

1. 把a处的值改为b

0，查询区间ab的子序列的最大和，这个比较特殊，子序列里面相邻的数要有不同的奇偶性

**********************************************************************

分析：因为是奇偶性不同才可以合并，于是只需要构造出来每个区间奇偶性序列就行，00，,11,01,10，也就四种情况，然后可以向上更新。

不过比赛中一直错，赛后才发现原来是查询的时候出错了，不能直接返回四种数里面的最大数，因为查询的时候有可能分成左右两端查询，所以还要进行合并操作才行。血的教训

************************************************************************

#include<algorithm>

#include<stdio.h>

#include<stack>

#include<string.h>

using namespace std;

#define lson r<<1

#define rson r<<1|1

const int maxn = ;

const int INF = 1e9+;

struct node

{///奇数位和偶数位

    int L, R;

    long long jj, jo, oj, oo;///奇奇，奇偶，偶奇，偶偶

    int Mid(){return (L+R)>>;}

}a[maxn*];

long long val[maxn];

struct even_odd

{

    long long jj, oo, jo, oj;

};

void pushUp(int r)

{

    a[r].jj = max( a[lson].jj, max( a[rson].jj, max( a[lson].jj + a[rson].oj, a[lson].jo + a[rson].jj ) ) );

    a[r].oo = max( a[lson].oo, max( a[rson].oo, max( a[lson].oo + a[rson].jo, a[lson].oj + a[rson].oo ) ) );

    a[r].jo = max( a[lson].jo, max( a[rson].jo, max( a[lson].jj + a[rson].oo, a[lson].jo + a[rson].jo ) ) );

    a[r].oj = max( a[lson].oj, max( a[rson].oj, max( a[lson].oo + a[rson].jj, a[lson].oj + a[rson].oj ) ) );

}

void Build(int r, int L, int R)

{

    a[r].L = L, a[r].R = R;

    a[r].jj = a[r].jo = a[r].oj = a[r].oo = -INF;

    if(L == R)

    {

        if(L %  == )

            a[r].oo =  val[L];

        else

            a[r].jj = val[L];

        return ;

    }

    Build(lson, L, a[r].Mid());

    Build(rson, a[r].Mid()+, R);

    pushUp(r);

}

void upDate(int r, int k, long long e)

{

    if(a[r].L == a[r].R)

    {

        if(k %  == )

        {

            a[r].oo = e;

            a[r].jj = a[r].oj = a[r].jo = -INF;

        }

        else

        {

            a[r].jj = e;

            a[r].oo = a[r].oj = a[r].jo = -INF;

        }

        return ;

    }

    if(k <= a[r].Mid())

        upDate(lson, k, e);

    else

        upDate(rson, k, e);

    pushUp(r);

}

even_odd Query(int r, int L, int R)

{

    if(a[r].L == L && a[r].R == R)

    {

        even_odd s;

        s.jj = a[r].jj, s.oo = a[r].oo, s.jo = a[r].jo, s.oj = a[r].oj;

        return s;

    }

    if(R <= a[r].Mid())

        return Query(lson, L, R);

    else if(L > a[r].Mid())

        return Query(rson, L, R);

    else

    {

        even_odd ls = Query(lson, L, a[r].Mid());

        even_odd rs = Query(rson, a[r].Mid()+, R);

        even_odd s;

        s.jj = max( ls.jj, max( rs.jj, max( ls.jj + rs.oj, ls.jo + rs.jj ) ) );

        s.oo = max( ls.oo, max( rs.oo, max( ls.oo + rs.jo, ls.oj + rs.oo ) ) );

        s.jo = max( ls.jo, max( rs.jo, max( ls.jj + rs.oo, ls.jo + rs.jo ) ) );

        s.oj = max( ls.oj, max( rs.oj, max( ls.oo + rs.jj, ls.oj + rs.oj ) ) );

        return s;

    }

}

int main()

{

    int i, T;

    scanf("%d", &T);

    while(T--)

    {

        int N, M, op, x, y;

        even_odd s;

        scanf("%d%d", &N, &M);

        for(i=; i<=N; i++)

            scanf("%lld", &val[i]);

        Build(, , N);

        while(M--)

        {

            scanf("%d%d%d", &op, &x, &y);

            if(op == )

            {

                s = Query(, x, y);

                printf("%lld\n", max(s.jj, max(s.oo, max(s.oj, s.jo))));

            }

            else

                upDate(, x, y);

        }

    }

    return ; }

巴特西

Magician - hdu 5316 (区间查询合并)

最新文章

热门文章