这是一种经典的单调栈+线段树的维护方法。
从左到右枚举右端点。
线段树维护每一个左端点的max(+ or -)min的值。
每次右端点移动的时候,把a[i]加入单调栈。
每弹栈一次,便在线段树上把对应弹掉的区间加上a[i]-a[s[top]]。
时间复杂度是均摊O(nlogn)的。
2024-02-22 20:25:04
这是一种经典的单调栈+线段树的维护方法。
从左到右枚举右端点。
线段树维护每一个左端点的max(+ or -)min的值。
每次右端点移动的时候,把a[i]加入单调栈。
每弹栈一次,便在线段树上把对应弹掉的区间加上a[i]-a[s[top]]。
时间复杂度是均摊O(nlogn)的。