最大最小（C题）

在我自己blog写的详细点（比较懒，这里就复制解法给大家看）。
blog：https://www.cnblogs.com/grisaia/p/13418456.html（参考别人代码写的，打的时候没过）。

解法：

  1. 首先用一个数组储存A[i]前面第一个比他小的值的下标。即pr[i]
  2. 再用一个数组储存A[i]之后第一个比他小的值的下标。即nt[i]
  3. 然后用同样的做法，但是中间需要以2分查找的方式找到在i前面第一个大于2倍A[i]的下标。
  4. 最后对每一个pr1[i]=max(pr[i],pr[i]) nt1[i]=min(nt[i],nt1[i]):这一步可以在pr1和nt1生成时候做。
  5. 最后循环n次。ans+=(i-pr[i])*(nt[i]-i)-(i-pr1[i])*(nt1[i]-i)。

解析：

为什么要求第一个前后最小啦？

由于求区间最大最小。求左右最小也就是该数值能成为最小的作用的区域。也就是pr[i]~nt[i]区间A[i]都是最小。

既然我们求得了一个值在最小作用的区域。第二步那就是在此区域内pr[i]~nt[i]大于A[i]2倍的值。用2分找到。

左边区间即为1~pr1[i]。右边即为nt1[i]~n;

由于区间最小区域要和大于两倍A[i]的区域重叠才能有解。（不重叠你就算是区间最最小，没有大于2倍也没有区间满足）

所以会有第4步。不过做的时候可以直接就求出区间重叠部分。（代码也是这么写的）

最后计算就是：包含i在内所有的区间减去不满足条件的区间。比如pr1[i]-i之间就不存在大于A[i]2倍的值。所以直接减去。