离散化

InfiniteHorizon · 2021-11-05 15:12:26 · 算法·理论

问题：给定一个序列，求其逆序对个数。

这题很显然要用树状数组，但是在元素规模过大的情况下（如到了 10^{12}），树状数组会存不下。

我们考虑如下一个序列：

1 53 23 5464543 34

它的逆序对数量应该和下面这个序列是一样的：

1 4 2 5 3

可见，数字的大小与逆序对的数量无关。由此我们引入了离散化这个方法。

离散化的方法

• 记录数据的编号，对数据排序。
• 将原数组排序，然后去重，可使用algorithm中的unique函数。
• 最开始记录下的数据编号，就是数据离散化后的结果。

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 100010;

int num[maxn];
int tp[maxn];
map<int,int>mp;
int id[maxn];
int real[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
        tp[i]=num[i];
    }
    sort(tp,tp+n);
    int m=unique(tp,tp+n)-tp;
    for(int i=0;i<m;i++){
        mp[tp[i]]=i+1;
        real[i+1]=tp[i];
    }
    for(int i=0;i<n;i++){
        id[i]=mp[num[i]];
        cout<<id[i]<<" ";
    }
    return 0;
}