刷题记录:NC208813求逆序数

传送门:牛客

题目描述:

在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为
一个逆序。一个排列中逆序的总数就称为这个排列的逆序数。
比如一个元素个数为4的数列，其元素为2，4，3，1，则(2,1)，(4,3)，(4,1)，(3,1)是逆序，逆序数是4
现在求给定数列的逆序数
输入:
4
2 4 3 1
输出:
4
1
2
3
4
5
6
7
8
9

主要思路:

这道题主义是去求逆序对的一道题,首先这道题暴力也是可以很轻松的解决的,因此难度是不高的,暴力代码如下

#include 
int main(){
    int n, cnt = 0;
    scanf("%d", &n);
    int a[n];
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    for(int i = 0; i < n - 1; i++){
        for(int j = i + 1; j < n; j++) {
            if(a[j] < a[i])cnt++;
        }
    }
    printf("%d", cnt);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

但是显然这个代码是可以继续优化的,请移步如下逆序对,你会发现之前写的代码不出所料的Tie掉了,然后你感到很郁闷.然后就会发现了用归并排序来优化这道题

如果你完全不会归并排序,可以移步百度进一步学习,如果你之前有所了解,可以移步这里去稍微复习一遍,或许可以唤醒你的记忆

然后我们举个栗子:
比如
5 5 6(在左边) 和1 1 9(在右边)这两个序列(使用归并排序进行二分了)
然后我们使用归并排序进行合并时就会发现1碰到当前的5是比5小的,也就是此时的1是合并到新序列中去的,而此时左边剩下3个数字,也就是此时对于1来说存在3个逆序对,同理,右边的第二个1也有3个逆序对,而9就没有逆序对了

也就是说当我们去执行归并排序中的这个代码时:

	while(i<=mid&&j<=r) {
		if(a[i]<a[j]) {//将两个组合中的较大的值放入新的组合的前列
			fuzhu[k++]=a[i++];
		}else {
			fuzhu[k++]=a[j++];
		}
	}
1
2
3
4
5
6
7

当我们发现a[i]>a[j]时就会产生逆序对了,而此时产生的逆序对的数量恰好是左边序列中剩余的数字的个数(即mid-i+1),因为只有右边进行合并的数字比左边的任何一个数字都要小时才会合并到新的序列中的,至此我们就得到了使用归并排序来求逆序列的方法了

下面是具体代码(只比归并排序多了一句代码):

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define maxn 1000000
int ans=0;
int a[3000],fuzhu[3000];
void qsort(int l,int r) {
	if(l>=r) return ;
	int mid=(l+r)>>1;
	qsort(l,mid);qsort(mid+1,r);
	int k=l,i=l,j=mid+1;
	while(i<=mid&&j<=r) {
		if(a[i]<=a[j]) fuzhu[k++]=a[i++];
		else {
			fuzhu[k++]=a[j++];
			ans+=(mid-i+1);
		}
	}
	while(i<=mid) fuzhu[k++]=a[i++];
	while(j<=r) fuzhu[k++]=a[j++];
	for(int ii=l;ii<=r;ii++) a[ii]=fuzhu[ii];
}
int main() {
	int n;n=read();
	for(int i=1;i<=n;i++) a[i]=read();
	qsort(1,n);
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

当然求逆序对还有更加NB装逼的方法,你可以使用树状数组,甚至是线段树的方法进行求值,但是我现在还没复习到(唉,明明之前是会的,现在却…),就不献丑了,之后补坑.

---

update in 2023.02(已经补完线段树)

泪目了,没想到如今的我居然能够轻松的独立写出线段树代码了,并且已经完全懂了如何使用离散化的操作.想想当初高中OI时期即使学了线段树,打了不少题,还是十分懵懂的,线段树上的离散化则是完全不理解. 想了这么多,泪不禁要流了下来.

对于一个位置$j$来说,他如果能与之前的位置$i$形成逆序对,意味着$a[i]>a[j]$,那么逆序对的个数实际上就是$j$之前所有大于$a[j]$的$a[i]$的个数,对于这个我们可以直接使用线段树进行解决.

我们可以使用线段树维护目前位置$a[i]$出现的次数.类似于桶的方法,每当$a[i]$出现一次,就将$a[i]$位置的值+1,然后对于我们的$j$来说,我们只要用线段树来查询大于$a[j]$所有位置的和即可.因为对于$a[j]$来说,目前线段树中维护的所有值肯定都是在$a[j]$之前出现过的.那么只要是大于$a[j]$的肯定就是我们的逆序对了

对于此题来说,我们发现$l,r$在$int$范围内,但是我们无法直接使用线段树来维护这么大的区间,所以我们需要进行离散化操作.对于离散化操作,网上对此有大量的博客,篇幅都较长,也不乏有非常详细的,所以此处就不在赘述了

下面是具体的代码部分:

#include 
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls rt<<1
#define rs rt<<1|1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 1000000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Segment_tree{
	int l,r,sum;
}tree[maxn*4];
int n;int a[maxn];
void pushup(int rt) {
	tree[rt].sum=tree[ls].sum+tree[rs].sum;
}
void build(int l,int r,int rt) {
	tree[rt].l=l;tree[rt].r=r;
	if(l==r) return ;
	int mid=(l+r)>>1;
	build(lson);build(rson);
	pushup(rt);
}
void update(int pos,int rt,int v) {
	if(tree[rt].l==pos&&tree[rt].r==pos) {
		tree[rt].sum+=v;
		return ;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(pos<=mid) update(pos,ls,v);
	else update(pos,rs,v);
	pushup(rt);
}
int query(int l,int r,int rt) {
	if(tree[rt].l==l&&tree[rt].r==r) {
		return tree[rt].sum;
	}
	int mid=(tree[rt].l+tree[rt].r)>>1;
	if(r<=mid) return query(l,r,ls);
	else if(l>mid) return query(l,r,rs);
	else return query(l,mid,ls)+query(mid+1,r,rs);
}
vector<int>v;
signed main() {
	n=read();
	for(int i=1;i<=n;i++) {
		a[i]=read();
		v.push_back(a[i]);
	}
	//进行离散化操作
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	int Size=v.size();
	build(1,Size+10,1);//加10是为了操作过程中产生越界的情况,这个10可以是任意数字
	int ans=0;
	for(int i=1;i<=n;i++) {
		int x=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
		ans+=query(x+1,Size+10,1);
		update(x,1,1);
	}
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73