数组离散化

1
// 离散化
2
sort(begin(v_sorted), end(v_sorted));
3
v_sorted.erase(unique(begin(v_sorted), end(v_sorted)), end(v_sorted));
4

5
// 映射离散化索引（1-based index）
6
for (int i = 0; i < (int)v_sorted.size(); i++) {
7
  index_map[v_sorted[i]] = i + 1;
8
}

1
vector<ll> arr(n + 1);
2
vector<ll> sorted_arr(n + 1);
3

4
for (int i = 1; i <= n; i++) {
5
  cin >> arr[i];
6
  sorted_arr[i] = arr[i];  // 复制数组用于排序
7
}
8

9
sort(next(begin(sorted_arr)), end(sorted_arr)); // 仅排序副本
10
auto f = [&](ll x) {
11
  return lower_bound(next(begin(sorted_arr)), end(sorted_arr), x) - sorted_arr.begin();
12
};

1
#define all(x) x.begin(), x.end()
2
#define unq_all(x) x.erase(unique(all(x)), x.end())
3
#define sort_all(x) sort(all(x))
4

5
vector<ll> g = v;
6
sort_all(v);
7
unq_all(v);
8
auto get_id = [&](ll x) {
9
  return lower_bound(g.begin(), g.end(), x) - g.begin() + 1; // 下标从1开始
10
};