CF 下分记录
7.27 edu152
\(+173=2048\)
B 没细看数据范围 WA 了一次
D 没判 \(i-1=0\) WA 了一次
E. Max to the Right of Min
考虑增大右端点，维护每个左端点的合法性
当右端点从 \(r-1\) 增大到 \(r\) 时，
- 若 \(a[r-1]<a[r]\)：\(r\) 只能作为区间最大值。记上一个 \(>a[r]\) 的位置是 \(p\)，那么 \(i\in(p,r],[i,r]\) 的最大值是 \(r\)，一定合法。对于 \(i\le p\)，最值都不是 \(r\)，合法性不变
- 若 \(a[r-1]>a[r]\)：\(r\) 只能作为区间最小值。同理
数据结构维护合法的左端点，支持插入/删除末尾一个区间。使用栈可以做到 \(O(n)\)