树状数组求逆序对

说在前面

我原本只知道求逆序对可以用归并排序,但是现在在做一道DP的题目的时候,需要通过求逆序对来优化,然后就意外的知道了树状数组求逆序对的方法……

其实,其实这篇博客本来应该合并在最开始写的树状数组里面的,但是懒得找了,直接开一篇新的吧,这样比较方便。

其实逆序对是可以用归并排序来写的,复杂度和树状数组是一样的都是O(NlogN),但是树状数组要好写一些,常数也比较的小……

然后就是这几天一直在刷NOIP的题目,超级爽……

树状数组求逆序对

树状数组:

首先我要重复一些树状数组的思路,因为我在写树状数组求逆序对的时候,一直想不通为什么,emmmmm其实是忘掉了树状数组是单点修改,区间查询的条件,以为是区间修改,区间查询。然后就死活都理解不了为什么这样可以求出来逆序对。

树状数组的本质上是单点修改,区间查询。一定要记得这一点。然后树状数组的c[i]保存的是它所属的下属元素的累加和,每次查询区间的时候都是从1到x这个区间里面的所有元素的和。每次在更新的时候也是不断的将控制它的c[i]也更新一下。emmmmm仔细想想其实是很简单的。

策略:

  • 其实策略是比较简单的,我们遍历这个数组,将a[i]这个点修改到树状数组里面+1,然后查询a[i]+1到n的和,ans加上这个和即可。最后这个ans就是逆序对的个数。
  • 其实这个就是通过树状数组把原本O(n)的查询时间改成了O(logn),所以和归并排序是一样的。

线段树需要注意的地方

  • 这个说一下线段树,线段树每次开始的Left,Right,Root的值是固定的,都是1,Maxx,1。控制查询和修改的范围是通过修改全局变量x和y来实现的。

P1438火柴排队

题目描述:

涵涵有两盒火柴,每盒装有 n 根火柴,每根火柴都有一个高度。 现在将每盒中的火柴各自排成一列, 同一列火柴的高度互不相同, 两列火柴之间的距离定义为: ∑(ai-bi)^2

其中 ai 表示第一列火柴中第 i 个火柴的高度,bi 表示第二列火柴中第 i 个火柴的高度。

每列火柴中相邻两根火柴的位置都可以交换,请你通过交换使得两列火柴之间的距离最小。请问得到这个最小的距离,最少需要交换多少次?如果这个数字太大,请输出这个最小交换次数对 99,999,997 取模的结果。

输入:

  • 第一行包含一个整数 n,表示每盒中火柴的数目。

  • 第二行有 n 个整数,每两个整数之间用一个空格隔开,表示第一列火柴的高度。

  • 第三行有 n 个整数,每两个整数之间用一个空格隔开,表示第二列火柴的高度。

输出:

输出共一行,包含一个整数,表示最少交换次数对 99,999,997 取模的结果。

题解:

  • 这个,我们可以通过贪心的思路来将两个数组排个序,用结构体记录下来原来的位置。然后把两个数组原来的位置绑定起来。F[a[i].ID]=F[b[i].ID],这样我们就把求交换次数转换成了求逆序对个数。
  • 然后用上面的树状数组求逆序对来解出来逆序对的个数,注意Mod就行了。

代码:

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
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cctype>
#include<cstdio>
using namespace std;
#define Mod 99999997
struct Number
{
long long Num;
long long ID;
}a[400000],b[400000];
long long n,sit[400000],c[400000];
long long ans,cnt;
long long Lowbit(long long x)
{ return -x&x;}
bool mycmp(Number x,Number y)
{ return x.Num<y.Num; }
inline long long Read()
{
long long F=true;
long long This=false;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') F=-1;
ch=getchar();
}
while(isdigit(ch))
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This*F;
}
void Add(long long x)
{
while(x<=n)
{
c[x]++;
x+=Lowbit(x);
}
}
long long Find(long long x)
{
long long Sum=false;
while(x>false)
{
Sum+=c[x];
x-=Lowbit(x);
}
return Sum;
}
int main()
{
n=Read();
for(long long i=1;i<=n;i++)
{
a[i].Num=Read();
a[i].ID=i;
}
for(long long i=1;i<=n;i++)
{
b[i].Num=Read();
b[i].ID=i;
}
sort(a+1,a+n+1,mycmp);
sort(b+1,b+n+1,mycmp);
for(int i=1;i<=n;i++)
sit[a[i].ID]=b[i].ID;
for(int i=1;i<=n;i++)
{
Add(sit[i]);
ans=(ans+i-Find(sit[i]))%Mod;
}
cout<<ans<<endl;
return 0;
}