HNOI2017 影魔

对于两种贡献，都只用考虑左边第一个比自己大的，和右边第一个比自己大的数，分别记为 \(l_i、r_i\)

对于询问一，每个数对 \((l_i,r_i)\) 构成全部情况
对于询问二，可以拆分成 \(x=l_i\) 时，\(y \in [i+1,r_i-1]\) ，以及 \(y=r_i\) 时，\(x \in [l_i+1,i-1]\)

我们考虑用扫描线实现，将这些贡献离线下来排序，我们扫描右端点
对于第一种，在我们扫描到 \(r_i\) 时，给 \(l_i\) 加上贡献
对于第二种，在我们扫描到 \(l_i\) 时，给 \([i+1,r_i-1]\) 区间加，另一个同理
答案为区间 \([l,r]\) 的和 （吗？）

我们会发现对于第二种情况的贡献我们可能会多算，于是我们可以在 扫描到 \(l-1\) 的时候，给答案先减去此时的和，这样就对了