HDU 5316 Magician(2015多校联合)

发表于   |  

题目链接：

戳我

题目大意：

一段序列 $n$个数$(n<=10^5)$，这 $n$个数的范围是$-10^9 <= a_i <= 10^9$，有两种操作， 0 L R代表 L R 这个区间 beautiful subsequence 的最大和。 1 a b代表修改 a位置的数为b
beautiful subsequence 的意思是下标奇偶相互交错的序列
例如 ${4, 7, 9, 2}$ 这个序列，beautiful subsequence有
${4}$ ${7}$ ${9}$ ${2}$
${4, 7}$ ${7, 9}$ ${9, 2}$ ${4, 2}$
${4, 7, 9}$ ${7, 9, 2}$
${4, 7, 9, 2}$

样例解释:

略

解题思路：

j代表奇数，o代表偶数
奇偶交错的序列有 4 种情况。开始和结尾 分别为 $jj, jo, oo, oj$
故线段树内维护这四种情况的最大值即可。
更新即为普通的更新。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
//Author LJH
//www.cnblogs.com/tenlee
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#define clc(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
const ll inf = -10000000000;
const int INF = 0x3f3f3f3f;
const int maxn = 1e5+5;

struct Sum
{
    ll jo, jj, oo, oj;
};
struct Tree
{
    int l, r;
    Sum s;
}tree[maxn << 2];
int n, m;
ll a[maxn];

inline Sum getSum(Sum l, Sum r)
{
    Sum ss;
    ss.jj = max(l.jj, r.jj); 
    ss.jj = max(ss.jj, l.jj+r.oj);
    ss.jj = max(ss.jj, l.jo+r.jj);

    ss.jo = max(l.jo, r.jo);
    ss.jo = max(ss.jo, l.jj+r.oo);
    ss.jo = max(ss.jo, l.jo+r.jo);

    ss.oo = max(l.oo, r.oo); 
    ss.oo = max(ss.oo, l.oj+r.oo);
    ss.oo = max(ss.oo, l.oo+r.jo);

    ss.oj = max(l.oj, r.oj);
    ss.oj = max(ss.oj, l.oj+r.oj);
    ss.oj = max(ss.oj, l.oo+r.jj);
    return ss;
}
void Build(int i, int l, int r)
{
    tree[i].l = l;
    tree[i].r = r;
    if(l == r)
    {
        if(l%2) // j
        {
            tree[i].s.jj = a[l]; tree[i].s.jo = inf; //因为存在负数，故要初始化为负无穷
            tree[i].s.oo = inf; tree[i].s.oj = inf;
        }
        else
        {
            tree[i].s.jj = inf; tree[i].s.jo = inf;
            tree[i].s.oo = a[l]; tree[i].s.oj = inf;
        }
       return;
    }
    int mid = (l + r) >> 1;
    Build(i<<1, l, mid);
    Build(i<<1|1, mid+1, r);
    tree[i].s = getSum(tree[i<<1].s, tree[i<<1|1].s);
}
void Update(int i, int id, ll val)
{
    if(tree[i].l == id && tree[i].r == id)
    {
        if(id%2) // 奇
        {
            tree[i].s.jj = val; tree[i].s.jo = inf;
            tree[i].s.oo = inf; tree[i].s.oj = inf;
        }
        else // 偶
        {
            tree[i].s.jj = inf; tree[i].s.jo = inf;
            tree[i].s.oo = val; tree[i].s.oj = inf;
        }
       return;
    }
    int mid = (tree[i].l + tree[i].r) >> 1;
    if(id > mid) Update(i<<1|1, id, val);
    else Update(i<<1, id, val);
    tree[i].s = getSum(tree[i<<1].s, tree[i<<1|1].s);
}
Sum Quary(int i, int l, int r)
{
    if(tree[i].l == l && tree[i].r == r)
    {
        return tree[i].s;   
    }
    int mid = (tree[i].l + tree[i].r) >> 1;
    if(r <= mid) return Quary(i<<1, l, r);
    else if(l > mid) return Quary(i<<1|1, l, r);
    else return(getSum(Quary(i<<1, l, mid), Quary(i<<1|1, mid+1, r))); 
}
int main()
{
    int T, x, y, op;
    Sum s;
    ll sum = 0, v;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d %d", &n, &m);
        for(int i = 1; i <= n; i++)
        {
            scanf("%lld", &a[i]);
        }
        Build(1, 1, n);
        while(m--)
        {
            scanf("%d", &op);
            if(x > y) swap(x, y);
            if(op == 0)
            {
                scanf("%d %d",&x, &y);
                if(n == 0)
                {
                    puts("0");continue;
                }
                s = Quary(1, x, y);
                sum = max(s.jj, s.jo);
                sum = max(sum, s.oo);
                sum = max(sum, s.oj);
                printf("%lld\n", sum);
            }
            else 
            {
                scanf("%d %lld", &x, &v);
                Update(1, x, v);
            }
        }
    }
    return 0;
}