小 W 喜欢研究排队序列。操场上全班同学排成一个队伍，小 W 认为如果有 4 位同学 ai,aj,ak,al的身高满足 ai=ak,aj=al，且 i<j<k<l 时，会构成一个交叉匹配， 但学生数较多，请编程帮助小 W 计算交叉匹配的个数。第一行为正整数 t(≤5)，表示数据组数；每组数据中，第一行为正整数 n(≤ 5000)，第二行为个正整数 ai(≤200)，表示每位同学的身高 c++编程

思路：

对于每个学生 i，记录有多少个和他身高相同的学生 j 在他前面，设为 pre[i]。然后再对于每个学生 j，记录有多少个和他身高相同的学生 i 在他后面，设为 suf[j]。这样，如果一个交叉匹配满足条件，则一定存在一个满足前者身高相同，后者身高相同，且前者比后者先出现的配对 $(i,j)$。因此，我们可以枚举前者 i，然后统计有多少个 j 满足前者身高相同，后者身高相同，且前者比后者先出现的条件，即 $pre[i]<j\leq n-suf[i]$，其中 n 为总人数。这个过程可以使用前缀和优化为 $O(n)$ 的时间复杂度。

代码：

相关问题

小 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等。