本文共 1318 字，大约阅读时间需要 4 分钟。
（分析见正睿2018.10.1笔记）
代码
#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;struct node { int pre,sur,ans,sum;};node d[200100];inline node work(node x,node y){ node res; res.sum=x.sum+y.sum; res.pre=max(x.pre,x.sum+y.pre); res.sur=max(y.sur,y.sum+x.sur); res.ans=max(max(x.ans,y.ans),x.sur+y.pre); return res;}inline void update(int le,int ri,int wh,int pl,int k){ if(le==ri){ d[wh].pre=d[wh].sur=d[wh].ans=d[wh].sum=k; return; } int mid=(le+ri)>>1; if(mid>=pl)update(le,mid,wh<<1,pl,k); else update(mid+1,ri,wh<<1|1,pl,k); d[wh]=work(d[wh<<1],d[wh<<1|1]); return; }inline node q(int le,int ri,int wh,int x,int y){ if(le>=x&&ri<=y){ return d[wh]; } int mid=(le+ri)>>1,cnt=0; node a,b; if(mid>=x)cnt+=1,a=q(le,mid,wh<<1,x,y); if(mid <<1|1,x,y); if(cnt==1)return a; if(cnt==2)return b; return work(a,b);} int main(){ int n,m,i,j,k,x,y; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&x); update(1,n,1,i,x); } scanf("%d",&m); for(i=1;i<=m;i++){ scanf("%d%d%d",&k,&x,&y); if(k==0){ update(1,n,1,x,y); }else { printf("%d\n",q(1,n,1,x,y).ans); } } return 0;}
转载于:https://www.cnblogs.com/yzxverygood/p/9748495.html