小新经常陪小白去公园玩，也就是所谓的遛狗啦…
在小新家附近有一条“公园路”，路的一边从南到北依次排着nn个公园，小白早就看花了眼，自己也不清楚该去哪些公园玩了。
一开始，小白就根据公园的风景给每个公园打了分-.-。小新为了省事，每次遛狗的时候都会事先规定一个范围，小白只可以选择第aa个和第bb个公园之间（包括aa、bb两个公园）选择连续的一些公园玩。小白当然希望选出的公园的分数总和尽量高咯。同时，由于一些公园的景观会有所改变，所以，小白的打分也可能会有一些变化。
那么，就请你来帮小白选择公园吧。
第一行，两个整数NN和MM，分别表示表示公园的数量和操作（遛狗或者改变打分）总数。
接下来NN行，每行一个整数，依次给出小白 开始时对公园的打分。
接下来MM行，每行三个整数。第一个整数KK，11或22。
小白每出去玩一次，都对应输出一行，只包含一个整数，表示小白可以选出的公园得分和的最大值。
5 3 1 2 -3 4 5 1 2 3 2 2 -1 1 2 3
2 -1
求区间最长连续和
有时候区间合并用结构体线段树要方便很多
#include<cstdio> #include<algorithm> using namespace std; struct Node { int l,r,lc,rc,lm,rm,ans,tot; }node[4000005]; int n,m,k,x,y,cnt=0,a[500001]; void maintain(int x)//维护更新，合并答案 { int ll=node[x].lc,rr=node[x].rc; node[x].tot=node[ll].tot+node[rr].tot; node[x].lm=max(node[ll].lm,node[ll].tot+node[rr].lm); node[x].rm=max(node[rr].rm,node[rr].tot+node[ll].rm); node[x].ans=max(max(node[ll].ans,node[rr].ans),node[ll].rm+node[rr].lm); } void build(int l,int r,int now) { node[now].l=l; node[now].r=r; if(l==r) { node[now].lm=node[now].rm=node[now].tot=node[now].ans=a[l];//赋初值 return;//不要忘记return } int mid=(l+r)>>1; node[now].lc=2*now; build(l,mid,node[now].lc); node[now].rc=2*now+1; build(mid+1,r,node[now].rc); maintain(now);//合并答案 } void update(int now,int to,int num) { int x=node[now].l,y=node[now].r; if(x==y) { node[now].lm=node[now].rm=node[now].tot=node[now].ans=num;//修改 return; } int mid=(x+y)>>1; if(to<=mid) update(node[now].lc,to,num); else update(node[now].rc,to,num); maintain(now);//合并答案 } Node query(int now,int l,int r) { int x=node[now].l,y=node[now].r; if(l<=x&&r>=y) return node[now];//当前节点在询问区间当中，直接返回答案。 int mid=(x+y)>>1,ll=node[now].lc,rr=node[now].rc; if(r<=mid) return query(ll,l,r); else if(l>mid) return query(rr,l,r); else//询问区间跨过mid时要合并一下答案，思路与maintain函数中的差不多，在此不再赘述。 { Node t,t1=query(ll,l,r),t2=query(rr,l,r); t.tot=t1.tot+t2.tot; t.lm=max(t1.lm,t1.tot+t2.lm); t.rm=max(t2.rm,t2.tot+t1.rm); t.ans=max(max(t1.ans,t2.ans),t1.rm+t2.lm); return t; } } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); for(int i=1;i<=m;i++) { scanf("%d%d%d",&k,&x,&y); if(k==1) { if(x>y) swap(x,y); printf("%d\n",query(1,x,y).ans); } else update(1,x,y); } return 0; }
原文：https://www.cnblogs.com/bxd123/p/11258700.html
