# 1 冒泡排序(bubble)

相信大家做过今年的 NOI（2018）。  

众所周知，排列合法当且仅当最长下降子序列不超过 $2$。  

为了方便我们将最长下降子序列的限制变成最长上升子序列的限制。  

特别地 $( a+b=n-1)$ 的情况。  

当 $( a+b<n-1)$ 时，可以将序列和值域都反转，$( a' = n - a - 1, b' = n - b - 1 )$。  

将 \((i, p_i)\) 在平面上画出来，(a, b) 将平面分成了四个区域，不难发现左下和右上不能同时有点。  

假设左没有点，那么左上有 \( a \) 个点，右下有 \( b \) 个点，右上有 \( n - 1 - a - b < 0 \) 个点，不合法。  

不难发现左下的点一定是单调递减的，可以将问题划分成下方和左方两个子问题，相当于要解决 \( b = n - 1 \) 的情况。  

一个合法的序列可以唯一对应一条从 \((0, n)\) 到 \((n, 0)\) 的路径，满足任意时刻 \( x + y \leq n \)，路径长成 \( f(x) = \min_{x \leq y} p_x \) 的形式。  

那么 \( b = n - 1 \) 的情况相当于一个长度为 \( b \) 的合法序列，前 \( a \) 个位置都是前缀最小值。  

前 \( a \) 个位置假设往下走了 \( t(t \geq a) \) 步，  

前面就是方程 \( x_1 + x_2 + x_3 + \cdots + x_a = t \) 的正整数解的个数，就是 $C_{t-1}^{a-1}$。  

后面是从 \((a, b - t)\) 走到 \((b, 0)\) 的方案数，是 $(C_{2b-a-t}^{b-a} - C_{2b-a-t}^{b-a+1})$。  

组合解是相当于从 \( 2b - a \) 个数里面选 \( b \) 个，以第 \( a \) 个数为分界线，枚举左右各有多少个数。  

同理 \(\sum_t C_{t-1}^{a-1} C^{2b-a-t}_{b-a+1} = C_{2b-a}^{b+1}\)。  

对于左方的子问题，将值和值域倒过来就变成下方的子问题了。  

但是这是 NOIP 模拟，所以肯定有更简单的做法。  

我们算左下没有点的情况，那么注意到 \((a, b)\) 这个位置是前缀最小值，那么考虑统计前缀最小值序列个数。  

还是用路径来刻画这个东西，可以发现这个限制等价于 \((a, b)\) 这里的路径是这样走的：\((a, b + 1) \to (a, b) \to (a + 1, b)\)。  

那么两边分开了，用折线法算方案数就行了。