题目
传送门：QWQ
分析
线段树维护一下最大子序列
维护一下最大前缀 最大后缀 区间和 就ok了
好像只能用结构体。。。。。
代码
#include <bits/stdc++.h> using namespace std; const int maxn=505000; int val[maxn<<2] ; struct Node{ int left,right,maxv,sum; }tree[maxn<<2]; void update(int o,int l,int r){ tree[o].sum=tree[o<<1].sum+tree[o<<1|1].sum; tree[o].left=max(tree[o<<1].left,tree[o<<1].sum+tree[o<<1|1].left); tree[o].right=max(tree[o<<1|1].right,tree[o<<1|1].sum+tree[o<<1].right); tree[o].maxv=max(tree[o<<1].right+tree[o<<1|1].left,max(tree[o<<1].maxv,tree[o<<1|1].maxv)); } void build(int o,int l,int r){ if(l==r){tree[o].sum=tree[o].left=tree[o].right=tree[o].maxv=val[l];return;} int mid=l+r>>1; build(o<<1,l,mid); build(o<<1|1,mid+1,r); update(o,l,r); } void modify(int o,int l,int r,int v,int L){ if(l>L||r<L) return; if(l==r){ tree[o].sum=tree[o].left=tree[o].right=tree[o].maxv=v; return;} int mid=l+r>>1; modify(o<<1,l,mid,v,L); modify(o<<1|1,mid+1,r,v,L); update(o,l,r); } Node query(int o,int l,int r,int L,int R){ if(L<=l&&R>=r) return tree[o]; int mid=l+r>>1; if(R<=mid) return query(o<<1,l,mid,L,R); else if(L>mid) return query(o<<1|1,mid+1,r,L,R); else{ Node res1=query(o<<1,l,mid,L,R),res2=query(o<<1|1,mid+1,r,L,R); Node res; res.sum=res1.sum+res2.sum; res.left=max(res1.left,res1.sum+res2.left); res.right=max(res2.right,res2.sum+res1.right); res.maxv=max(res1.right+res2.left,max(res1.maxv,res2.maxv)); return res; } } int main(){ int n,m;scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&val[i]); build(1,1,n); int k,a,b; while(m--){ scanf("%d%d%d",&k,&a,&b); if(k==1){if(a>b) swap(a,b); printf("%d ",query(1,1,n,a,b).maxv);} else modify(1,1,n,b,a); } }