考虑维护出每一个点左边第一个比它大的位置，右边同理，这样有一个合法区间。
然后对询问离线，由于要求只包含区间内的贡献，扫描线+线段树解决。
T1
http://codeforces.com/problemset/problem/1117/G
考虑一下笛卡尔树，然后分析出答案等于这个区间形成的笛卡尔树的所有节点的子树和。
再做一步转化就等价于有多少个节点存在祖先与后代的关系。
这个又等价于最开始的那个问题。
T2
https://www.luogu.org/problemnew/show/P3722
题意转化出来是：
一个端点为最大值，另一个端点是次大值贡献为p1。
一个端点为最大值，另一个端点不是次大值贡献为p2。
考虑先把所有有一个端点为最大值得区间全部记贡献为p2。
然后由于条件1和条件2的第二部分是互补的,只需要修改一部分贡献为p1即可。（如果不是互补的,你只改一部分另一部分还会包含不合法的。）
如果考虑去找以x为最大值,哪些位置可以为次大值并不容易。
考虑反向操作,找以x为次大值，哪些位置可以为最大值。
这个显然就只有两个位置。（也就是之前预处理出来的左/右第一个比它大的位置）
同样的方法用线段树维护即可。