小 W 喜欢研究排队序列。操场上全班同学排成一个队伍，小 W 认为如果有 4 位同学 ai,aj,ak,al的身高满足 ai=ak,aj=al，且 i<j<k<l 时，会构成一个交叉匹配， 但学生数较多，请编程帮助小 W 计算交叉匹配的个数。

暴力枚举4个同学是不现实的，考虑优化。
通过枚举 ai 和 ak，然后再找 aj 和 al，这样只要找到满足条件的 j 和 l，那么所有 i≤j≤k≤l≤n 的方案总数都是一个。也就是说，只要求出所有满足条件的 (i, k) 和 (j, l) 对的个数，即可求出交叉匹配的个数。
对于身高相同的同学，我们可以将其视为一类，这样问题转化为对于每一类，求出这一类中任意4个同学的方案总数之和。考虑到一个类中有 $c$ 个同学，那么总的方案总数是$c\choose 4$，可以通过组合数公式计算。而对于任意两个同学组成的组合，可以直接计算满足条件的方案总数，即两个同学中身高较高的人站在前面的方案数乘上身高较矮的人所能站的位置数。
具体的，对于身高相同的同学，将其存入一个集合中，从中任意选出两个同学，假设身高较高的同学的编号为 $p$，身高较低的同学的编号为 $q$，那么不难发现，方案数就等于 $p-1$ 个人中选 $3$ 个人的方案数乘上 $q$ 能够排在 p 前面的位置数，即 $q$ 前面有多少个同学是身高不低于 $q$ 的。计算完这些方案数之后，将它们相加即可。
时间复杂度 $O(c^2)$，其中 $c$ 表示同一类中的人数。
参考代码：

相关问题

将时间序列信号分割成一个个小段

可以使用滑动窗口的方法，将时间序列信号分割成固定长度的小段。也可以使用信号处理中的分段算法，根据信号的特征进行分段，比如变化点检测、峰值检测等。另外，也可以使用机器学习中的时间序列分析方法，比如HMM、LSTM等。

设计一个算法,采用分治法求一个包含n个整数的序列中的最大和最小元素。

分治法是将问题划分为更小的子问题，然后将子问题的解进行组合以得到原问题的解。对于求一个包含n个整数的序列中的最大和最小元素，可以采用以下算法：

1. 将序列分为两个子序列，分别为左子序列和右子序列。

2. 对左子序列和右子序列分别采用递归的方式继续分割，直到每个子序列只有一个元素。

3. 对于每个子序列，比较其中的元素，找出最大和最小的元素。

4. 将每个子序列的最大元素和最小元素进行比较，得到整个序列的最大和最小元素。

5. 返回最大和最小元素。

具体的实现步骤如下：

1. 若序列中只有一个元素，直接返回该元素作为最大和最小元素。

2. 将序列分为两个子序列，左子序列和右子序列。

3. 对左子序列采用分割的方式继续进行递归，找到左子序列的最大和最小元素。

4. 对右子序列采用分割的方式继续进行递归，找到右子序列的最大和最小元素。

5. 将左子序列的最大和最小元素与右子序列的最大和最小元素进行比较，得到整个序列的最大和最小元素。

6. 返回最大和最小元素。

这个算法的时间复杂度为O(n)，因为每次都将序列分为两个子序列，每个子序列的元素数量都减少一半，所以需要进行log(n)次递归操作，每次递归需要O(1)的时间复杂度，因此整个算法的时间复杂度为O(n)。该算法可以有效地找到序列中的最大和最小元素。