题目内容

在一家快速发展的互联网公司里，系统工程师小李正在开发一款高效的日志分析工具，旨在帮助运维团队更好地理解和优化语音合成系统的运行状况。为了提高工具的洞察力，他需要解决一个关键问题:如何通过分析一段时间内的合成请求的实时率 $RTF$ (合成耗时 /目标文本的音频时长)记录来识别“性能逆序对”的总数,实时率越高代表性能越差。

在这个系统中，“性能逆序对”被定义为一种情况，即如果某次请求的实时率比之后某次请求的实时率大，则这两者构成一个“性能逆序对”。这可以帮助运维团队识别出系统的性能退化点或者异常波动，从而采取措施优化系统性能。

具体来说，给定一个数组 $record$ ，它代表了一段时间内每次请求的实时率* $100$ (按时间顺序排列，因正常场景实时率 $<1$ ，因此对数值进行放大 $100$ 并取整)。小李的任务是设计并实现一个程序，该程序能够计算并返回这段时间内存在的“性能逆序对"总数。每个“性能逆序对”由两个索引 $i$ 和 $j$ 组成，满足条件 $0<=i<j<record.length$ 并且 $record[i] >record[j]$ 。如果 $record[i]-record[j]>threshold$ ，则该性能逆序对称为"严重性能逆序对"。

请协助小李完成这个功能的开发，确保它能高效地处理大量的日志数据，并提供即时反馈。具体任务包括编写一个函数，输入是一个整数数组 $record$，输出是其中存在的“严重性能逆序对”的总数。

题解

题面描述

给定长度为 $n$ 的整数数组 $\textit{record}$ （值域 $1\le \textit{record}[i]\le 50000$），以及一个阈值 $\textit{threshold}$。要求统计所有满足以下条件的“严重性能逆序对”数目：

• 对于索引对 $(i,j)$ ，满足 $0 \le i < j < n$；
• 并且 $\textit{record}[i] > \textit{record}[j]$ 且 $record[i]-record[j]>threshold$ ，则该性能逆序对称为"严重性能逆序对"。

输出满足上述条件的逆序对总数。数组长度可达 $10^5$，需在线性或近线性时间内完成。