基于计数归并排序的O(n log n)三元排列顺序对计数算法需求

问题分析 #

我们需要统计三个由1~n构成的排列中，满足两个数的相对顺序在三个排列中完全一致的无序数对数量。即对于数对(i,j)，要么i在三个排列中都在j前面，要么j在三个排列中都在i前面。

算法思路 #

核心思路是将问题转化为二维偏序统计：

1. 预处理每个元素在三个排列中的位置：a_pos[x]（元素x在第一个排列中的索引）、b_pos[x]（元素x在第二个排列中的索引）、c_pos[x]（元素x在第三个排列中的索引）。
2. 将所有元素按第一个排列的顺序（即a_pos[x]从小到大）排序，这样排序后的元素列表中，前面的元素在第一个排列中一定在后面的元素前面。
3. 此时问题转化为：统计排序后的列表中，前面元素x满足b_pos[x] < b_pos[y]且c_pos[x] < c_pos[y]的数对(x,y)数量——这些数对就是在三个排列中x都在y前面的符合条件的数对，而所有符合条件的数对都包含在其中。
4. 使用分治法+树状数组实现二维偏序统计，时间复杂度为O(n log n)：
   • 分治递归处理子区间，统计子区间内部的符合条件数对。
   • 跨区间统计时，将左右子区间按b_pos排序，用双指针配合树状数组统计左区间中b_pos小于当前右区间元素、且c_pos也小于当前右区间元素的数量。

代码实现 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

struct Element {
    int b, c;
    Element(int b = 0, int c = 0) : b(b), c(c) {}
};

// 树状数组实现
class FenwickTree {
private:
    vector<int> tree;
public:
    FenwickTree(int size) : tree(size + 2, 0) {}
    
    void update(int idx, int delta) {
        idx++; // 避免c=0的情况
        while (idx < tree.size()) {
            tree[idx] += delta;
            idx += idx & -idx;
        }
    }
    
    ll query(int idx) {
        idx++; // 对应update的偏移
        ll res = 0;
        while (idx > 0) {
            res += tree[idx];
            idx -= idx & -idx;
        }
        return res;
    }
};

// 分治统计符合条件的数对数量
ll solve(vector<Element>& arr, int l, int r) {
    if (l >= r) return 0;
    int mid = (l + r) / 2;
    ll left = solve(arr, l, mid);
    ll right = solve(arr, mid + 1, r);
    ll cross = 0;
    
    // 将左右区间按b排序
    vector<Element> left_arr(arr.begin() + l, arr.begin() + mid + 1);
    vector<Element> right_arr(arr.begin() + mid + 1, arr.begin() + r + 1);
    sort(left_arr.begin(), left_arr.end(), [](const Element& a, const Element& b) {
        return a.b < b.b;
    });
    sort(right_arr.begin(), right_arr.end(), [](const Element& a, const Element& b) {
        return a.b < b.b;
    });
    
    // 统计跨区间的符合条件数对
    FenwickTree ft(r - l + 1);
    int i = 0;
    for (const auto& y : right_arr) {
        // 将所有b < y.b的左区间元素加入树状数组
        while (i < left_arr.size() && left_arr[i].b < y.b) {
            ft.update(left_arr[i].c, 1);
            i++;
        }
        // 查询c < y.c的元素数量
        cross += ft.query(y.c - 1);
    }
    
    // 合并左右区间（按b排序，方便上层递归）
    merge(left_arr.begin(), left_arr.end(), right_arr.begin(), right_arr.end(), arr.begin() + l);
    
    return left + right + cross;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    
    vector<int> a(n), b(n), c(n);
    vector<int> a_pos(n), b_pos(n), c_pos(n);
    
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i]--; // 转为0-based
        a_pos[a[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        b[i]--;
        b_pos[b[i]] = i;
    }
    for (int i = 0; i < n; i++) {
        cin >> c[i];
        c[i]--;
        c_pos[c[i]] = i;
    }
    
    // 按a_pos排序，生成元素列表
    vector<Element> arr(n);
    for (int x = 0; x < n; x++) {
        arr[a_pos[x]] = Element(b_pos[x], c_pos[x]);
    }
    
    ll ans = solve(arr, 0, n - 1);
    cout << ans << "\n";
    
    return 0;
}

代码说明 #

1. 树状数组：用于高效统计前缀和，支持单点更新和区间查询，时间复杂度O(log n)。
2. 分治函数：递归处理子区间，合并时按b_pos排序，用双指针将左区间中b_pos小于当前右区间元素的元素加入树状数组，再查询c_pos小于当前元素的数量，得到跨区间的符合条件数对。
3. 预处理：将输入的排列转为0-based索引，记录每个元素在三个排列中的位置，然后按第一个排列的顺序生成元素列表。

内容的提问来源于stack exchange，提问作者Leon