题目理解

我们有一个数组 a，长度 N，元素是 1 到 K 的整数。

我们还有一个目标排列 p，初始是 [1, 2, ..., K]。它定义了排序顺序：最终数组中的数要按 p 的顺序排列。

朋友的排序算法用相邻交换，操作次数最少（等于逆序对数）。

我们要进行 Q 次操作，每次交换 p 中相邻的两个数，然后计算用这个 p 排序需要多少次交换。

关键点

• 最小交换次数 = 原数组关于目标排列的逆序对数
• 目标排列 p 定义了数的“大小”关系：在 p 中先出现的数更“小”
• 每次只交换 p 中相邻的两个数

思路

设目标排列 p 中，数 x 的位置是 pos[x]。

那么原数组 a 关于 p 的逆序对定义是：

• 对于 i < j，如果 pos[a[i]] > pos[a[j]]，则 (i, j) 是一个逆序对

交换的影响

假设我们交换 p 中位置 j 和 j+1 的两个数 u 和 v。

交换前：u 在 v 前面
交换后：v 在 u 前面

逆序对数的变化：

• 原来 u 在 v 前面不是逆序，交换后变成逆序，数量是 count[u][v]（原数组中 u 在 v 前面的次数）
• 原来 v 在 u 前面是逆序，交换后不是逆序了，数量是 count[v][u]（原数组中 v 在 u 前面的次数）

所以变化量 = count[v][u] - count[u][v]

算法步骤

1. 预处理每个数在原数组中的位置列表
2. 计算初始逆序对数（用树状数组）
3. 对于每次交换：
   • 计算 count[u][v] 和 count[v][u]
   • 更新逆序对数
   • 交换 p 中的两个数
   • 输出当前逆序对数

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i];
        a[i]--; // 转为0-based
    }
    
    // 初始目标排列
    vector<int> p(K);
    for (int i = 0; i < K; i++) p[i] = i;
    
    // 记录每个数的位置
    vector<vector<int>> pos(K);
    for (int i = 0; i < N; i++) {
        pos[a[i]].push_back(i);
    }
    
    // 计算初始逆序对数
    ll inv = 0;
    vector<int> bit(K + 1, 0);
    
    // 树状数组更新
    auto update = [&](int i, int delta) {
        for (i++; i <= K; i += i & -i) bit[i] += delta;
    };
    
    // 树状数组查询
    auto query = [&](int i) {
        int sum = 0;
        for (i++; i > 0; i -= i & -i) sum += bit[i];
        return sum;
    };
    
    // 从后往前计算逆序对
    for (int i = N - 1; i >= 0; i--) {
        inv += query(a[i] - 1);
        update(a[i], 1);
    }
    
    // 处理每次交换
    while (Q--) {
        int j;
        cin >> j;
        j--; // 转为0-based
        
        int u = p[j], v = p[j + 1];
        
        // 计算count[u][v]和count[v][u]
        ll cnt_uv = 0, cnt_vu = 0;
        int i1 = 0, i2 = 0;
        const auto& pu = pos[u];
        const auto& pv = pos[v];
        
        // 双指针统计
        while (i1 < pu.size() && i2 < pv.size()) {
            if (pu[i1] < pv[i2]) {
                cnt_uv++;
                i1++;
            } else {
                cnt_vu++;
                i2++;
            }
        }
        cnt_uv += pu.size() - i1;
        cnt_vu += pv.size() - i2;
        
        // 更新逆序对数
        inv += cnt_uv - cnt_vu;
        
        // 交换p中的两个数
        swap(p[j], p[j + 1]);
        
        cout << inv << "\n";
    }
    
    return 0;
}

样例验证

输入：

5 4 3
1 4 2 1 2
3
2
1

输出：

4
2
2

与题目一致。

复杂度分析

• 初始逆序对计算：O(N log K)
• 每次查询：O(位置列表长度之和)
• 总复杂度可以接受

这个解法利用了逆序对的性质和相邻交换的局部性，能够高效处理大规模数据。