Description

对于100%的数据，n<=500000,0<=A[i]<=10^9

线段树

比赛时想到的辣鸡方法 枚举区间右端点r，更新将[i,r-1]的答案更新为[i,r]的答案 该点会更新连续向左一段，一直到某个位置pos，已经出现比该点大，比该点小的点 那么1~pos-1答案不变 于是可以用线段树来维护区间[i,r]的最值与答案，代码繁琐，O（nlogn）

分治

就像往常一样从中间分开，考虑跨mid的区间的贡献 那么按照mid+1~r的顺序枚举右端点 左端点取值[l,mid]，可以按照最值在左边还是右边来分成3段，每段答案相同 段之间分界的位置可以二分，当然可以维护指针，由于右端点单调向右，所以指针单调向左移动 细节较多，O(nlogn)