【树状数组】洛谷 P1966 火柴排队
2021-03-15 17:55:00 # ACM

题链

若要将一个排列转换成另一个排列，一次只能交换相邻两个元素，例如将 $a =$ {$4$, $3$, $1$, $2$} 变成 $b =$ {$1$, $3$, $2$, $4$}，最少需要交换 $a$或$b$ 几步；

新建 $pa[a[i]] = i$ 记录排名$a[i]$的位置，$pb[b[i]] = i$ 记录排名$b[i]$的位置，令$p[pa[i]] = pb[i]$（相当于映射）得到的$p$序列求逆序数则为答案；

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
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//#pragma GCC optimize("O2")
using namespace std;
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ls rt<<1
#define rs rt<<1|1
#define one first
#define two second
#define MS 1000009
#define INF 1e18
#define mod 99999997
#define Pi acos(-1.0)
#define Pair pair<LL,LL>
#define eps 1e-9

LL n,m,k;
LL a[MS],aa[MS],pa[MS];
LL b[MS],bb[MS],pb[MS];
LL p[MS];
LL tr[MS];

LL lowbit(LL x){
	return x&(-x);
}

void add(LL pos,LL val){
	for(;pos<=n;pos+=lowbit(pos)){
		tr[pos] += val;
		tr[pos] %= mod;
	} 
} 

LL get_sum(LL pos){
	LL ans = 0;
	for(;pos;pos-=lowbit(pos)){
		ans += tr[pos];
		ans %= mod; 
	} 
	return ans;
}

int main(){
	//ios::sync_with_stdio(false);
	cin >> n;
	
	for(int i=1;i<=n;i++){
		cin >> a[i];
		aa[i] = a[i];
	}
	for(int i=1;i<=n;i++){
		cin >> b[i];
		bb[i] = b[i];
	}
	sort(aa+1,aa+n+1);
	sort(bb+1,bb+n+1);
	for(int i=1;i<=n;i++){
		a[i] = lower_bound(aa+1,aa+n+1,a[i]) - aa;
		pa[a[i]] = i;
		b[i] = lower_bound(bb+1,bb+n+1,b[i]) - bb;
		pb[b[i]] = i;
	}
	
	for(int i=1;i<=n;i++){
		p[pa[i]] = pb[i];
	}
	LL ans = 0;
	for(int i=1;i<=n;i++){
		add(n-p[i]+1,1);
		ans += get_sum(n-p[i]);
		ans %= mod;
	}
	cout << ans << endl;
	
	

	return 0;
}

Prev
2021-03-15 17:55:00 # ACM
Next