题意：n个数，由1~n编号，每个数的范围是[-1000000000, 1000000000]，两种操作：0 a b ：输出区间[a, b]中子序列的最大和，并且该子序列中的每两个相邻元素在原序列中的下标的奇偶性不同； 1 a b ：将下标为a的数改为b；
思路：这里的子序列并不需要连续；对于每段区间都有四种子序列：奇首奇尾(oo)， 奇首偶尾(oe)， 偶首奇尾(eo)， 偶首偶尾(ee)
那么查询呢？也说对于在两个相邻区间的查询来说，不能单纯的query(m<<1, l, mid)+query(m<<1|1, mid+1, r)，这样合并出来的区间可能并不符合题意；所以我们可以先返回一个区间t,然后像上边一样合并两个相邻区间；
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; const int N=1e5+10; const ll inf=1e18; int n,m; ll a[N]; struct tree{ int l,r; ll oo,oe,ee,eo; }t[N*4]; void pushup(tree &u,tree &l,tree &r) { u.oo=max(max(l.oo+r.eo,l.oe+r.oo),max(l.oo,r.oo)); u.oe=max(max(l.oo+r.ee,l.oe+r.oe),max(l.oe,r.oe)); u.eo=max(max(l.eo+r.eo,l.ee+r.oo),max(l.eo,r.eo)); u.ee=max(max(l.eo+r.ee,l.ee+r.oe),max(l.ee,r.ee)); } void pushup(int x) { pushup(t[x],t[x*2],t[x*2+1]); } void build(int x,int l,int r) { t[x].l=l;t[x].r=r; if(l==r) { if(l%2) { t[x].oo=a[l]; t[x].oe=t[x].eo=t[x].ee=-inf; } else { t[x].ee=a[l]; t[x].oe=t[x].eo=t[x].oo=-inf; } return; } int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); pushup(x); } void change(int x,int a,ll b) { if(t[x].l==t[x].r) { if(t[x].l%2) { t[x].oo=b; t[x].oe=t[x].eo=t[x].ee=-inf; } else { t[x].ee=b; t[x].oe=t[x].eo=t[x].oo=-inf; } return; } int mid=(t[x].l+t[x].r)/2; if(a<=mid) change(x*2,a,b); else change(x*2+1,a,b); pushup(x); } tree query(int x,int l,int r) { if(t[x].l>=l&&t[x].r<=r) { return t[x]; } int mid=(t[x].l+t[x].r)/2; if(r<=mid) { return query(x*2,l,r); } else if(l>mid) { return query(x*2+1,l,r); } else { tree ans; tree left=query(x*2,l,r); tree right=query(x*2+1,l,r); pushup(ans,left,right); return ans; } } int main() { int tt; scanf("%d",&tt); while(tt--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%lld",&a[i]); } build(1,1,n); for(int i=1;i<=m;i++) { int op; scanf("%d",&op); if(op==0) { int l,r; scanf("%d%d",&l,&r); tree T=query(1,l,r); printf("%lld\n",max(max(T.oo,T.oe),max(T.eo,T.ee))); } else { int x;ll y; scanf("%d%lld",&x,&y); change(1,x,y); } } } }