维护满足max(+ or -)min<=k的区间

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

上一篇:在 Centos7 的KVM上启用嵌套虚拟化


下一篇:spring boot @ResponseBody转换JSON 时 Date 类型处理方法,Jackson和FastJson两种方式,springboot 2.0.9配置fastjson不生效官方解决办法