因为题目要求子序列中相邻元素下标的奇偶性不同所以线段树中需要维护4个值：jj,jo,oj,oo分别代表奇数开头和结尾、奇数开头偶数结尾、偶数开头奇数结尾和偶数开头和结尾的子序列的和的最大值，然后就是普通的单点修改和区间查询了。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 6 typedef long long ll; 7 const ll INF = 100000000000000000; 8 const int N = 100010; 9 ll a[N]; 10 11 struct Node 12 { 13 int l, r; 14 ll jj, jo, oj, oo; 15 } node[N << 2]; 16 17 ll max( ll x, ll y ) 18 { 19 return x > y ? x : y; 20 } 21 22 void pushup( int i ) 23 { 24 int lc = i << 1, rc = lc | 1; 25 node[i].jj = max( node[lc].jj, node[rc].jj ); 26 node[i].jj = max( node[i].jj, node[lc].jj + node[rc].oj ); 27 node[i].jj = max( node[i].jj, node[lc].jo + node[rc].jj ); 28 node[i].jo = max( node[lc].jo, node[rc].jo ); 29 node[i].jo = max( node[i].jo, node[lc].jo + node[rc].jo ); 30 node[i].jo = max( node[i].jo, node[lc].jj + node[rc].oo ); 31 node[i].oj = max( node[lc].oj, node[rc].oj ); 32 node[i].oj = max( node[i].oj, node[lc].oj + node[rc].oj ); 33 node[i].oj = max( node[i].oj, node[lc].oo + node[rc].jj ); 34 node[i].oo = max( node[lc].oo, node[rc].oo ); 35 node[i].oo = max( node[i].oo, node[lc].oj + node[rc].oo ); 36 node[i].oo = max( node[i].oo, node[lc].oo + node[rc].jo ); 37 } 38 39 void build( int i, int l, int r ) 40 { 41 node[i].l = l, node[i].r = r; 42 if ( l == r ) 43 { 44 if ( l & 1 ) 45 { 46 node[i].jj = a[l]; 47 node[i].jo = node[i].oj = node[i].oo = -INF; 48 } 49 else 50 { 51 node[i].oo = a[l]; 52 node[i].jj = node[i].jo = node[i].oj = -INF; 53 } 54 return ; 55 } 56 int mid = ( l + r ) >> 1; 57 build( i << 1, l, mid ); 58 build( i << 1 | 1, mid + 1, r ); 59 pushup(i); 60 } 61 62 void update( int i, int pos, int val ) 63 { 64 if ( node[i].l == pos && node[i].r == pos ) 65 { 66 if ( pos & 1 ) 67 { 68 node[i].jj = val; 69 } 70 else 71 { 72 node[i].oo = val; 73 } 74 return ; 75 } 76 int mid = ( node[i].l + node[i].r ) >> 1; 77 if ( pos <= mid ) 78 { 79 update( i << 1, pos, val ); 80 } 81 else 82 { 83 update( i << 1 | 1, pos, val ); 84 } 85 pushup(i); 86 } 87 88 Node query( int i, int l, int r ) 89 { 90 if ( node[i].l == l && node[i].r == r ) return node[i]; 91 int lc = i << 1, rc = lc | 1, mid = ( node[i].l + node[i].r ) >> 1; 92 if ( r <= mid ) 93 { 94 return query( lc, l, r ); 95 } 96 else if ( l > mid ) 97 { 98 return query( rc, l, r ); 99 } 100 else 101 { 102 Node ln = query( lc, l, mid ), rn = query( rc, mid + 1, r ), res; 103 res.jj = max( ln.jj, rn.jj ); 104 res.jj = max( res.jj, ln.jj + rn.oj ); 105 res.jj = max( res.jj, ln.jo + rn.jj ); 106 res.jo = max( ln.jo, rn.jo ); 107 res.jo = max( res.jo, ln.jj + rn.oo ); 108 res.jo = max( res.jo, ln.jo + rn.jo ); 109 res.oj = max( ln.oj, rn.oj ); 110 res.oj = max( res.oj, ln.oj + rn.oj ); 111 res.oj = max( res.oj, ln.oo + rn.jj ); 112 res.oo = max( ln.oo, rn.oo ); 113 res.oo = max( res.oo, ln.oo + rn.jo ); 114 res.oo = max( res.oo, ln.oj + rn.oo ); 115 return res; 116 } 117 } 118 119 int main() 120 { 121 int t; 122 scanf("%d", &t); 123 while ( t-- ) 124 { 125 int n, m; 126 scanf("%d%d", &n, &m); 127 for ( int i = 1; i <= n; i++ ) 128 { 129 scanf("%I64d", &a[i]); 130 } 131 build( 1, 1, n ); 132 while ( m-- ) 133 { 134 int op; 135 scanf("%d", &op); 136 if ( op == 0 ) 137 { 138 int l, r; 139 scanf("%d%d", &l, &r); 140 Node nn = query( 1, l, r ); 141 ll ans = nn.jj; 142 ans = max( ans, nn.jo ); 143 ans = max( ans, nn.oj ); 144 ans = max( ans, nn.oo ); 145 printf("%I64d ", ans); 146 } 147 else if ( op == 1 ) 148 { 149 int pos, val; 150 scanf("%d%d", &pos, &val); 151 update( 1, pos, val ); 152 } 153 } 154 } 155 return 0; 156 }