这道题目的思想非常新
首先我们按照比较传统的想法，考虑交换两个位置\(i\)和\(j\)能带来什么影响
然后这就是这道题目的精华所在了，我们考虑影响的时候，没有必要去精确每一个位置的两个信息（左边更大的数的个数和右边更小的数的个数）怎么样变化，而是只用考虑这一次交换会让答案增大多少
我们先考虑\((i,j)\)，不难发现，如果某一个数（设为\(x\)）左边恰好有一个数比其大，右边恰好有一个数比其小，而且恰好分别对应下标\(i\)和\(j\)，那么\(x\)就会对\(i,j\)的交换产生一个贡献
再考虑\(i\)或\(j\)是否会产生贡献，比如\(i\)，显然只有将\(i\)交换到下标\(p_i\)时才会产生贡献
而在区间\([i,j]\)外面的都不用考虑
综上所述，有效的区间最多有\(2n\)个，用map记录即可
没写代码，写一下
标签：数比,交换,Should,Field,考虑,Empty From： https://www.cnblogs.com/dingxingdi/p/18033220