[Vijos1083 小白逛公园] 【线段树维护最大子段和】

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1756
【算法分析】
就是线段树动态维护最大子段和。实际易错较难的就只是update函数和找ans部分。
注意维护Lmax,Rmax,ans,Sum这4个域即可。
【其它】
1Y。
MS是oimaster大神出的题。。。但据说是动态树= =。。。貌似不是这题？好像还有小白逛公园加强版。。。不过不知道哪里有得交。。。
【CODE】
#include #include #include const int N=505555;
int n,m,res,Follow;
int w[N];
struct Node{int l,r,Lmax,Rmax,ans,Sum;}Tr[N*3];

void init(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++) scanf("%d",&w[i]);
}

int max(int x,int y){return x>y?x:y;}

void update(int p){
Tr[p].Sum=Tr[p*2].Sum+Tr[p*2+1].Sum;
Tr[p].Lmax=max(Tr[p*2].Lmax,Tr[p*2].Sum+Tr[p*2+1].Lmax);
Tr[p].Rmax=max(Tr[p*2+1].Rmax,Tr[p*2+1].Sum+Tr[p*2].Rmax);
Tr[p].ans=max(Tr[p*2].ans,Tr[p*2+1].ans);
Tr[p].ans=max(Tr[p].ans,Tr[p*2].Rmax+Tr[p*2+1].Lmax);
}

void build(int p,int l,int r){
Tr[p].l=l; Tr[p].r=r;
if (l==r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=w[l];
return;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
update(p);
}

void Change(int p,int pos,int key){
if (Tr[p].l==Tr[p].r){
Tr[p].Lmax=Tr[p].Rmax=Tr[p].ans=Tr[p].Sum=key;
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (pos<=mid) Change(p*2,pos,key);
else Change(p*2+1,pos,key);
update(p);
}

void Get(int p,int l,int r){
if (l<=Tr[p].l && Tr[p].r<=r){
res=max(res,Tr[p].ans);
res=max(res,Tr[p].Lmax+Follow);
Follow=max(Tr[p].Rmax,Tr[p].Sum+Follow);
return;
}
int mid=(Tr[p].l+Tr[p].r)/2;
if (l<=mid) Get(p*2,l,r);
if (r> mid) Get(p*2+1,l,r);
}

void solve(){
int op,x,y,i;
for (i=1;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if (op==1){
res=-0x7FFFFFFF; Follow=0;
if (x>y){x^=y; y^=x; x^=y;}
Get(1,x,y);
printf("%dn",res);
}
else Change(1,x,y);
}
}

int main(){
init();
build(1,1,n);
solve();
}