算法基础课笔记（五）

1.7.2归并.acwing.788. 逆序对的数量（模板题）

本题在蓝桥杯系列（十七）中有讲解。

给定一个长度为 n 的整数数列，请你计算数列中的逆序对的数量。

逆序对的定义如下：对于数列的第 i 个和第 j 个元素，如果满足 i<j 且 a[i]>a[j]，则其为一个逆序对；否则不是。

输入格式
第一行包含整数 n，表示数列的长度。
第二行包含 n 个整数，表示整个数列。

输出格式
输出一个整数，表示逆序对的个数。

数据范围
1≤n≤100000
输入样例：
6
2 3 4 5 6 1
输出样例：
5

将逆序对分成三类：

1.两个元素都在左边；2.两个元素都在右边；3.两个元素一个在左一个在右；

然后计算逆序对的数量（序列）：

1. 递归算左边的；
2. 递归算右边的；
3. 算一个左一个右的；
4. 把他们加到到一起。

递归是为了把前2种情况转化为第3种情况，变成一边一个来计算逆序对数量。

对于划分的两个区间L和R，先考虑R中的每个数，在L中有多少个数比它大，这样就能不重不漏计算出所有逆序对数量。区间合并（数的交换）过程并不会影响逆序对数量，所以可以边归并边计算。

• 归并排序合并过程中计算逆序对数量
• 若 a[i] > a[j]，则a[i] 和它后面的元素都大于 a[j]，a[i] 构成逆序对数量：res += mid - i + 1;

// 注意：当倒序时逆序对数量最多，等于n/2*(n-1)，约为5*10^9，int范围约为2*10^9，用long long
#include <cstdio>
typedef long long LL;
using namespace std;

const int N = 100010;
int q[N],tmp[N];
int n;

LL merge_sort(int l,int r){
    if (l >= r) return 0;
    int mid = l+r>>1;
    LL res = merge_sort(l,mid) + merge_sort(mid+1,r);
    
    int i = l,j = mid+1,k = 0;
    while (i <= mid && j <= r){
        if (q[i] <= q[j]) tmp[k++] = q[i++];
        else{
            tmp[k++] = q[j++];
            res += mid - i + 1;// 计算逆序对数量
        }
    }
    // 扫尾
    while (i <= mid) tmp[k++] = q[i++];
    while (j <= r) tmp[k++] = q[j++];
    // 物归原主
    for(int i = l,j = 0;i <= r;i++,j++) q[i] = tmp[j];
    return res;
}

int main(){
    scanf("%d",&n);
    
    for (int i = 0;i < n;i++) scanf("%d",&q[i]);
    
    printf("%lld\n",merge_sort(0,n-1));
    return 0;
}

1.8：双指针算法

双指针算法一般分为两类：
1.对撞指针 ：两个指针分别指向不同的队列（归并）
2.快慢指针 ： 两个指针指向一个队列（快排）

利用双指针算法可以将时间复杂度由平方级降低到线性级，也就是优化二重循环的朴素做法。

双指针算法 —— 模板题 AcWIng 799. 最长连续不重复子序列, AcWing 800. 数组元素的目标和

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;
    // 具体问题的逻辑
}

双指针的经典应用例子，将带空格的句子中每个单词逐行输出。（2单词间只有1个空格）

#include <cstdio>
#include <cstring>
using namespace std;

int main(){
    char c[100];
    fgets(c,100,stdin);
    
    int n = strlen(c);
    
    for (int i = 0;i < n;i++){
        int j = i;
        while (j < n && c[j] != ' ') j++;
        
        for (int k = i;k < j;k++) printf("%c",c[k]);
        puts("");
        /* 这道题的具体逻辑：第一次 i指向第一个单词的首字母，
		  j结束时指向第一个空格，输出第一个单词并换行，令 i=j，i指向第一个空格 
		 下一次最外层的循环中，i++，i指向第二个单词的首字母，同上操作 */
        i = j;// 外层循环中有i++，在双指针算法中特别注意！
    }
    return 0;
}
/*Hello world This is c
Hello
world
This
is
c*/

例题：799. 最长连续不重复子序列（模板题）

给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。

输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。

输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。

数据范围
1≤n≤10^5
输入样例：
5
1 2 2 3 5
输出样例：
3

首先，我们想一下朴素做法怎么解决，再去考虑双指针算法来优化就比较好想。

朴素做法： 假设 i 是终点，j 是起点，先枚举终点 i，再枚举起点 j。

// 朴素做法： O(n^2)
for (int i = 0;i < n;i++)
   for (int j = 0;j <= i;j++){
      if (check(j,i)){
        res = max(res,i-j+1);
   }
}

本质： j 尽可能与 i 的距离变大，并保证没有重复数字。

双指针优化：朴素做法的指针j每次都从0开始，没有必要。

当 i 向右移动时，j 指针不会回退，只能不动或者向右移动 (如果 j 需要向右移动，则表示表示出现重复数字了，此时只需要把 j 向右移动，直到 i 和 j 之前没有重复数字为止)。即：保持一定的单调性。

// 双指针算法： O(n)
for (int i = 0,j = 0;i < n;i++)
    while (j <= i && check(j,i)) j++;
	res = max(res,i-j+1);

关于快慢指针的解释：（针对模板）

两个指针一前一后从左往右走，不会往回走，时间复杂度为：O(2*n)==O(n)。直到不满足check性质或走到头才退出while循环，此时就找到了所求的区间。有点滑动窗口的意思。

本题中所用到的check性质应该就是a[i]重复出现。

双指针[j, i]维护的是以a[i]结尾的最长连续不重复子序列。

其实，双指针优化过程就是寻找单调性。

单调性含义：随i的增加，j一直延一个方向变化，就是单调性。比如，随i的增加，j也一直增加，这叫单调递增，如随i的增加，j一直减小，这叫单调递减，总之随i的增加，j一会增，一会减就没有单调性了。

拿本题举例，单调性：设[j,i]是目前的“最长不重复”，当i+1时，j不变或者增加。因为i增加后，如j减小了，那么组成[j-1,i+1]的新区间如果是“最长不重复”，那么上一个区间[j,i]属于[j-1,i+1],因此[j,i]就不是最长不重复，这和我们的设定有矛盾，故i增，j必增。

参考题解1：https://www.acwing.com/solution/content/6460/。

参考题解2：https://www.acwing.com/solution/content/13491/。

参考题解3：https://www.acwing.com/blog/content/4176/。

y总代码。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+5;
int n;
int a[N],s[N];// s是标记数组

int main(){
    scanf("%d",&n);
    int res = 0;
    
    for (int i = 0,j = 0;i < n;i++){
        scanf("%d",&a[i]);
        s[a[i]]++;
        
        while (s[a[i]] > 1){
            -- s[a[j++]];// 先减次数后右移指针j
        }
        res = max(res,i-j+1);// [j,i]是选择的连续不重复子序列
    }
    printf("%d",res);
    return 0;
}

时间复杂度：使用双指针的题目一般都是O(n)。

空间复杂度：标记数组占内存比较大，数组长度为数据范围上界，其实完全可以用哈希表代替，这样优化后额外的空间复杂度就是O(n)。标记数组就是空间换时间。