题意：给一个array，有两种操作，(1)修改某一个位置的值，(2)询问区间[L,R]内的最大子段和，其中子段需满足相邻两个数的位置的奇偶性不同

思路：假设对于询问操作没有奇偶性的限制，那么记录区间的最大子段和就可以通过合并区间得到答案了。加上奇偶性的限制后，记录的信息必须更加具体，需要把子段的端点的奇偶性加进去，也就是说一个区间需要记录4个值， 分别是奇奇，奇偶，偶偶，偶奇，然后同样可以通过合并区间来得到答案。

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
/* ******************************************************************************** */
#include <iostream>                                                                 //
#include <cstdio>                                                                   //
#include <cmath>                                                                    //
#include <cstdlib>                                                                  //
#include <cstring>                                                                  //
#include <vector>                                                                   //
#include <ctime>                                                                    //
#include <deque>                                                                    //
#include <queue>                                                                    //
#include <algorithm>                                                                //
using namespace std;                                                                //
                                                                                    //
#define pb push_back                                                                //
#define mp make_pair                                                                //
#define X first                                                                     //
#define Y second                                                                    //
#define all(a) (a).begin(), (a).end()                                               //
#define foreach(i, a) for (typeof(a.begin()) it = a.begin(); it != a.end(); it ++)  //
                                                                                    //
void RI(vector<int>&a,int n){a.resize(n);for(int i=0;i<n;i++)scanf("%d",&a[i]);}    //
void RI(){}void RI(int&X){scanf("%d",&X);}template<typename...R>                    //
void RI(int&f,R&...r){RI(f);RI(r...);}void RI(int*p,int*q){int d=p<q?1:-1;          //
while(p!=q){scanf("%d",p);p+=d;}}void print(){cout<<endl;}template<typename T>      //
void print(const T t){cout<<t<<endl;}template<typename F,typename...R>              //
void print(const F f,const R...r){cout<<f<<", ";print(r...);}template<typename T>   //
void print(T*p, T*q){int d=p<q?1:-1;while(p!=q){cout<<*p<<", ";p+=d;}cout<<endl;}   //
                                                                                    //
typedef pair<int, int> pii;                                                         //
typedef long long ll;                                                               //
typedef unsigned long long ull;                                                     //
                                                                                    //
/* -------------------------------------------------------------------------------- */
                                                                                    //
template<typename T>bool umax(T &a, const T &b) {
    return a >= b? false : (a = b, true);
}
 
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
 
const ll inf = (ll)1e18;
const int maxn = 1e5 + 7;
 
struct SegTree {
private:
    struct Node {
        ll a[4];
    };
    Node tree[maxn << 2];
    int n;
    bool chk(int i, int j) {
        return (i & 1) ^ (j >> 1);
    }
    int get(int i, int j) {
        return (i & 2) | (j & 1);
    }
    Node merge(const Node &nl, const Node &nr) {
        Node ans;
        for (int i = 0; i < 4; i ++) {
            ans.a[i] = nl.a[i];
            umax(ans.a[i], nr.a[i]);
        }
        for (int i = 0; i < 4; i ++) {
            for (int j = 0; j < 4; j ++) {
                if (chk(i, j)) {
                    umax(ans.a[get(i, j)], nl.a[i] + nr.a[j]);
                }
            }
        }
        return ans;
    }
    void build(int l, int r, int rt) {
        if (l == r) {
            int x;
            RI(x);
            int buf = (l & 1) << 1 | (l & 1);
            for (int i = 0; i < 4; i ++) tree[rt].a[i] = i == buf? x : -inf;
            return ;
        }
        int m = (l + r) >> 1;
        build(lson);
        build(rson);
        tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1]);
    }
    void update(int p, int x, int l, int r, int rt) {
        if (l == r) {
            tree[rt].a[(p & 1) << 1 | (p & 1)] = x;
            return ;
        }
        int m = (l + r) >> 1;
        if (p <= m) update(p, x, lson);
        else update(p, x, rson);
        tree[rt] = merge(tree[rt << 1], tree[rt << 1 | 1]);
    }
    Node query(int L, int R, int l, int r, int rt) {
        if (L <= l && r <= R) return tree[rt];
        int m = (l + r) >> 1;
        if (R <= m) return query(L, R, lson);
        if (L > m) return query(L, R, rson);
        return merge(query(L, R, lson), query(L, R, rson));
    }
public:
    void build(int nn) { n = nn; build(1, n, 1); }
    void update(int p, int x) { update(p, x, 1, n, 1); }
    ll query(int l, int r) {
        Node buf = query(l, r, 1, n, 1);
        ll ans = buf.a[0];
        for (int i = 1; i < 4; i ++) umax(ans, buf.a[i]);
        return ans;
    }
};
SegTree st;
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGE
    int T;
    cin >> T;
    while (T --) {
        int n, m;
        RI(n, m);
        st.build(n);
        for (int i = 0; i < m; i ++) {
            int t, a, b;
            RI(t, a, b);
            if (t) st.update(a, b);
            else printf("%I64d\n", st.query(a, b));
        }
    }
    return 0;                                                                       //
}                                                                                   //
                                                                                    //
                                                                                    //
                                                                                    //
/* ******************************************************************************** */

最新文章

  1. Windows10安装MongoDB
  2. AutoMapper.EF6
  3. 类：String，Math，DateTime，Random随机数，异常保护
  4. rabbitmq之消息转储vm_memory_high_watermark_paging
  5. opengl的mipmap
  6. docker学习整理
  7. 黑马程序员——【Java基础】——Java概述
  8. 微软职位内部推荐-Senior Dev Lead
  9. prefixfree.js介绍
  10. 有关android源码编译的几个问题
  11. avd
  12. iOS 之 界面编程解析
  13. unity 屏幕适配的问题
  14. 【fork/join】java并发编程-fork/join示例
  15. P2467 [SDOI2010]地精部落 （dp+组合数）【扩展Lucas好难不会】
  16. openstack热添加磁盘
  17. 查看Selinux和关闭Selinux
  18. LOADRUNNER重装经验
  19. 004.SMB之guest级别配置
  20. 问题解决——MFC SDI程序 CFormView中控件随窗体缩放

热门文章

  1. php7.2.1+redis3.2.1 安装redis扩展（windows系统）
  2. CSS 中的伪类和伪元素
  3. 基于spring的安全管理框架-Spring Security
  4. BypassUAC
  5. 8个超好用的Python内置函数，提升效率必备（小白必看）
  6. php 对象的调用和引入
  7. centos7下端口映射
  8. 2019-2020-1 20199326《Linux内核原理与分析》第四周作业
  9. 2019-2020-1 20199328《Linux内核原理与分析》第五周作业
  10. 小白也能轻松上手的Prometheus教程