AcWing 788. 逆序对的数量--归并排序和离散化+树状数组
原题链接
简单
作者:
记_得
,
2021-12-16 18:07:56
,
所有人可见
,
阅读 281
归并排序做法
#include<iostream>
using namespace std;
const int N = 1e6+10;
typedef long long LL;
int n;
int q[N],temp[N];
LL merge(int l,int r)
{
if(l==r) return 0;
int mid=l+r>>1;
LL res=merge(l,mid)+merge(mid+1,r);
int k=0,i=l,j=mid+1;
while(i<=mid&&j<=r)
{
if(q[i]<=q[j]) temp[k++]=q[i++];
else
{
temp[k++]=q[j++];
res+=mid-i+1;
}
}
while(i<=mid) temp[k++]=q[i++];
while(j<=r) temp[k++]=q[j++];
for(int i=l,j=0;i<=r;i++,j++) q[i]=temp[j];
return res;
}
int main()
{
cin >> n;
for(int i=0;i<n;i++) cin >> q[i];
cout << merge(0,n-1);
return 0;
}
树状数组做法
因为a[i]的值最大为1e9所以需要离散化一下
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
typedef long long LL;
int n;
int a[N],tr[N];
vector<int> alls;
int lsh(int x) //离散化
{
return lower_bound(alls.begin(),alls.end(),x)-alls.begin()+1;
}
int lowbit(int x)
{
return x&-x;
}
void add(int x,int c)
{
for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}
int sum(int x)
{
int res=0;
for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];
return res;
}
int main()
{
cin >> n;
for(int i=1;i<=n;i++)
{
cin >> a[i];
alls.push_back(a[i]);
}
sort(alls.begin(),alls.end()); //离散化
alls.erase(unique(alls.begin(),alls.end()),alls.end());
LL res=0;
for(int i=1;i<=n;i++)
{
int id=lsh(a[i]);
// res+=sum(id-1); //需要倒着枚举
res+=sum(n)-sum(id);
add(id,1);
}
cout << res << endl;
return 0;
}