链接：https://www.nowcoder.com/acm/contest/72/D
线段树需要维护的：最大有效子区间权值和，左端最大有效子区间权值和，右端最大有效子区间权值和，区间和，本区间有效性。
#include<stdio.h> #include<algorithm> #include<string.h> #include<map> #include<queue> #include<set> #include<vector> #define MAXN 1000005 using namespace std; typedef long long ll; int a[100005]; struct Node{ int l,r; ll lsum,rsum,sum,v; bool jiou; Node operator + (const Node &t)const { Node res; res.jiou=0; res.l=l,res.r=t.r; res.v=v+t.v; res.sum=max(sum,t.sum); res.lsum=lsum; res.rsum=t.rsum; if((a[r]&1)!=(a[t.l]&1)) { if(jiou&&t.jiou) res.jiou=1; res.sum=max(res.sum,rsum+t.lsum); if(jiou==1) res.lsum=max(v+t.lsum,lsum); if(t.jiou==1) res.rsum=max(rsum+t.v,t.rsum); } return res; } }node[300015]; void construct(int l,int r,int k) { if(l==r) { node[k].l=l,node[k].r=r; node[k].lsum=(ll)a[l]; node[k].rsum=(ll)a[l]; node[k].sum=(ll)a[l]; node[k].v=(ll)a[l]; node[k].jiou=1; return; } int mid=(l+r)/2; construct(l,mid,2*k); construct(mid+1,r,2*k+1); node[k]=node[2*k]+node[2*k+1]; } struct Node query(int k,int x,int y) { int l=node[k].l,r=node[k].r; if(x<=l&&r<=y) { return node[k]; } int mid=(l+r)/2; struct Node a; if(x>mid) a=query(2*k+1,x,y); else if(y<=mid) a=query(2*k,x,y); else a=query(2*k,x,mid)+query(2*k+1,mid+1,y); return a; } struct Node modifiy(int k,int x,ll num) { int l=node[k].l,r=node[k].r; if(l==r&&l==x) { node[k].lsum=num; node[k].rsum=num; node[k].sum=num; node[k].v=(ll)num; return node[k]; } int mid=(l+r)/2; if(x>mid) node[k]=node[2*k]+modifiy(2*k+1,x,num); else if(x<=mid) node[k]=modifiy(2*k,x,num)+node[2*k+1]; return node[k]; } int main() { int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); construct(1,n,1); while(m--) { int q,x,y; scanf("%d%d%d",&q,&x,&y); if(q==0) { struct Node temp; temp=query(1,x,y); printf("%lld ",temp.sum); } else if(q==1) { a[x]=y; modifiy(1,x,(ll)y); } } return 0; }