逆序对——权值树状数组+离散化

整理日期按学习顺序编排，不代表原始发表时间。实际整理于 2026-10-23。

难度为阅读建议，可从 ACM 学习索引 按阶段阅读。

• 给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。每个数字不超过1e9。

int n, m;
int a[N];
int tr[N];
vector<int>lan;
int lowbit(int x){
	return x&(-x);
}
void discrete()
{
    sort(lan.begin(), lan.end());   //排序
    lan.erase(unique(lan.begin(), lan.end()), lan.end());   //去重
}

//查询
int find(int x)
{
    return lower_bound(lan.begin(), lan.end(), x)-lan.begin()+1;  //返回所查询的数据的下标
}
void add(int x,int c){
	for(int i=x;i<=n;i+=lowbit(i))tr[i]+=c;
}

int query(int x){
	int res=0;
	for(int i=x;i;i-=lowbit(i))res+=tr[i];
	return res;
}
void solve(){
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	
	for(int i=1;i<=n;i++)lan.push_back(a[i]);
	discrete();
	int mx=lan.size();
	ll cnt=0;
	for(int i=1;i<=n;i++){
		cnt+=query(mx)-query(find(a[i]));
		add(find(a[i]),1);
	}
	cout<<cnt<<endl;
}