题解

题面描述

给定长度为 $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$，需在线性或近线性时间内完成。

题目内容

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

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

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

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

输入描述

每组数据第一行为严重性能逆序对的阈值 $threshold$ ，第二行为日志数量 $n$ ,第三行为日志数据的数组 $record$ ，数组数值可能重复

输入范围限制:

$0<record.length <= 100000$

$0< record[i] <= 50000$

输出描述

严重性能逆序对的总数

样例1

输入

2
5
9 7 5 4 6

输出

4

说明

输入：$record=[9,7,5,4,6],threshold=2$

输出：$4$

解释：日志中的严重性能逆序对为 $(9,5),(9,4),(9,6),(7,4)$，这些逆序对满足序对第一个值大于第二个且差值大于 $2$

样例2

输入

3
2
5 1

输出

1

说明

输入：$record=[5,1],threshold=3$

输出：$1$

解释：日志中的严重性能逆序对为 $(5,1)$ ，这些逆序对满足序对第一个值大于第二个且差值大于 $3$

样例3

输入

3
2
1 5

输出

0

说明

输入：$record=[1,5],threshold-3$

输出：$0$

解释：无逆序列