P2401

prob

有实力的。

这题与逆序对那题不同的是，那题求逆序对，我们只关心元素的相对顺序。本题中难以直接计算增加的 < 个数，需要分讨。分讨第 \(i\) 个元素插在哪：

1. 序列最开头。出现 \(i > S_1\)，无贡献。
2. 序列最末尾。出现 \(S_n < i\)，贡献加一。
3. \(S_l < S_r\) 之间。出现 \(S_l < i > S_r\)，无贡献。
4. \(S_l > S_r\) 之间。出现 \(S_l < i > S_r\)，贡献加一。

综上，对于一个 \(f_{i,j}\) 表示 \(i\) 个元素造了 \(j\) 个 <：

1. 假设第 \(i\) 个元素多造了一个 <，能插的位置就是 > 的位置加上序列末尾，即 \(i-2-(j-1) + 1\)，其中 \(i-2\) 表示符号个数，\(j-1\) 表示 < 个数。那么 \(f_{i,j} = f_{i,j} + f_{i-1,j-1} \times (i-j)\)。
2. 假设没造。能插的位置就是 < 的位置加上序列开头，即 \(j + 1\)。\(f_{i,j} = f_{i,j} + f_{i-1,j} \times (j+1)\)。

做完了。时间复杂度 \(O(n^2)\)。