离散化：大坐标映射

算法理解

我们只关心数据间的相对顺序，而非数值本身时，先排序、去重，再用二分查找取得排名。这样 10^9、负数等坐标就能交给只能使用连续下标的数据结构。

• 复杂度：预处理 O(n log n)，每个映射 O(log n)。
• 注意：树状数组通常用 1 基下标，因此排名结果要 +1。

模板代码

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define int long long
using pii=pair<int,int>;
const int mod=1e9+7;
//const int maxn=1e6+5;
#define lowbit(x) (x&(-x))
#define vc vector<int>
int get_id(int x,const vector<int>&a)
{
	return lower_bound(a.begin()+1,a.end(),x)-a.begin();
}
void solve()
{
	int n;
	cin>>n;
	vector<int>b(n+1);
	vector<int>a(n+1);
	for (int i=1;i<=n;i++)
	{
		cin>>a[i];
		b[i]=a[i];
	}
	sort(a.begin()+1,a.end());
	a.erase(unique(a.begin() + 1, a.end()), a.end());
	vector<int>ans;
	for (int i=1;i<=n;i++)
	{
		int x=get_id(b[i],a);
		ans.push_back(x);
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int t=1;
//	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}