逆序数(也叫逆序对)
在一个排列中,如果一对数的前后位置与大小顺序相反,即前面的数大于后面的数,那么它们就称为一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
【1】无重复的数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAX 500000
typedef long long ll;
ll c[MAX];
ll n;
struct record
{
ll val, pos;//记录数值 和 位置
}num[MAX];
bool cmp(record a,record b)
{
return a.val > b.val;
}
ll lowbit(ll x)
{
return x&(-x);
}
ll sum(ll x)//求和
{
ll s = ;
while(x > )
{
s += c[x];
x -= lowbit(x);
}
return s;
}
void update(ll x)//更新
{
while(x <= n)
{
c[x] += ;
x += lowbit(x);
}
}
int main()
{
ll i, j;
ll x,y;
ll ans;//统计总数目
while(~scanf("%lld%lld%lld", &n,&x,&y))
{
memset(c, , sizeof(c));//初始化
for(i = ;i < n; i++)
{
scanf("%lld", &num[i].val);
num[i].pos = i + ;
}
sort(num, num+n, cmp);
ans = ;
for(i = ;i < n; ++i)//每一次插入当前最大值
{
update(num[i].pos);
ans += sum(num[i].pos-);//统计前面有多少个数
}
ll anss=ans*min(x,y);
printf("%lld\n",anss);
}
}
【2】有重复的数
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
#define MAX 500000
typedef long long ll;
ll c[MAX];
ll n;
struct record
{
ll val, pos;//记录数值 和 位置
}num[MAX];
bool cmp(record a, record b)
{
if(a.val != b.val)
return a.val > b.val;
else
return a.pos > b.pos;
}
ll lowbit(ll x)
{
return x&(-x);
}
ll sum(ll x)//求和
{
ll s = ;
while(x > )
{
s += c[x];
x -= lowbit(x);
}
return s;
}
void update(ll x)//更新
{
while(x <= n)
{
c[x] += ;
x += lowbit(x);
}
}
int main()
{
ll i, j;
ll x,y;
ll ans;//统计总数目
while(~scanf("%lld%lld%lld", &n,&x,&y))
{
memset(c, , sizeof(c));//初始化
for(i = ;i < n; i++)
{
scanf("%lld", &num[i].val);
num[i].pos = i + ;
}
sort(num, num+n, cmp);
ans = ;
for(i = ;i < n; ++i)//每一次插入当前最大值
{
update(num[i].pos);
ans += sum(num[i].pos-);//统计前面有多少个数
}
ll anss=ans*min(x,y);
printf("%lld\n",anss);
}
}
【3】树状数组求逆序数(离散化)当maxn较大时,直接开数组显然是不行了,这是的解决办法就是离散化
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll c[],s[],a[],b[];
ll n;
ll x,y;
int lowbit(int x)
{
return x&(-x);
}
void update(ll i,int x)
{
while(i<=n)
{
c[i]+=x;
i+=lowbit(i);
}
}
ll Sum(ll x)
{
ll sum=;
while(x>)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
int main()
{
while(~scanf("%lld%lld%lld",&n,&x,&y))
{
memset(c,,sizeof(c));
ll ans=;
int m;
for(int i=;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]+=;
b[i]=a[i];
}
sort(b+,b+n+);
int len=unique(b+,b+n+)-b-;
for(int i=;i<=n;i++)
{
a[i]=lower_bound(b+,b+len+,a[i])-b;
update(a[i],);
ans+=(ll)i-Sum(a[i]);
}
ll ma=min(x,y);
printf("%lld\n",ans*ma);
}
}