Code:
#include#define N 50001 #define ll long long #define lson now<<1 #define rson now<<1|1 #define inf 1000000000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; ll A[N]; struct Matrix { ll a[3][3]; ll*operator[](int x) {return a[x];} void re() {memset(a,0,sizeof(a));} void Min() {for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[i][j]=-inf;} ll getmax() {return max(a[0][1], a[2][1]);} }t[N<<2]; Matrix operator*(Matrix a,Matrix b) { int i,j,k; Matrix c; c.Min(); for(i=0;i<3;++i) { for(j=0;j<3;++j)for(k=0;k<3;++k) c[i][j]=max(c[i][j],a[i] [k]+b[k][j]); } return c; } void pushup(int l,int r,int now) { t[now]=t[lson]; int mid=(l+r)>>1; if(r>mid) t[now]=t[now]*t[rson]; } void build(int l,int r,int now) { if(l==r) { t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=A[l]; t[now][0][2]=t[now][1][0]=t[now][1][2]=-inf; t[now][1][1]=t[now][2][2]=0; return; } int mid=(l+r)>>1; if(l<=mid) build(l,mid,lson); if(r>mid) build(mid+1,r,rson); pushup(l,r,now); } Matrix qmax(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) return t[now]; int mid=(l+r)>>1; Matrix re; if(L<=mid) { re=qmax(l,mid,lson,L,R); if(R>mid) re=re*qmax(mid+1,r,rson,L,R); } else { re=qmax(mid+1,r,rson,L,R); } return re; } void update(int l,int r,int now,int p,int v) { if(l==r) { A[p]=v; t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=v; return; } int mid=(l+r)>>1; if(p<=mid) update(l,mid,lson,p,v); else update(mid+1,r,rson,p,v); pushup(l,r,now); } int main() { // setIO("input"); int n,q,i,j; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%lld",&A[i]); build(1,n,1); scanf("%d",&q); for(i=1;i<=q;++i) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==0) { update(1,n,1,l,r); } else { if(l>r) swap(l,r); printf("%lld ",qmax(1,n,1,l,r).getmax()); } } return 0; }
#include#define N 50001 #define ll long long #define lson now<<1 #define rson now<<1|1 #define inf 1000000000 #define setIO(s) freopen(s".in","r",stdin) using namespace std; ll A[N]; struct Matrix { ll a[3][3]; ll*operator[](int x) {return a[x];} void re() {memset(a,0,sizeof(a));} void Min() {for(int i=0;i<3;++i) for(int j=0;j<3;++j) a[i][j]=-inf;} ll getmax() {return max(a[0][1], a[2][1]);} }t[N<<2]; Matrix operator*(Matrix a,Matrix b) { int i,j,k; Matrix c; c.Min(); for(i=0;i<3;++i) { for(j=0;j<3;++j)for(k=0;k<3;++k) c[i][j]=max(c[i][j],a[i] [k]+b[k][j]); } return c; } void pushup(int l,int r,int now) { t[now]=t[lson]; int mid=(l+r)>>1; if(r>mid) t[now]=t[now]*t[rson]; } void build(int l,int r,int now) { if(l==r) { t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=A[l]; t[now][0][2]=t[now][1][0]=t[now][1][2]=-inf; t[now][1][1]=t[now][2][2]=0; return; } int mid=(l+r)>>1; if(l<=mid) build(l,mid,lson); if(r>mid) build(mid+1,r,rson); pushup(l,r,now); } Matrix qmax(int l,int r,int now,int L,int R) { if(l>=L&&r<=R) return t[now]; int mid=(l+r)>>1; Matrix re; if(L<=mid) { re=qmax(l,mid,lson,L,R); if(R>mid) re=re*qmax(mid+1,r,rson,L,R); } else { re=qmax(mid+1,r,rson,L,R); } return re; } void update(int l,int r,int now,int p,int v) { if(l==r) { A[p]=v; t[now][0][0]=t[now][0][1]=t[now][2][0]=t[now][2][1]=v; return; } int mid=(l+r)>>1; if(p<=mid) update(l,mid,lson,p,v); else update(mid+1,r,rson,p,v); pushup(l,r,now); } int main() { // setIO("input"); int n,q,i,j; scanf("%d",&n); for(i=1;i<=n;++i) scanf("%lld",&A[i]); build(1,n,1); scanf("%d",&q); for(i=1;i<=q;++i) { int op,l,r; scanf("%d%d%d",&op,&l,&r); if(op==0) { update(1,n,1,l,r); } else { if(l>r) swap(l,r); printf("%lld ",qmax(1,n,1,l,r).getmax()); } } return 0; }