说在前面

我原本只知道求逆序对可以用归并排序，但是现在在做一道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;
}