题解 | #数组中的逆序对#
数组中的逆序对
https://www.nowcoder.com/practice/96bd6684e04a44eb80e6a68efc0ec6c5
和大家讲解一下树状数组求逆序对的方法
例如：
tree：0 0 0 0 0
x=4:
tree: 0 0 0 0 1
然后对x进行查询read(x)，可以得到x之前插入了多少个数，因为x之前插入的数都比x小，所以用当前插入的数的总数i减去read(x)可以得到当前插入的i个数中有多少个比x大，即x有多个逆序对。
离散化： 如果插入的x很大，每次对x进行查询，时间用的多，且tree的空间不够。这时候需要进行离散化。具体做法是每次输入一个数的同时记录下该数输入的顺序是多少。然后对输入的数进行排序。
tree：0 0 0 0 0
x=4:
tree: 0 0 0 0 1
然后对x进行查询read(x)，可以得到x之前插入了多少个数，因为x之前插入的数都比x小，所以用当前插入的数的总数i减去read(x)可以得到当前插入的i个数中有多少个比x大，即x有多个逆序对。
离散化： 如果插入的x很大，每次对x进行查询，时间用的多，且tree的空间不够。这时候需要进行离散化。具体做法是每次输入一个数的同时记录下该数输入的顺序是多少。然后对输入的数进行排序。
#include<bits/stdc++.h>
#define ll long long
#define lowbit(x) (x)&(-x)
const int maxn=1e5;
using namespace std;
ll n,tree[maxn];
struct node
{
int val;
int id;
}arr[maxn];
bool cmp(node a,node b)
{
return a.val<b.val;
}
void update(int k,int a)
{
while(k<=n)
{
tree[k]+=a;
k+=lowbit(k);
}
}
ll read(ll k)
{
ll sum=0;
while(k)
{
sum+=tree[k];
k-=lowbit(k);
}
return sum;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>arr[i].val;
arr[i].id=i;
}
sort(arr+1,arr+n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i++)
{
update(arr[i].id,1);
ans+=(i-read(arr[i].id));
//cout<<arr[i].id<<" ";
}
cout<<ans<<endl;
return 0;
}
