这个题细节有点多啊。
考虑冒泡排序的本质，就是对于一个 a_i 满足 \max\limits_{j = 1} ^ {i - 1}{a_j} < a_i 将它交换到第一个比它大的数之前。更直观的，记 pre_i = \max\limits_{j = 1} ^ i a_i，在一个坐标系上出现 (i, pre_i) 这个点。
如果一个排列建出来长这个样子，那么显然的就是对于类似 BF 的线段（即这一段所有前缀最大值相等）上面所有点会循环左移，即除开头外，其它元素向前移动 1，开头移动到结尾。
这个时候性质就足够了，可以 dp 了。
设 f(i, j) 表示填了前 i 个数，当前最大值为 j 的方案数。（即会出现 (i, j) 的方案数）。
转移的话，根据上述模拟的过程可以推出来，当前位置 j 要填 i 的话，要么 j 是 i 开头的段的结尾；要么就是 i 不是某一段开头，且 j + 1 填 i。
记 cnt_j 表示 Q 中 [i + 1, n] 中 [1, j] 的出现次数。
根据上述过程可知，i 填的数和 Q_{i - 1} 有关。
- 若 Q_{i - 1} = -1 则当前位置可以随意填，无影响，则
- 若 k > j，则 f(i, k) \leftarrow f(i - 1, j)。
- 否则，f(i, j) \leftarrow f(i - 1, j) \times (j - (i - 1) - cnt_{j - 1})。
- 若 Q_{i - 1} \neq -1，则有两种情况，
- 若 Q_{i - 1} < j 则当前位置必须填 Q_{i - 1}，而 Q_{i - 1} < j 小不会影响前缀最大值，f(i, j) \leftarrow f(i - 1, j)。
- 否则，这一段到这里就结束了，因此当前的数需要比 Q_{i - 1} 大，即
这样就能写出 \mathcal{O}(n ^ 3) 的代码了，而每次区间加都是加的后缀，差分维护即可实现 \mathcal{O}(n ^ 2)。
\texttt{Code}