T1. 逆序对
给出一个长度为 \(n\) 的排列 \(a\)，你需要交换其中两个元素，使得逆序对尽可能少，输出逆序对变化量。
\(1 \leq n \leq 10^6\)
先推式子，考虑交换 \(x,y(x\leq y)\) 两个位置的逆序对变化量。
容易发现逆序对减少了：
\[\sum_{k=x+1}^{y-1}[a_k\leq a_x]+\sum_{k=x+1}^{y-1}[a_k\geq a_y]-\sum_{k=x+1}^{y-1}[a_k\geq a_x]-\sum_{k=x+1}^{y-1}[a_k\leq a_y]+[a_i\geq a_j] \]且若上式大于 \(0\)，则 \(a_i\leq a_j\)。而我们只需要考虑大于 \(0\) 的情况，所以上式可以化简得：
\[2\times\left(\sum_{k=x+1}^{y-1}[a_k\leq a_x]-\sum_{k=x+1}^{x+1}[a_k\leq a_y]\right)+1 \]于是只需要高效计算上面的两和式之差即可。
先考虑如果存在一个 \(z\)，使得 \(z\leq x,a_z \geq a_x\)，则选 \(z\) 当左端点一定比选 \(x\) 不劣。如果存在一个 \(z\) 使得 \(z\geq y,a_z\leq a_y\) 则选 \(z\) 当右端点一定比选 \(y\) 不劣。
所以左端点一定是 \(a\) 的前缀最大值，右端点一定是 \(b\) 的后缀最小值。
然后我们维护和式较为不便，正难则反，我们可以维护一个东西可以对和式产生贡献。
如果将 \((l,r)\) 看成坐标轴上的一个点，则我们对于每一个元素 \(i\)，可以找到最左侧的值比 \(a_i\) 小的前缀最大值位置 \(x_1\) 和最左侧的位置比 \(i\) 小的前缀最大值位置 \(x_2\)。
找到最右侧值比 \(a_i\) 小与等于的后缀最小值位置 \(y_1\) 和 最右侧的位置比 \(i\) 小于等于的后缀最小值 \(y_2\)。
则 \(x_1 \leq l \leq x_2,y_1 \leq r \leq y_2\) 就会因为 \(i\) 产生 \(1\) 的贡献。注意这里的 \(l,r\) 只得是前缀最大/后缀最小值的下标。可以看成一个矩形。
于是你可以用扫描线找到矩形覆盖最多的一个点覆盖了多少下，就是上面的和式之差。
标签：geq,22,day9,sum,冲刺,leq,最小值,端点,逆序 From： https://www.cnblogs.com/zheyuanxie/p/17742391.html