LOJ #3470. 「JOI 2021 Final」集体照
设最终操作成的序列为 \(b\)，由于其满足 \(b_i \le b_{i+1}+1\)，我们可以得知它相当于把 \(1,2,\cdots, n\) 划分成若干个区间，每个区间翻转所得到的排列。
要求最小化 \(N(b\circ a^{-1})\)。而 \(b\circ a^{-1}\) 就是相当于把 \(a^{-1}\) 划分成若干个区间，每个区间翻转所得到的排列，要最小化逆序对数。
考虑 DP，设 \(dp(i)\) 表示 前 \(i\) 个数进行翻转操作后所得逆序对最小值，转移为 \(dp(i)=\min_{j=1}^{i} \{dp(j-1)+W(j-1,i)+\binom{i-j+1}{2}-N(j,i)\}\)，其中 \(N(j,i)\) 表示区间 \([j,i]\) 的逆序对数，\(W(j-1,i)=\sum_{x\in[1,j-1],y\in[j,i]}[a_x>a_y]\) 。注意到 \(W\) 和 \(N\) 是可以 \(O(n^2)\) 预处理的，DP 也是 \(O(n^2)\)，总时间复杂度 \(O(n^2)\)。
代码
LOJ #3469. 「JOI 2021 Final」雪球
每个雪球的雪都是一段区间，二分求出左右端点即可。
LOJ #2765. 「JOI 2013 Final」 冒泡排序
最大化交换 \(a_i,a_j\) 后逆序对的减小量，即最大化 \(\sum_{k=i+1}^{j-1}[a_i>a_k>a_j]\)。
要想这个最大，首先发现 \(a_i>a_j\)，进一步地，\(a_i\) 必须是前缀最大值，\(a_j\) 必须是后缀最小值。
用点 \((i,j)\) 表示交换 \(a_i,a_j\) 的答案，其中第一分量只包含前缀最大，第二分量只包含后缀最小，此时每个点的贡献是一个矩阵，扫描线求出最大的点即可。
核心在于单独拎出来前缀最大和后缀最小，这样把点的贡献成了矩形加。