逆序对

题目

P1908
备注：SSLOJ带多测，n<=250000，值小于100

---

解析

本题是裸的逆序对，关键在于怎么做
显然可以使用归并排序或树状数组+离散化
奉上四份代码

code(洛谷):

树状数组

#include<cstdio>
#include<algorithm>
#define int long long
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
inline void write(int x)
{
	int F[20];
	int tmp=x>0?x:-x;
	if(x<0)putchar('-');
	int cnt=0;
	while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
	while(cnt>0)putchar(F[--cnt]);
	if(x==0)putchar('0');
}
struct q{int id,val;}a[500010];
bool cmp1(q x,q y){return x.val<y.val;}
bool cmp2(q x,q y){return x.id<y.id;}
int n,tree[500010],ans=0,la=-1;
inline void add(int x,int k){for(;x<=n;x+=(x&-x))tree[x]+=k;}
inline int sum(int x){int q=0;for(;x;x^=(x&-x))q+=tree[x];return q;}
signed main()
{
	n=read();
	for(int i=1;i<=n;++i)a[i].val=read(),a[i].id=i;
	sort(a+1,a+n+1,cmp1);
	for(int i=1;i<=n;++i)
	{
		if(a[i].val!=la)la=a[i].val,a[i].val=a[i-1].val+1;
		else a[i].val=a[i-1].val;
	}
	sort(a+1,a+n+1,cmp2);
	for(int i=1;i<=n;++i)add(a[i].val,1),ans+=i-sum(a[i].val);
	write(ans);
	return 0;
}

---

归并排序

#include<cstdio>
#define rr register int
#define int long long
using namespace std;
int n,a[500010],b[500010],ans;
inline void gb(int l,int r)
{
	if(l==r)return;
	rr mid=l+r>>1,p=l,j=mid+1,i=l;
	gb(l,mid),gb(j,r);
	while(l<=mid&&j<=r){if(a[j]<a[l])ans+=mid+1-l;b[p++]=(a[j]>=a[l])?a[l++]:a[j++];}
	while(l<=mid)b[p++]=a[l++];
	while(j<=r)b[p++]=a[j++];
	for(;i<=r;++i)a[i]=b[i];
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;++i)scanf("%lld",&a[i]);
	gb(1,n);
	printf("%lld",ans);
	return 0;
}

---

code(SSLOJ):

树状数组

#include<cstdio>
#define int long long
using namespace std;
inline bool idigit(char x){return (x<'0'|x>'9')?0:1;}
inline int read()
{
	int num=0,f=1;
	char c=0;
	while(!idigit(c=getchar())){if(c=='-')f=-1;}
	while(idigit(c))num=(num<<1)+(num<<3)+(c&15),c=getchar();
	return num*f;
}
inline void write(int x)
{
	int F[20];
	int tmp=x>0?x:-x;
	if(x<0)putchar('-');
	int cnt=0;
	while(tmp>0){F[cnt++]=tmp%10+'0';tmp/=10;}
	while(cnt>0)putchar(F[--cnt]);
	if(x==0)putchar('0');
	putchar('\n');
}
int n,tree[110],ans;
inline void add(int x){for(;x<=100;x+=(x&-x))++tree[x];}
inline int sum(int x){int q=0;for(;x;x^=(x&-x))q+=tree[x];return q;}
signed main()
{
	while(~scanf("%lld",&n)&&n)
	{
		ans=0;
		for(int i=1;i<=100;++i)tree[i]=0;
		for(int i=1;i<=n;++i)read(),ans=(ans+sum(tree[0]=read()))%1000000,add(tree[0]);
		write(((((n*(n-1))>>1)-ans)%1000000+1000000)%1000000);
	}
	return 0;
}

---

归并排序

#include<cstdio>
#define rr register int
#define int long long
using namespace std;
int n,a[250010],b[250010],ans;
inline void gb(int l,int r)
{
	if(l==r)return;
	rr mid=l+r>>1,p=l,j=mid+1,i=l;
	gb(l,mid),gb(j,r);
	while(l<=mid&&j<=r){if(a[j]<a[l])(ans+=mid+1-l)%=1000000;b[p++]=(a[j]>=a[l])?a[l++]:a[j++];}
	while(l<=mid)b[p++]=a[l++];
	while(j<=r)b[p++]=a[j++];
	for(;i<=r;++i)a[i]=b[i];
}
signed main()
{
	while(~scanf("%lld",&n)&&n)
	{
		ans=0;
		for(int i=1;i<=n;++i)scanf("%lld%lld",&a[0],&a[i]);
		gb(1,n);
		printf("%lld\n",ans);
	}
	return 0;
}