题解: 这个题可以采取离线处理的方式.先处理出每个点i左边第一个比它大的点L[i]L[i]L[i],和右边第一个比它大的点R[i]R[i]R[i]. 那么对于区间L[i]L[i]L[i]到R[i]R[i]R[i]有p1p1p1的贡献.①①① 对于左端点在L[i]+1L[i]+1L[i]+1到i−1i-1i−1,右端点为R[i]R[i]R[i]的区间有p2p2p2的贡献.②②② 对于左端点为L[i]L[i]L[i],右端点为i+1i+1i+1到R[i]−1R[i]-1R[i]−1的区间也有p2p2p2的贡献.③③③ 所以我们离线排序处理好. 对于①①①情况,我们在扫到R[i]R[i]R[i]时,更新点L[i]L[i]L[i]的贡献 对于②②②情况,我们在扫到R[i]R[i]R[i]时,更新区间L[i]+1L[i]+1L[i]+1到i−1i-1i−1的贡献 对于③③③情况,我们在扫到L[i]L[i]L[i]时,更新区间i+1i+1i+1到R[i]−14R[i]-14R[i]−14的贡献 我们对于每个询问[l,r][l,r][l,r],在扫到l−1-1−1时,我们记录此时区间lll到rrr的每个点的贡献和为sum1sum1sum1,然后当我们扫到rrr的时候,再次记录此时的区间lll到rrr的每个点的贡献和为sum2sum2sum2,显然答案就是sum2−sum1sum2-sum1sum2−sum1了. 鹅鹅鹅，建议看到最后 别走！！！这里才是正确代码：：