本节主要学习双指针、位运算、离散化、区间合并等知识。

双指针算法

常见类型：指向两个不同序列 或者 指向同一个系列的不同位置。

通用模版

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

核心思想：将下面的朴素算法优化到 $O(n)$ 。

for(int i = 0; i < n; i++){
    for (int j = 0; j < n; j ++){

    }
}

举例：一串字符串里面单词用空格分隔，用双指针把每个单词都弄出来。

举例2：给定整数序列，求最长无重复数字的连续子序列长度。

做法：用指针i枚举右端点，指针j维护最远左端点，用哈希表记录区间内每个元素的出现次数，总共循环次数2n，时间复杂度降低到了 $O(n)$ 。

for (int i = 0, j = 0; i < n; i++){
    while(j < i && check(i,j)){
        pop(arr[j]);
        j++;
    }
    res = max(res,i-j+1);
}

常用位运算

1. 求n的二进制表示中第k位是几（记个位是0位）

   n >> k & 1

作用：输出n的二进制表示。

2. 返回x的最后一位1，如101000->1000

   x & -x = x & (~x + 1)

作用：求n的二进制表达中的1的个数。

离散化

整数、有序的离散化。比如一个数组值域为$(0,10^9)$，个数为$10^5$。此时如果想把数组值转化为下标使用，此时需要进行映射，这个过程称作离散化。

离散化可能用两个问题：1. a[]中可能有重复元素，需要去重；2.如何算出a[i]离散化后的值是多少。

解决办法：

先把所有值用sort排序，再用arr.erase(unique(arr.begin(),arr.end()),arr.end())去除重复元素，再使用二分查找查出来对应的值。

//手动实现unique函数
vector<int>::iterator unique(vector<int> &a){
    int j = 0;
    for(int i = 0; i < a.size(); i ++){
        if(!i || a[i] != a[i-1]) a[j++] = a[i];
    }
    return a.bigin() + j;
}

区间合并

给定n个区间 $[l_i, r_i]$ ，要求合并所有有交集的区间。

步骤：

1. 按区间左端点排序。
2. 按左端点从小到大顺序遍历，记录一个当前的区间，扫描接下来的区间是否与当前区间有交集，若有交集则合并在一起并继续扫描，如果没有交集就把当前区间更新为这个区间。

void merge(vector<PII> &segs){
    vector<PII> res;
    sort(segs.begin(), segs.end());
    int st = -2e9, ed = -2e9;
    for(auto seg: segs){
        if(ed < seg.first){
            if (st != -2e9) res.push_back({st,ed});
            st = seg.first, ed = seg.second;
        }
        else ed = max(ed,seg.second);
    }
    if(st != -2e9) res.push_back({st,ed});
    segs = res;
}