写在前面的话
考场估分 \(100+100+20+30=250\) ，实际得分 \(0+90+20+30=140\) 。这是停课以来挂分最为严重的一次，值得深思。挂分的原因也比较令人头疼，就是数组开大导致的 \(\text{MLE}\) 。所以我决定以后的每一次考试都要测试使用的内存大小：
fprintf(stderr,"%.3lf MB",(&Med-&Mbe)/(1.0*1024*1024));
希望自己以后不要犯这种低级错误。
本场比赛在改完题之后觉得难度为 \(\text{T3}-\text{T2}-\text{T1}-\text{T4}\) 。考试的时候偏执的认为啊 \(\text{T1}\) 就是最简单的一道而和大多数人一样忽略了 \(\text{T3}\) ，本来完全有实力打出这道题，但是不得不承认自己的考试策略有待进一步提升。
\(T1\)
题目描述
现在有一个长度为 \(n\) 的序列 \(a\) 。问交换两个元素最多可以让逆序对数量减少多少。
\(n \leqslant 10^6\) 。
思路点拨
题目非常的简洁，我提供一种自己的做法，不同于 \(\text{std}\) 。
首先十分显然的，对于另个元素 \(a_l,a_r\) ，如果 \(l<r\) 并且 \(a_l<a_r\) 我们就没有必要交换这两个元素，这只会给我们带来更多的逆序对数量，这里不考虑。
我们想一下，如果知道了我们需要交换 \(l,r\) ，那么如何快速的计算贡献呢？假设我们将每一个元素按照柱状图的形式画出来：
我们将这些数划分为三个部分：
-
\(A\) 部分：\(a_i>a_l\) 。
-
\(B\) 部分：\(a_r<a_i<a_l\) 。
-
\(C\) 部分：\(a_i<a_r\) 。
首先，不在这个区间内的元素的逆序对关系并不会边，我们就只需要大胆的考虑这个区间内产生的变化。对于 \(a_r\) 而言，与 \(A+B\) 部分的元素产生了逆序对关系，而到了 \(l\) 的位置之后则与 \(C\) 部分的元素产生关系，贡献就是 \(A+B-C\) 。对于 \(a_l\) 而言，他与 \(B+C\) 部分的元素产生了逆序对关系，但是到了 \(r\) 的位置之后则与 \(A\) 部分产生逆序对关系,贡献就是 \(B+C-A\) 。
总体来说，贡献就是 \((A+B-C)+(B+C-A)=2B\) ，加上 \(l,r\) 自身贡献了一个逆序对就是 \(2B+1\)。现在我们知道了，交换 \(l,r\) 的贡献就是 \(2\sum_{i=l}^r[a_r<a_i<a_l]\) 。如果需要统计的话，\(O(n^2)\) 可以考虑二维前缀和。\(O(n \log n)\) 可以考虑主席树，但是这都意义不大了，我们需要正解。
这样的结论显然是不足以写出正解，但是注意到交换 \(l,r\) 的时候产生贡献的元素需要满足什么要求？\(l<i<r\) ，并且 \(a_r<a_i<a_l\) 。这是一个二维关系，我们考虑将 \((i,a_i)\) 看做一个点放进平面直角坐标系里面，然后问题就是我们需要选出一个矩形的左上角和一个右下角，要求矩形内的元素数量尽量多。
考虑什么样的左上角是有意义的。如果对于一个左上角 \((i,a_i)\) ，存在 \((j,a_j)\) 满足 \(j<i\) ，同事 \(a_j>a_i\) ，那么 \(i\) 就是没有意义的。因为如果我们选择 \(j\) 作为左上角，以 \(i\) 作为左上角的矩形在同一个右下角的情况下会被包含，所以只会让贡献变小，就比如说：
所以谁更加牛逼一目了然吧。我们继续考虑对于右下角有需要满足什么条件。如果存在节点 \((i,a_i)\) ，但是有 \((j,a_j)\) 有 \(i<j\) ，同时 \(a_i>a_j\) 。那么 \(i\) 就是没有意义的。就比如说：
所以我们成功的缩小了左右端点的范围。接下来我们所说的左右端点只考虑这些有用的左右端点。
标签：T1,text,元素,贡献,左上角,test20230912,逆序 From： https://www.cnblogs.com/Diavolo/p/17697917.html