51Nod 1019 逆序数(树状数组/归并)

题目链接

看了很多博客都说把数据离散化。我也不是很懂

树状数组基本的做法浪费空间。存储不下

我感觉所谓的离散化就是根据数据的大小排序，然后根据下标重新给数组一个顺序

举个例子把：

1 5 6 3  num

1 2 3 4 id

根据num排序之后

1 3 5 6 num

1 4 2 3 id

因为现在id就代表数据的位置

为id附上编号

1 3 5 6 num

1 4 2 3 id

1 2 3 4 编号

现在fz[1]=1  fz[4]=2  fz[2]=3  fz[3]=4;

把fz数组按照顺序输出：1 3 4 2 这样的新顺序和原顺序保持一致

然后把这个数组用树状数组就行了

#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdio>
using namespace std;
static int t[50001]={0};
int n;
typedef struct node{
	int num,id;
}node;
node no[50001];
bool cmp(node n1,node n2){
	return n1.num<n2.num;
}
int add(int x,int num){
	while(x<=n){
		t[x]+=num;
		x+=x&-x;
	}
}
int sum(int x){
	int sum=0;
	while(x){
		sum+=t[x];
		x-=x&-x;
	}
	return sum;
}
int main(){
	cin>>n;
	int cnt=0;
	for(int i=1;i<=n;i++){
		int num;
		scanf("%d",&no[i].num);
		no[i].id=i;
	}
	sort(no+1,no+1+n,cmp);
	int fz[50001];
	for(int i=1;i<=n;i++) fz[no[i].id]=i;
	for(int i=1;i<=n;i++){
		add(fz[i],1);
		//cout<<fz[i]<<" "<<sum(fz[i])<<endl;
		cnt+=i-sum(fz[i]);
	}
	cout<<cnt;
	return 0;
}

归并排序：

之前蓝桥杯做过，只不过是求每个位置的逆序数，最后除以2就好

#include<iostream>
using namespace std;
typedef struct S{
	int num,len;
}S;
S a[100005],c[100005];
void merge(S a[],int first,int last){
	int temp=first,p=first;
	int mid=(first+last)/2;
	int q=mid+1;
	while(p<=mid&&q<=last){
		if(a[p].num>a[q].num){
			a[q].len+=mid+1-p;
			c[temp++]=a[q++];
		}
		else{
			a[p].len+=q-mid-1;
			c[temp++]=a[p++];	
		}
	}
	while(q<=last){
		c[temp++]=a[q++];
	}
	q--;
	while(p<=mid){
		a[p].len+=q-mid;
		c[temp++]=a[p++];
	}
	for(int i=first;i<=last;i++)
	   a[i]=c[i];
}
void sort(S a[],int first,int last){
	if(first==last) return ;
	int mid=(first+last)/2;
	sort(a,first,mid);
	sort(a,mid+1,last);
	merge(a,first,last);
}
int main(){
	int n; cin>>n;
	for(int i=0;i<n;i++)  {
		cin>>a[i].num;
		a[i].len=0;
	}
	sort(a,0,n-1);
	long long sum=0;
	for(int i=0;i<n;i++) {
	   long long s=a[i].len;
	   sum+=s;
	} 
	cout<<sum/2;
	return 0;
}