解题思路

1. 排序映射
   将所有元素与其原始下标组成对 $(a_i, i)$，按照值 $a_i$ 升序排序，得到一组有序对列表 $\text{ord}$。
2. 统计跳转
   从 $\text{ord}[1]$（最小值）开始，每一步跳转都对应相邻两个有序对之间的下标变化：
   • 若 $\text{ord}[k].\text{idx}$ < $\text{ord}[k+1].\text{idx}$，则为正向传送；
   • 否则为逆向传送。
3. 复杂度
   • 排序：$O(n\log n)$
   • 一次线性扫描统计：$O(n)$
   • 总体对每组数据 $O(n\log n)$，多组数据 $\sum n\le 2\times10^5$ 可接受。

复杂度分析

• 时间复杂度：每组 $O(n\log n)$，总和 $\sum n\le2\times10^5$。
• 空间复杂度：$O(n)$ 用于存储数值-下标对。

代码

Python

import sys
input = sys.stdin.readline

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        arr = list(map(int, input().split()))
        # 构造(值, 下标)对并排序
        p = sorted((v, i) for i, v in enumerate(arr, start=1))
        fwd = back = 0
        # 遍历相邻对，统计索引变化
        for k in range(1, n):
            if p[k][1] > p[k-1][1]:
                fwd += 1
            else:
                back += 1
        print(fwd, back)

if __name__ == "__main__":
    solve()

Java

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            String[] ss = br.readLine().split(" ");
            // 存放(值, 下标)
            int[][] p = new int[n][2];
            for (int i = 0; i < n; i++) {
                p[i][0] = Integer.parseInt(ss[i]);
                p[i][1] = i + 1;
            }
            // 按值升序
            Arrays.sort(p, Comparator.comparingInt(a -> a[0]));
            int fwd = 0, back = 0;
            for (int i = 1; i < n; i++) {
                if (p[i][1] > p[i-1][1]) fwd++;
                else back++;
            }
            System.out.println(fwd + " " + back);
        }
    }
}

C++

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

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

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<pair<int,int>> p(n);
        for (int i = 0; i < n; i++) {
            cin >> p[i].first;
            p[i].second = i + 1;  // 记录原始下标
        }
        // 按值排序
        sort(p.begin(), p.end());
        int fwd = 0, back = 0;
        for (int i = 1; i < n; i++) {
            if (p[i].second > p[i-1].second) fwd++;
            else back++;
        }
        cout << fwd << " " << back << "\n";
    }
    return 0;
}

题目内容

小美有一个长度为 $n$ 的数组 $a$，数组中所有元素的值互不相同，且数组的下标从 $1$ 开始。

她计划对这个数组中的每个元素进行“数数”，她会从数组中数值最小的元素的索引开始。每次数数时，她会选择第一个值大于当前位置元素值的元素，直到所有元素都被数过为止。

例如，假设数组 $a = [3,1,5]$，小美一开始选择的是索引 $i=2($此时 $a_2=1)$，她会接着找到第一个比 $1$ 大的元素 $3($索引 $i= 1)$，然后再找到第一个比 $3$ 大的元素 $5 ($索引 $i= 3)$。整个数数过程为：$a_2$ -> $a_1$ -> $a_3$。

在这一过程中，如果小美的操作是从较小索引移动到较大索引（即$j>i$），我们称之为正向传送；如果是从较大索引移动到较小索引（即 $j<i$），则称之为逆向传送。

你的任务是帮助小美计算她在整个数数过程中需要进行多少次正向传送和多少次逆向传送。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 $T(1 \leq T\leq 1000)$，代表数据组数，每组测试数据描述如下：

对于每一组测试数据：

第一行一个整数 $n(1 \leq n \leq 2* 10^5)$，表示数组长度。

第二行 $n$ 个整数，第 $i$ 个数为 $a_i(1 \leq a_i \leq 10^9)$，表示数组元素。

单个测试文件 $\sum n ≤ 2* 10^5$。

输出描述

共 $T$ 行，每行两个整数，分别表示正向传送和逆向传送的次数，以空格隔开。

示例1

输入

2
3
1 2 3
3
3 2 1

输出

2 0
0 2