企业网站的功能/常用seo站长工具

逆序对
逆序对
逆序对的概念
对于给定的一段正整数序列，逆序对就是序列中 ai>aj 且 i<j 的有序对。
例如：
1 2 3
这个整数数列的逆序对个数是0，而
2 1 3
这个整数数列的逆序对个数是1，因为(2, 1)是一对逆序对；
再比如：
3 2 1
这个整数数列的逆序对个数是3，因为(3, 2)、(3, 1)、(2, 1)都是逆序对
信息学竞赛课堂
逆序对
归并排序求逆序对
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经
典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题
然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，
即分而治之)。
信息学竞赛课堂
逆序对
信息学竞赛课堂
逆序对
信息学竞赛课堂
逆序对
信息学竞赛课堂
逆序对
例题：瑞士轮
题目背景
在双人对决的竞技性比赛，如乒乓球、羽毛球、国际象棋中，最常见的赛制是淘汰赛和循环赛。前者
的特点是比赛场数少，每场都紧张刺激，但偶然性较高。后者的特点是较为公平，偶然性较低，但比
赛过程往往十分冗长。本题中介绍的瑞士轮赛制，因最早使用于1895年在瑞士举办的国际象棋比赛而
得名。它可以看作是淘汰赛与循环赛的折中，既保证了比赛的稳定性，又能使赛程不至于过长。
题目描述
2×N 名编号为 1-2N 的选手共进行R轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分
从高到低对选手进行一次排名。选手的总分为第一轮开始前的初始分数加上已参加过的所有比赛的得
分和。总分相同的，约定编号较小的选手排名靠前。
每轮比赛的对阵安排与该轮比赛开始前的排名有关：第1 名和第2 名、第 3 名和第 4名、……、第2K
- 1 名和第 2K名、…… 、第2N - 1 名和第2N名，各进行一场比赛。每场比赛胜者得1分，负者得0分
。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表
现。现给定每个选手的初始分数及其实力值，试计算在R轮比赛过后，排名第 Q 的选手编号是多少。
我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。
信息学竞赛课堂
信息学竞赛课堂
逆序对
输入输出格式
输入格式：
第一行是三个正整数N,R,Q,每两个数之间用一个空格隔开，表示有2×N名选手、R轮比赛，以及我们
关心的名次Q。第二行是2×N 个非负整数s_1, s_2, …, s_2N，每两个数之间用一个空格隔开，其中s_i
表示编号为i的选手的初始分数。 第三行是2×N 个正整数w_1 , w_2 , …, w_2N，每两个数之间用一个
空格隔开，其中 w_i表示编号为i的选手的实力值。。
输出格式：
一个整数，即R轮比赛结束后，排名第Q的选手的编号。
输入输出样例
输入样例1：
2 4 2
7 6 6 7
10 5 20 15
输出样例1：
1
说明
【数据范围】
对于30%的数据，1≤N≤100；
对于50%的数据，1≤N≤10,000；
对于100%的数据，1 ≤ N ≤ 100,000,1 ≤ R
≤ 50,1 ≤ Q ≤ 2N,0 ≤ s_1, s_2, …,
s_2N≤10^8,1 ≤w_1, w_2 , …, w_2N≤ 10^8
逆序对
树状数组求逆序对（小数据情况 倒序扫描）
之所以能够利用树状数组也可以求解逆序对，主要利用的还是树状数组最本质的
“单点修改”和“区间求和”这两个特性。在求解逆序对这个问题中，“单点修
改”其实就是在对应的位置“+1”
，“区间求和”其实就是求前缀和。
在数据值比较小的情况下，可以采用正序或倒序的扫描方法。
以下是倒序扫描的方法，核心代码如下：
for( int i=n; i>=1; i-- ) { //倒序扫描
ans+=getSum(a[i]-1);
    add(a[i]); //依次加入树状数组
}
注意：
要特别留意add函数里面的写法，里面的循环范围很可能不是n，而是a[i]能取到
的最大值。
信息学竞赛课堂
逆序对
树状数组求逆序对（小数据情况 正序扫描）
在数据值比较小的情况下，正序扫描也可以，核心代码如下：
for(int i=1; i<=n; i++) { //正序扫描
add(a[i]);
    ans+=(i-getSum(a[i])); //计算结果并累计
}
注意：
同样要特别留意add函数里面的写法，里面的循环范围很可能不是n，而是a[i]能
取到的最大值。
信息学竞赛课堂
逆序对
树状数组求逆序对（大数据情况 离散化+排序）
在数据范围很大的情况下，不能像前面的小数据情况那样直接扫描来求解，因为
我们开不了那么大的数组，所以这时候需要离散化。
但需要注意以下3点：
1、如果所给的数列中数据的值很大，需要进行离散化，因为我们关注的其实数
列中数值之间的相对大小关系，并不关心实际的数值大小。
2、需要对数列按照数据排序，记录每个数据在原数组中的位置，但插入到树状
数组中的并不是数列本身的数据，而是在数据对应的位置处加1。
3、特别要注意的是如果数列中有数值相同的数，在排序时需要处理，否则这些
数值虽然相同，但是排序后的位置肯定不同，而我们经过离散化后只会考察数据
的位置，所以可能会错误的将相同数值的数据也当成逆序对。
信息学竞赛课堂
逆序对
THANKS
信息学竞赛课堂