一開始度错题了，题意是求一段和最大的【子序列】，要求相邻两个元素的位置必须互为奇偶。

这样我们能够使用线段树维护4个值：

一段区间内开头结尾元素为：

奇奇

奇偶

偶奇

偶偶

的最大值

之后在pushup的的时候依据题目所给的意思进行合并。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define lson (pos<<1)

#define rson (pos<<1|1)

typedef long long LL;

const int maxn = 100005;

const LL  INF =  9999999999999999LL;

int n,m;

struct Node{

    LL oe;

    LL oo;

    LL ee;

    LL eo;

}node[maxn << 2];

LL value[maxn];

Node pushnode(Node p,Node q){

    Node newNode;

    newNode.oe = max(max(p.oe,q.oe),max(p.oo + q.ee,p.oe + q.oe));

    newNode.oo = max(max(p.oo,q.oo),max(p.oo + q.eo,p.oe + q.oo));

    newNode.ee = max(max(p.ee,q.ee),max(p.eo + q.ee,p.ee + q.oe));

    newNode.eo = max(max(p.eo,q.eo),max(p.eo + q.eo,p.ee + q.oo));

    return newNode;

}

void pushup(int pos){

    node[pos].oe = max(max(node[lson].oe,node[rson].oe),max(node[lson].oo + node[rson].ee,node[lson].oe + node[rson].oe));

    node[pos].oo = max(max(node[lson].oo,node[rson].oo),max(node[lson].oo + node[rson].eo,node[lson].oe + node[rson].oo));

    node[pos].ee = max(max(node[lson].ee,node[rson].ee),max(node[lson].eo + node[rson].ee,node[lson].ee + node[rson].oe));

    node[pos].eo = max(max(node[lson].eo,node[rson].eo),max(node[lson].eo + node[rson].eo,node[lson].ee + node[rson].oo));

}

void build(int l,int r,int pos){

    if(l == r){

        if(l & 1){

            node[pos].oe = node[pos].ee = node[pos].eo = -INF;

            node[pos].oo = value[l];

        }

        else{

            node[pos].oe = node[pos].oo = node[pos].eo = -INF;

            node[pos].ee = value[l];

        }

        return;

    }

    int mid = (l + r) >> 1;

    build(l,mid,lson);

    build(mid + 1,r,rson);

    pushup(pos);

}

void update(int l,int r,int pos,int to,int v){

    if(l == r){

        if(l & 1){

            node[pos].oe = node[pos].ee = node[pos].eo = -INF;

            node[pos].oo = v;

        }

        else{

            node[pos].oe = node[pos].oo = node[pos].eo = -INF;

            node[pos].ee = v;

        }

        return;

    }

    int mid = (l + r) >> 1;

    if(to <= mid)

        update(l,mid,lson,to,v);

    else

        update(mid + 1,r,rson,to,v);

    pushup(pos);

}

Node query(int l,int r,int L,int R,int pos){

    if(L <= l && r <= R){

        return node[pos];

    }

    int mid = (l + r) >> 1;

    if(R <= mid)

        return query(l,mid,L,R,lson);

    else if(L > mid)

        return query(mid + 1,r,L,R,rson);

    else{

        Node v1 = query(l,mid,L,R,lson);

        Node v2 = query(mid + 1,r,L,R,rson);

        return pushnode(v1,v2);

    }

}

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(int i = 1; i <= n; i++){

            scanf("%I64d",&value[i]);

        }

        build(1,n,1);

        for(int i = 0; i < m; i++){

            int op;

            LL  a,b;

            scanf("%d%I64d%I64d",&op,&a,&b);

            if(op == 0){

                Node nans = query(1,n,a,b,1);

                LL ans = max(max(nans.oo,nans.eo),max(nans.ee,nans.oe));

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

            }

            else if(op == 1)

                update(1,n,1,a,b);

        }

    }

    return 0;

}