发现大家都是维护的四个标记,提供一个维护三个标记的做法。
先做个前缀和,转化成维护类似 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;
}
问一下这个做法有名字吗,以及为什么没有人写。