【洛谷P1966】火柴排队【树状数组，离散化，思维】

分析

不要被那个平方和取模吓到！！

不管你平不平方，就相当于要让两个对应编号的差距最小。那用贪心的思想，只要大的对大的，小的对小的，也就是说我们只关注他们的排名。

哦？排名？就可以想到离散化。然后把一个数组映射到另一个数组上（反之亦可），将一个看成有序的，看看多少次能变成这样有序的就行。

举个栗子：

1 3 4 2
1 7 2 4
1
2

离散化后变成：

1 4 2 3
1 3 4 2
1
2

将上面那个看成有序，一一对应映射到一个数组 $f$ 上：

f[1]=1; f[2]=4; f[3]=2; f[4]=3;
1

然后就转化为了 $f$ 数组变成有序所需要的交换次数，这个问题就是逆序对的个数，实现起来就是树状数组啦。

上代码

#include
#include
#include
using namespace std;
typedef long long ll;

struct node
{
	int s,p;
}a[100010];
struct node2
{
	int s,p;
}b[100010];

const int mod=1e8-3;
ll n,c[500010],ans,f[500010];

int cmp(node l,node r) {return l.s<r.s;}
int cmp2(node2 l,node2 r) {return l.s<r.s;}

int lowbit(int x) {return x&(-x);}
void update(int x,int v)
{for(int i=x;i<=n;i+=lowbit(i)) c[i]+=v;}
int getsum(int x)
{
	ll s=0;
	for(int i=x;i;i-=lowbit(i)) s=(s+c[i])%mod; 
	return s%mod;
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i].s);
		a[i].p=i;
	}
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&b[i].s);
		b[i].p=i;
	}
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+n+1,cmp2);
	for(int i=1;i<=n;i++) f[a[i].p]=b[i].p;//互相映射，将一个看成有序 
	for(int i=1;i<=n;i++)
	{
		update(f[i],1);
		ans=(ans+i-getsum(f[i]))%mod;//无序变有序的交换次数 
	}
	cout<<ans%mod;
	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