线段树嘛,94维护的东西罗嗦些。为了确保找到最大子序和,要维护的有:
最大的左缀和lsm及其右端点ly,最大的右缀和rsm及其左端点rz,最大情况zsm及其zz和zy端点。

对于up()(感觉自己稍骚,其实跑得慢,还码量大)
起初,一直WA13,忘记传儿子的zsm了
void up(ll u,ll l,ll r){ pai.clear(); ll mid=l+r>>1; sm[u]=sm[ls]+sm[rs]; pai.push_back(node(l,r,sm[u])); if(lsm[ls]>=sm[ls]+lsm[rs]){ lsm[u]=lsm[ls]; ly[u]=ly[ls]; } else{ lsm[u]=sm[ls]+lsm[rs]; ly[u]=ly[rs]; } pai.push_back(node(l,ly[u],lsm[u])); if(rsm[rs]>sm[rs]+rsm[ls]){ rsm[u]=rsm[rs]; rz[u]=rz[rs]; } else{ rsm[u]=sm[rs]+rsm[ls]; rz[u]=rz[ls]; } pai.push_back(node(rz[u],r,rsm[u])); pai.push_back(node(rz[ls],mid,rsm[ls])); pai.push_back(node(mid+1,ly[rs],lsm[rs])); pai.push_back(node(rz[ls],ly[rs],lsm[rs]+rsm[ls])); pai.push_back(node(zz[ls],zy[ls],zsm[ls])); pai.push_back(node(zz[rs],zy[rs],zsm[rs])); sort(pai.begin(),pai.end(),cmp); zsm[u]=pai[0].w; zz[u]=pai[0].l; zy[u]=pai[0].r; }
讯享网
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/113380.html