好像题解区没有看到这种做法,与正常的四个标记的维护方法不同,这种做法只用三个标记。
将原序列做个前缀和,维护一个 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。