最大子段和的另一种维护方法
查看原帖
最大子段和的另一种维护方法
167936
linanchen楼主2025/7/23 13:14

好像题解区没有看到这种做法,与正常的四个标记的维护方法不同,这种做法只用三个标记。

将原序列做个前缀和,维护一个 max{a[r]a[l]}\max\{a[r]-a[l]\} 之类的东西。这个维护区间最大值、最小值就可以了。

inline friend Node operator+(const Node&x,const Node&y) {
	Node ans;ans.maxx=max(x.maxx,y.maxx);ans.minn=min(x.minn,y.minn);
	ans.ans=max({x.ans,y.ans,y.maxx-x.minn});return ans;
}

想询问一下这个做法有没有名字,或者求 Hack。

2025/7/23 13:14
加载中...