HDU 5316 Magician(线段树区间合并， 子序列最值 多校2015啊)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define lson l , mid , rt << 1
#define rson mid + 1 , r , rt << 1 | 1
//lson和rson分辨表示结点的左儿子和右儿子
//rt表示当前子树的根(root),也就是当前所在的结点
const int maxn = 100000+7;
struct node
{
    int has[2][2];//是否有这种情况
    LL val[2][2];//该情况的最大值
} tre[maxn<<2];

int max(int x,int y)
{
    if(x > y)
        return x;
    return y;
}

//合并
node UNION(node a,node b)
{
    node c;
    //四种起始和终止情况可以直接继承于左儿子或右儿子的对应情况
    for(int i = 0; i <= 1; i++)
    {
        for(int j = 0; j <= 1; j++)
        {
            c.has[i][j] = a.has[i][j] + b.has[i][j];
            if(a.has[i][j] && b.has[i][j])
                c.val[i][j] = max(a.val[i][j], b.val[i][j]);
            else if(a.has[i][j])
                c.val[i][j] = a.val[i][j];
            else if(b.has[i][j])
                c.val[i][j] = b.val[i][j];
        }
    }

    //四种情况由左儿子和右儿子的情况合并。
    //如奇始奇终可以由左儿子的奇始奇终和右儿子的偶始奇终合并
    //也可以由左儿子的奇始偶终和右儿子的奇始奇终合并，，以此类推
    for(int i = 0; i <= 1; i++)
    {
        for(int j = 0; j <= 1; j++)
        {
            for(int k = 0; k <= 1; k++)
            {
                if(a.has[i][j] && b.has[!j][k])
                {
                    if(c.has[i][k])
                    {
                        c.val[i][k] = max(c.val[i][k], a.val[i][j]+b.val[!j][k]);
                    }
                    else
                    {
                        c.has[i][k] = 1;
                        c.val[i][k]=a.val[i][j]+b.val[!j][k];
                    }
                }
            }
        }
    }
    return c;
}

void PushUP(int rt)
{
    tre[rt] = UNION(tre[rt<<1],tre[rt<<1|1]);
}

void build(int l,int r,int rt)
{
    memset(tre[rt].has,0,sizeof(tre[rt].has));
    if (l == r)
    {
        int tt;
        scanf("%d",&tt);
        tre[rt].has[l%2][l%2] = 1;
        tre[rt].val[l%2][l%2] = tt;
        return ;
    }
    int mid = (l + r) >> 1;
    build(lson);
    build(rson);
    PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt)
{
    if (l == r) //叶节点
    {
        memset(tre[rt].has,0,sizeof(tre[rt].has));
        tre[rt].has[l%2][l%2] = 1;
        tre[rt].val[l%2][l%2] = sc;
        return ;
    }
    int mid = (l + r) >> 1;
    if (p <= mid)//递归更新左子树或者右子树
        update(p , sc , lson);
    else
        update(p , sc , rson);
    PushUP(rt);
}
node query(int L,int R,int l,int r,int rt)
{
    if (L <= l && r <= R)
    {
        return tre[rt];
    }
    int flag1 = 0, flag2 = 0;
    node ans1, ans2;
    int mid = (l + r) >> 1;
    if (L <= mid) //往左走
    {
        ans1 = query(L , R , lson);
        flag1 = 1;
    }
    if (mid < R)//往右走
    {
        ans2 = query(L , R , rson);
        flag2 = 1;
    }
    if(!flag1)
    {
        return ans2;
    }
    if(!flag2)
    {
        return ans1;
    }
    return UNION(ans1,ans2);
}
int main()
{
    int t;
    int N , M;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&N,&M);
        build(1 , N , 1); //建树
        while(M--)
        {
            int op, a , b;
            scanf("%d%d%d",&op,&a,&b);
            if(op == 1)
            {
                update(a , b , 1 , N , 1);
            }
            else if (op == 0)
            {
                node t = query(a , b , 1 , N , 1);
                LL ans;
                int flag = 0;
                for(int i = 0; i <= 1; i++)
                {
                    for(int j = 0; j <= 1; j++)
                    {
                        if(t.has[i][j])
                        {
                            if(flag == 0)
                            {
                                ans = t.val[i][j];
                                flag=1;
                            }
                            else
                                ans = max(ans, t.val[i][j]);
                        }
                    }
                }
                printf("%lld\n",ans);
            }
        }
    }
    return 0;
}

版权声明：本文为博主原创文章，未经博主允许不得转载。