算法面试真题：给定n数排列数组，求满足指定条件的五元组(i,j,k,l,m)数量

约束拆分 #

原问题要求统计满足下标顺序i<j<k<l<m且值顺序a[i]<a[k]<a[j]<a[m]<a[l]的五元组总数，我们可以通过拆分约束大幅降低时间复杂度：
把五元组的约束拆分为以(j,k)为中间连接点的两部分：

• 左半部分：i<j且a[i]<a[k]
• 右半部分：l>k、m>l且a[j]<a[m]<a[l]
  当固定满足j<k且a[k]<a[j]的(j,k)对时，当前对能贡献的五元组数量 = 左半部分合法i的数量 * 右半部分合法(l,m)对的数量，累加所有合法(j,k)对的贡献即可得到最终答案。

立方级复杂度实现（O(n³)） #

如果对性能要求不高，可先实现立方级方案，比暴力枚举C(n,5)快两个数量级：

• 遍历所有满足j<k且a[k]<a[j]的(j,k)对，时间复杂度O(n²)
• 左半部分合法i的数量：遍历0到j-1统计小于a[k]的元素个数，单次O(n)
• 右半部分合法(l,m)对的数量：遍历所有k<l<m，统计满足a[j]<a[m]<a[l]的对数，单次O(n)
  整体复杂度O(n³)，适用于n≤200的场景。

平方级复杂度实现（O(n²)） #

利用排列数组元素值为1~n且不重复的特性，预处理前缀、后缀计数数组可将单次查询降到O(1)，实现平方级复杂度：

1. 预处理左半部分计数
   维护前缀计数数组pre_cnt，pre_cnt[v]表示前j个元素中值小于等于v的元素总数。遍历j从0到n-1，对每个j遍历k从j+1到n-1，若a[k]<a[j]，则左半部分合法i的数量为pre_cnt[a[k]-1]，查询耗时O(1)。每轮j遍历结束后将a[j]加入pre_cnt更新。
2. 预处理右半部分计数
   维护二维后缀计数数组suf_pair[v]，suf_pair[v]表示当前位置右侧所有值大于v的元素中，满足l<m且a[l]>a[m]的逆序对总数。从数组末尾向左遍历更新：

• 每新增一个元素x = a[k]，对所有v < x，suf_pair[v]新增的逆序对数量等于当前右侧值在(v, x)区间内的元素个数
• 可提前维护后缀元素频率数组，O(1)计算区间内元素个数
  预处理完成后，对任意(j,k)对，右半部分合法(l,m)的数量直接取suf_pair[a[j]]即可，查询耗时O(1)。
  该方案适用于n≤2000的场景，比立方级方案性能提升一个数量级。

可选优化（O(n² logn)） #

如果n更大，可使用树状数组（BIT）代替前缀、后缀的数组计数，将空间复杂度从O(n²)降到O(n)，时间复杂度维持在*O(n² logn)*级别，适用于n≤5000的场景。

内容的提问来源于stack exchange，提问作者KnightKnight