彩球排序｜逆序对去重

第六题 - Sorting Color Balls

题目跳转：彩球排序。

一道逆序对的题目，因为我懒的使用归并排序来做，所以我用了 树状数组 + map 的方式，荣获运行时长 44.9s 的好成绩。其实这道题应该比第五题简单，Based on my opinion。

一道普普通通的逆序对的题目，在计算逆序对的时候去除相同颜色的逆序对就可以了，类似一道模板题。我用了两个树状数组分别来计算每个数字出现的次数和每个颜色出现的次数。

2024.08.19 更新：优化了程序常数，在 $1000$ 毫米内可以执行完所有的测试点。

本题的 AC 代码如下，时间复杂度约为 $O(N \log_2 N)$：

#include <iostream>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n, c[N], x[N];
int cnt[N], tot[N];
unordered_map<int, int> cnt2[N];

// 记录某一个数字出现的次数。
void add_n(int x) {
    while (x <= n) {
        cnt[x] += 1;
        x += x & (-x);
    }
}

// 记录某一个颜色出现的次数。
void add_c(int color, int x) {
    while (x <= n) {
        cnt2[color][x] += 1;
        x += x & (-x);
    }
}

// 查询某一个数字出现的次数。
int query_n(int x) {
    int ans = 0;
    while (x) {
        ans += cnt[x];
        x -= x & (-x);
    }
    return ans;
}

// 查询某一个颜色出现的次数。
int query_c(int color, int x) {
    int ans = 0;
    while (x) {
        if (cnt2[color].count(x)) {
            ans += cnt2[color][x];
        }
        x -= x & (-x);
    }
    return ans;
}

signed main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
    for (int j = 1; j <= n; j++) scanf("%d", &x[j]);
    int result = 0;
    for (int i = 1; i <= n; i++) {
        // 减去相同颜色出现的次数即可。
        result += (i - 1) - tot[c[i]] - query_n(x[i]) + query_c(c[i], x[i]);
        tot[c[i]] += 1;
        add_c(c[i], x[i]); add_n(x[i]);
    }
    cout << result << endl;
    return 0;
}

---

以下是之前的代码，常数比较大：

#include <iostream>
#include <vector>
#include <unordered_map>
#define int long long
using namespace std;

const int N = 3e5 + 5;
int n, c[N], x[N];
int cnt[N], tot[N];
unordered_map<int, int> cnt2[N];

// 记录某一个数字出现的次数。
void add_n(int x){
    while(x <= n){
        cnt[x] += 1;
        x += x & (-x);
    }
}

// 记录某一个颜色出现的次数。
void add_c(int x, int c){
    while(x <= n){
        cnt2[x][c] += 1;
        x += x & (-x);
    }
}

// 查询某一个数字出现的次数。
int query_n(int x){
    int ans = 0;
    while(x){
        ans += cnt[x];
        x -= x & (-x);
    }
    return ans;
}

// 查询某一个颜色出现的次数。
int query_c(int x, int c){
    int ans = 0;
    while(x){
        ans += cnt2[x][c];
        x -= x & (-x);
    }
    return ans;
}

signed main(){
    cin >> n;
    for (int i=1; i<=n; i++) cin >> c[i];
    for (int j=1; j<=n; j++) cin >> x[j];
    int result = 0;
    for (int i=1; i<=n; i++){
        // 减去相同颜色出现的次数即可。
        result += (i - 1) - tot[c[i]] - query_n(x[i]) + query_c(x[i], c[i]);
        tot[c[i]] += 1;
        add_c(x[i], c[i]); add_n(x[i]);
    }
    cout << result << endl;
	return 0;
}