题解

题面描述

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

思路

1. 离散化
   由于 $\textit{record}[i]$ 最大为 $50000$，可直接作为树状数组大小，但若值域更大则需先离散化。

2. 倒序遍历
   我们从右向左扫描数组，维护一个树状数组 BIT，用于统计已经遍历过的元素的出现次数。

3. 查询计数
   对于当前元素 $x = \textit{record}[i]$，要找出后面位置上所有满足
   $y < x - \textit{threshold}$
   的元素个数，即查询
   

4. 更新树状数组
   在查询完当前 $x$ 后，将其在 BIT 中的计数加 1：

   $$\text{update}(x, +1).$$

5. 复杂度

   • 每次查询与更新均为 $O(\log M)$，其中 $M$ 为值域大小（此处 $M\le5\times10^4$）。
   • 总时间 $O(n\log M)$，空间 $O(M)$。

C++

#include <bits/stdc++.h>
using namespace std;

// 树状数组大小
static const int MAXV = 50000;

struct Fenwick {
    vector<int> bit;
    int n;
    Fenwick(int _n): n(_n) { bit.assign(n+1, 0); }
    // 返回 x 的最低位
    int lowbit(int x) { return x & -x; }
    // 在下标 x 加上 Δ
    void update(int x, int delta) {
        for (; x <= n; x += lowbit(x))
            bit[x] += delta;
    }
    // 查询前缀 [1..x] 的和
    int query(int x) {
        int s = 0;
        for (; x > 0; x -= lowbit(x))
            s += bit[x];
        return s;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int threshold, n;
    cin >> threshold >> n;
    vector<int> record(n);
    for (int i = 0; i < n; i++) {
        cin >> record[i];
    }

    Fenwick fw(MAXV);
    long long ans = 0;
    // 倒序遍历
    for (int i = n - 1; i >= 0; i--) {
        int x = record[i];
        int limit = x - threshold - 1;
        if (limit >= 1) {
            ans += fw.query(limit);
        }
        fw.update(x, 1);
    }

    cout << ans << "\n";
    return 0;
}

Python

import sys
input = sys.stdin.readline

# 树状数组类
class Fenwick:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n+1)

    def lowbit(self, x):
        return x & -x

    def update(self, x, delta):
        while x <= self.n:
            self.bit[x] += delta
            x += self.lowbit(x)

    def query(self, x):
        s = 0
        while x > 0:
            s += self.bit[x]
            x -= self.lowbit(x)
        return s

def main():
    threshold = int(input())
    n = int(input())
    record = list(map(int, input().split()))

    fw = Fenwick(50000)
    ans = 0
    # 倒序遍历
    for x in reversed(record):
        limit = x - threshold - 1
        if limit >= 1:
            ans += fw.query(limit)
        fw.update(x, 1)
    print(ans)

if __name__ == "__main__":
    main()

Java

import java.io.*;
import java.util.*;

public class Main {
    static final int MAXV = 50000;
    static class Fenwick {
        int[] bit;
        int n;
        Fenwick(int n) {
            this.n = n;
            bit = new int[n+1];
        }
        // lowbit 函数
        int lowbit(int x) { return x & -x; }
        // 在 x 位置加 delta
        void update(int x, int delta) {
            for (; x <= n; x += lowbit(x)) {
                bit[x] += delta;
            }
        }
        // 查询 [1..x] 前缀和
        int query(int x) {
            int s = 0;
            for (; x > 0; x -= lowbit(x)) {
                s += bit[x];
            }
            return s;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int threshold = Integer.parseInt(br.readLine());
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Fenwick fw = new Fenwick(MAXV);

        long ans = 0;
        int[] record = new int[n];
        for (int i = 0; i < n; i++) {
            record[i] = Integer.parseInt(st.nextToken());
        }
        // 倒序遍历
        for (int i = n - 1; i >= 0; i--) {
            int x = record[i];
            int limit = x - threshold - 1;
            if (limit >= 1) {
                ans += fw.query(limit);
            }
            fw.update(x, 1);
        }
        System.out.println(ans);
    }
}

题目内容

在一家快速发展的互联网公司里，系统工程师小李正在开发一款高效的日志分析工具，旨在帮助运维团队更好地理解和优化语音合成系统的运行状况。为了提高工具的洞察力，他需要解决一个关键问题:如何通过分析一段时间内的合成请求的实时率 $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

输入

3
2
1 5

输出

0

说明

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

输出：$0$

解释：无逆序列

样例2

输入

3
2
5 1

输出

1

说明

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

输出：$1$

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

样例3

输入

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$