题意：有一个区间，然后有两种操作
1. 把a处的值改为b
0，查询区间ab的子序列的最大和，这个比较特殊，子序列里面相邻的数要有不同的奇偶性
**********************************************************************
分析：因为是奇偶性不同才可以合并，于是只需要构造出来每个区间奇偶性序列就行，00，,11,01,10，也就四种情况，然后可以向上更新。
不过比赛中一直错，赛后才发现原来是查询的时候出错了，不能直接返回四种数里面的最大数，因为查询的时候有可能分成左右两端查询，所以还要进行合并操作才行。血的教训
************************************************************************
#include<algorithm>
#include<stdio.h>
#include<stack>
#include<string.h>
using namespace std; #define lson r<<1
#define rson r<<1|1 const int maxn = ;
const int INF = 1e9+; struct node
{///奇数位和偶数位
int L, R;
long long jj, jo, oj, oo;///奇奇，奇偶，偶奇，偶偶
int Mid(){return (L+R)>>;}
}a[maxn*];
long long val[maxn];
struct even_odd
{
long long jj, oo, jo, oj;
}; void pushUp(int r)
{
a[r].jj = max( a[lson].jj, max( a[rson].jj, max( a[lson].jj + a[rson].oj, a[lson].jo + a[rson].jj ) ) );
a[r].oo = max( a[lson].oo, max( a[rson].oo, max( a[lson].oo + a[rson].jo, a[lson].oj + a[rson].oo ) ) );
a[r].jo = max( a[lson].jo, max( a[rson].jo, max( a[lson].jj + a[rson].oo, a[lson].jo + a[rson].jo ) ) );
a[r].oj = max( a[lson].oj, max( a[rson].oj, max( a[lson].oo + a[rson].jj, a[lson].oj + a[rson].oj ) ) );
}
void Build(int r, int L, int R)
{
a[r].L = L, a[r].R = R;
a[r].jj = a[r].jo = a[r].oj = a[r].oo = -INF; if(L == R)
{
if(L % == )
a[r].oo = val[L];
else
a[r].jj = val[L]; return ;
} Build(lson, L, a[r].Mid());
Build(rson, a[r].Mid()+, R); pushUp(r);
}
void upDate(int r, int k, long long e)
{
if(a[r].L == a[r].R)
{
if(k % == )
{
a[r].oo = e;
a[r].jj = a[r].oj = a[r].jo = -INF;
}
else
{
a[r].jj = e;
a[r].oo = a[r].oj = a[r].jo = -INF;
} return ;
} if(k <= a[r].Mid())
upDate(lson, k, e);
else
upDate(rson, k, e); pushUp(r);
}
even_odd Query(int r, int L, int R)
{
if(a[r].L == L && a[r].R == R)
{
even_odd s;
s.jj = a[r].jj, s.oo = a[r].oo, s.jo = a[r].jo, s.oj = a[r].oj;
return s;
} if(R <= a[r].Mid())
return Query(lson, L, R);
else if(L > a[r].Mid())
return Query(rson, L, R);
else
{
even_odd ls = Query(lson, L, a[r].Mid());
even_odd rs = Query(rson, a[r].Mid()+, R);
even_odd s; s.jj = max( ls.jj, max( rs.jj, max( ls.jj + rs.oj, ls.jo + rs.jj ) ) );
s.oo = max( ls.oo, max( rs.oo, max( ls.oo + rs.jo, ls.oj + rs.oo ) ) );
s.jo = max( ls.jo, max( rs.jo, max( ls.jj + rs.oo, ls.jo + rs.jo ) ) );
s.oj = max( ls.oj, max( rs.oj, max( ls.oo + rs.jj, ls.oj + rs.oj ) ) ); return s;
}
} int main()
{
int i, T; scanf("%d", &T); while(T--)
{
int N, M, op, x, y;
even_odd s; scanf("%d%d", &N, &M); for(i=; i<=N; i++)
scanf("%lld", &val[i]); Build(, , N); while(M--)
{
scanf("%d%d%d", &op, &x, &y); if(op == )
{
s = Query(, x, y);
printf("%lld\n", max(s.jj, max(s.oo, max(s.oj, s.jo))));
}
else
upDate(, x, y);
}
} return ; }