離散化

Discretization

用途:當資料太大時,無法開到那麼大的陣列時,可立用離散化只表示出相對關係,離散化是依數值大小重新排列,排列的結果為離散化之後的結果
舉例:

vector<int> a{2,345245,54345,653,25656253,0,34};

離散化:

vector<int> b{2,6,5,4,7,1,3}

1. 先複製一個陣列作為找尋ID用並排序

id=input;
sort(id.begin(),id.end());

2. 找尋ID的時候用lower_bound,其找到的索引值就是新排序後的編號

int getID(long long x){
  return lower_bound(id.begin(),id.end(),x)-id.begin()+1;
}

3. 重新賦予離散化之後的值

for(int i=0;i<n;i++) a[i]=getID(a[i]);

3. 開開心心做想要做的事

d794: 世界排名

#include <bits/stdc++.h>
#define MAXN 100005
using namespace std;
int bit[MAXN+1]={0};
vector<long long> input,id;

int getID(long long x){
  return lower_bound(id.begin(),id.end(),x)-id.begin()+1;
}

int main(){
  int n;
  while(cin >> n){
    input.clear();
    memset(bit,0,sizeof(bit));
    long long x;
    for(int i=1;i<=n;i++){
      cin >> x;
      input.push_back(x);
    }
    id=input;
    sort(id.begin(),id.end());
    for(int i=1;i<=n;i++){
      int target=input[i-1];
      int id=getID(target);
      for(int node=id;node<=MAXN;node+=node &-node) bit[node]++;
      int ans=0;
      for(int node=id-1;node>0;node-=node & -node) ans+=bit[node];
      cout << i-ans << '\n';
    }
  }

  return 0;
}