线段树+DP 求区间连续最大子段和 hoj Candy
#include <stdio.h>#include <cstring>#define maxn 100001#include <iostream>using namespace std;int m[maxn<<2],f[maxn<<2],b[maxn<<2],sum[maxn<<2];void pushup(int rt){ m[rt]=max(m[rt<<1],m[rt<<1|1]); m[rt]=max(m[rt],b[rt<<1]+f[rt<<1|1]); sum[rt]=sum[rt<<1]+sum[rt<<1|1]; f[rt]=max(f[rt<<1],sum[rt<<1]+f[rt<<1|1]); b[rt]=max(b[rt<<1|1],sum[rt<<1|1]+b[rt<<1]);}void build(int l,int r,int rt){ if(l==r) { scanf("%d",&m[rt]); f[rt]=b[rt]=sum[rt]=m[rt]; return ; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt);}void update(int c,int p,int l,int r,int rt){ if(l==r) { m[rt]=p; sum[rt]=f[rt]=b[rt]=p; return ; } int mid=(l+r)>>1; if(c<=mid) update(c,p,l,mid,rt<<1); else update(c,p,mid+1,r,rt<<1|1); pushup(rt);}int main(){ int n,t,a,bb; while(scanf("%d%d",&n,&t)==2) { memset(m,0,sizeof(m)); memset(f,0,sizeof(f)); memset(b,0,sizeof(b)); memset(sum,0,sizeof(sum)); build(1,n,1); while(t--) { scanf("%d%d",&a,&bb); update(a,bb,1,n,1); printf("%d\n",m[1]); } } return 0;}
