思路与结论

• 只有“跨区间”的数对会受影响：

  • 新增逆序对：区间内的元素与区间右侧相同值形成的新逆序对（$a_i == a_j$ 且 $i$ 在区间内、$j$ 在区间右侧）。
  • 被消去的逆序对：区间左侧值为 $v+1$ 与区间内值为 $v$ 的数对（$a_p = a_q + 1$，$p$ 在区间左侧，$q$ 在区间内）。

• 将“选择区间 $[L,R]$ 并把区间内加 1”的收益定义为：

  • 收益 = 被消去对数 − 新增对数
  • 等价于：$sum_{q∈[L,R]} pre[L-1][a_q+1]$ − $sum_{q∈[L,R]} suf[R+1][a_q]$

题目内容

你有一个长度为 $n$ 的序列 $A:a_1,a_2,…,a_n$，你需要进行如下操作至多一次：

选择一个区间$[L,R](1≤L≤R≤n)$，将 $a_1,a_{L+1},...,a_R$ 全部加 $1$ 。即 $a_L,a_{L+1},...,a_R$ 均变为 $a_L+1,a_{L+1}+1,...,a_R+1$

设变化后的序列为 $B：b_1,b_2,…,b_n$，你需要最大化 $inv(A)-inv(B)$ ，其中 $inv()$ 函数表示该序列的逆序对数量，即满足 $i<j，a_1>a_j$ 的二元组 $(i,j)$ 个数。换句话说，你需要尽可能地减小序列 $A$ 的逆序对数量。