传送门
Solution:
与上一题十分类似的，我们考虑维护一个节点的区间从左到右包含最左端点的最大值，以及从右到左的最大值，以及整体的最大值，以及当前区间的权值和。
不过方便一点，我们不用再去维护区间左右端点的值，因为有了区间的权值和，父节点的lmax=max(lson.lmax,lson.v+rson.lmax)即可，不必再麻烦的去特判左右端点。
#include<bits/stdc++.h> #define N 500005 #define lson 2*now #define rson 2*now+1 using namespace std; int n,m,val[N]; struct node { int l,r,lmax,rmax,allmax,v; }tree[4*N]; inline void build(int l,int r,int now) { tree[now].l=l,tree[now].r=r; if(l==r) { tree[now].lmax=tree[now].rmax=tree[now].allmax=tree[now].v=val[l]; return; } int m=(l+r)>>1; build(l,m,lson); build(m+1,r,rson); tree[now].lmax=max(tree[lson].lmax,tree[lson].v+tree[rson].lmax); tree[now].rmax=max(tree[rson].rmax,tree[rson].v+tree[lson].rmax); tree[now].allmax=max(max(tree[lson].allmax,tree[rson].allmax),(tree[rson].lmax+tree[lson].rmax)); tree[now].v=tree[lson].v+tree[rson].v; } int ans=INT_MIN; inline node query(int l,int r,int now) { if(l<=tree[now].l&&tree[now].r<=r) { return tree[now]; } int m=(tree[now].l+tree[now].r)>>1; if(r<=m) return query(l,r,lson); else if(m<l) return query(l,r,rson); else { node t,t1,t2; t1=query(l,r,lson); t2=query(l,r,rson); t.lmax=max(t1.lmax,t1.v+t2.lmax); t.rmax=max(t2.rmax,t2.v+t1.rmax); t.allmax=max(max(t1.allmax,t2.allmax),(t2.lmax+t1.rmax)); return t; } } inline void update(int num,int k,int now) { if(tree[now].l==tree[now].r) { tree[now].lmax=tree[now].rmax=tree[now].allmax=tree[now].v=k; return; } int m=(tree[now].l+tree[now].r)>>1; if(num<=m) update(num,k,lson); else update(num,k,rson); tree[now].lmax=max(tree[lson].lmax,tree[lson].v+tree[rson].lmax); tree[now].rmax=max(tree[rson].rmax,tree[rson].v+tree[lson].rmax); tree[now].allmax=max(max(tree[lson].allmax,tree[rson].allmax),(tree[rson].lmax+tree[lson].rmax)); tree[now].v=tree[lson].v+tree[rson].v; } int main() { ios::sync_with_stdio(false); cin.tie(NULL),cout.tie(NULL); cin>>n>>m; for(int i=1;i<=n;i++) { cin>>val[i]; } build(1,n,1); for(int i=1;i<=m;i++) { int opt,l,r; cin>>opt; if(opt==1) { cin>>l>>r; if(l>r) swap(l,r); cout<<query(l,r,1).allmax<<endl; } if(opt==2) { cin>>l>>r; update(l,r,1); } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9396427.html
