原题链接：更好的阅读体验
题目描述
小H给你一个数组{a}，要求支持以下两种操作：
0 l r(1<=l<=r<=n)，询问区间[l,r]中权值和最大的有效子区间的权值和，一个子区间被认为是有效的当且仅当这个子区间中没有两个相邻的偶数或者奇数。
1 x v(1<=x<=n,-109<=v<=109)，将a[x]的值修改为v。
输入描述:
第一行读入两个正整数n,m(1<=n,m<=105)
第二行读入n个整数，第i个表示a[i](-109 <= a[i] <= 109)
接下来m行，每行三个数表示操作，描述见题目描述。
输出描述:
输出每个询问的答案。
示例1
输入
复制
10 10
-9 -8 -8 -8 2 -7 -5 2 2 3
0 3 5
0 4 4
0 2 4
1 6 6
1 1 6
1 5 9
0 1 2
1 5 -8
0 2 4
1 3 -2
输出
复制
2
-8
-8
6
-8
思路：
一般用线段树的话，就是通过增加维护的东西来达到目的，这个题比维护最大连续子段和的题多了一个限制奇偶的条件，只需要在结构体中加入flag标记即可。
/**
用线段树维护一个区间的和，
区间是否有效，
区间的左端和右端的奇偶性，
区间左端和右端开始的最大的有效子区间的和，
区间里最大的有效子区间的和，
**/
ps:以后还是少用结构体全部赋值，少了个v找了半小时bug
代码：
#include<bits/stdc++.h> typedef long long ll; using namespace std; inline void read(ll &x){ ll s = 0, w = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar(); x = s*w; } const int maxn=1e6+7; struct node{ ll flag;///该区间是否有效 ll sum;///区间的和 ll suml,sumr,maxsum;///左端开始的最大有效子区间和，右端，总的 ll flagl,flagr;///左右区间的奇偶:1奇0偶 }a[maxn*4]; ll n,m; ll vis[maxn]; void pushup(ll u){ auto l=a[u<<1],r=a[u<<1|1],&x=a[u]; x.flag=0; x.maxsum=max(l.maxsum,r.maxsum);///维护区间有效最大值 x.flagl=l.flagl;x.flagr=r.flagr;///维护区间端点的奇偶性 x.suml=l.suml;x.sumr=r.sumr;///维护左端开始的最大有效子区间和 ///以上都是区间未合并时的情况 if(l.flagr^r.flagl){///区间可合并 x.maxsum=max(x.maxsum,l.sumr+r.suml); if(r.flag) x.sumr=max(x.sumr,l.sumr+r.sum); ///如果右边区间合法，总区间的从右端区间开始的合法区间是右边区间和左边区间的从右开始的合法部分 if(l.flag) x.suml=max(x.suml,r.suml+l.sum); if(l.flag&&r.flag){ x.flag=1; x.sum=l.sum+r.sum; } } } node qupdate(node l,node r){ node x; x.flag=0; x.maxsum=max(l.maxsum,r.maxsum);///维护区间有效最大值 x.flagl=l.flagl;x.flagr=r.flagr;///维护区间端点的奇偶性 x.suml=l.suml;x.sumr=r.sumr;///维护左端开始的最大有效子区间和 ///以上都是区间未合并时的情况 if(l.flagr^r.flagl){///区间可合并 x.maxsum=max(x.maxsum,l.sumr+r.suml); if(r.flag) x.sumr=max(x.sumr,l.sumr+r.sum); ///如果右边区间合法，总区间的从右端区间开始的合法区间是右边区间和左边区间的从右开始的合法部分 if(l.flag) x.suml=max(x.suml,r.suml+l.sum); if(l.flag&&r.flag){ x.flag=1; x.sum=l.sum+r.sum; } } return x; } void build(ll u,ll l,ll r){ if(l==r) a[u]={1,vis[l],vis[l],vis[l],vis[l],vis[l]&1,vis[l]&1}; else{ int mid=(l+r)>>1; build(u<<1,l,mid);build(u<<1|1,mid+1,r); pushup(u); } } /** struct node{ bool flag;///该区间是否有效 ll sum;///区间的和 ll suml,sumr,maxsum;///左端开始的最大有效子区间和，右端，总的 bool flagl,flagr;///左右区间的奇偶:1奇0偶 }a[maxn*4]; **/ void update(int u,int l,int r,int x,int v){ if(l==r) a[u]={1,v,v,v,v,v&1,v&1}; else{ int mid=(l+r)>>1; if(x<=mid) update(u<<1,l,mid,x,v); else update(u<<1|1,mid+1,r,x,v); pushup(u); } } node qask(int u,int l,int r,int x,int y){ if(x<=l&&y>=r) return a[u]; int mid=(l+r)>>1; if(y<=mid) return qask(u<<1,l,mid,x,y); else if(x>mid) return qask(u<<1|1,mid+1,r,x,y); else return qupdate(qask(u<<1,l,mid,x,y),qask(u<<1|1,mid+1,r,x,y)); } int main(){ cin>>n>>m; for(ll i=1;i<=n;i++) cin>>vis[i]; build(1,1,n); ll op,x,y; while(m--){ cin>>op>>x>>y; if(!op) printf("%lld\n",qask(1,1,n,x,y).maxsum); else update(1,1,n,x,y); } return 0; }
