题意
给一个长度为 \(n\) 的排列 \(a\)，和一个 \(3\) 的排列 \(p\)。求问 \(a\) 有多少长度为 \(3\) 的子序列，满足将其中的元素从小到大编号后为 \(p\)。
思路
仔细手玩一下会发现很难找到一个对于任意 \(p\) 的通解，实际上 \(p\) 的情况可以做一些合并：
| 原 \(p\) | 归约方法（对于 \(a\) 的变换） | 归约至 \(p'\) |
|---|---|---|
| \(1,2,3\) | 不需要归约 | \(1,2,3\) |
| \(1,3,2\) | 不需要归约 | \(1,3,2\) |
| \(2,1,3\) | \(a_i\) 变为 \((n+1)-a_i\)，\(a\) 再倒序 | \(1,3,2\) |
| \(2,3,1\) | \(a\) 变为倒序 | \(1,3,2\) |
| \(3,1,2\) | \(a_i\) 变为 \((n+1)-a_i\) | \(1,3,2\) |
| \(3,2,1\) | \(a\) 变为倒序 | \(1,2,3\) |
因此，问题变为了只需要针对 \((1,2,3)\) 和 \((1,3,2)\) 的情况求解。
- 求数列中大小顺序为 \((1,2,3)\) 的子序列，这是一个很典型的思路，我们遍历子序列的中心点，并用树状数组 \(O(\log n)\) 动态维护该点左右边的数，每次遍历到一个点 \(O(\log n)\) 查询该点左边比它小的和右边比他大的数有多少个，相乘即可得到以该点为中心点的满足大小顺序 \((1,2,3)\) 的子序列数。最后相加即可，整体时间复杂度 \(O(n\log n)\)。
- 求数列中大小顺序为 \((1,3,2)\) 的子序列，经尝试后会发现很难用如上遍历中心点的思想来维护，此时其实可以考虑“减法原理”，即可以先求出 \((1,2,3)\) 和 \((1,3,2)\) 的子序列数之和之后再减去 \((1,2,3)\) 的子序列数。而求 \((1,2,3)\) 和 \((1,3,2)\) 的子序列数之和即是求中间右边大于左边的三元子序列数，此时只需要遍历最左侧点，树状数组动态维护右侧比该点大的数的个数，记为 \(k\)，则符合要求的三元子序列显然为 \(\frac{k(k-1)}{2}\) 个。