求逆序对的常用方法(树状数组,归并排序,线段树)
1.树状数组
首先对数组b[i]进行离散化处理,按价值从大到小排序得到位置数组a[i],排序后用树状数组维护,将a[i](数从大到小排序后的位置)依次加入树状数组,然后依次查询a[i]位置前面一位的数,答案相加即为逆序对个数。
例:洛谷P1908 逆序对
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize ("unroll-loops")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#define INF 0x3f3f3f3f
#define lowbit(a) ((a)&-(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,c[500005],a[500005],b[500005];
void update(int x,int y,int n)
{
for(int i=x;i<=n;i+=lowbit(i))
{
c[i]=c[i]+y;
}
}
ll getsum(int x)
{
ll ans=0;
for(int i=x;i;i-=lowbit(i))
{
ans+=c[i];
}
return ans;
}
int cmp(int s1,int s2)
{
if(b[s1]==b[s2])
return s1>s2;
else
return b[s1]>b[s2];
}
int main()
{
ll ans=0;
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d",&b[i]);
a[i]=i;
}
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++)
{
update(a[i],1,n);
ans+=getsum(a[i]-1);
}
cout<<ans<<endl;
}
2.归并排序
如归并过程中左边大于右边,则逆序对个数加一;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize ("unroll-loops")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<math.h>
#include<string>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#define INF 0x3f3f3f3f
#define lowbit(a) ((a)&-(a))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
int n,a[500010],c[500010];
long long ans;
void msort(int b,int e)//归并排序
{
if(b==e)
return;
int mid=(b+e)/2,i=b,j=mid+1,k=b;
msort(b,mid),msort(mid+1,e);
while(i<=mid&&j<=e)
if(a[i]<=a[j])
c[k++]=a[i++];
else
c[k++]=a[j++],ans+=mid-i+1;//统计答案
while(i<=mid)
c[k++]=a[i++];
while(j<=e)
c[k++]=a[j++];
for(int l=b;l<=e;l++)
a[l]=c[l];
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
msort(1,n);
printf("%lld",ans);
return 0;
}
3.线段树
与树状数组原理类似,进行单点修改,查询区间和;