双指针

利用某些性质，将暴力的 $O(n^2)$ 算法优化到到 $O(n)$ 。

如输出字符串中所有单词 “I love reading books.”

# include<iostream>
# include<cstring>
using namespace std;
int main(){
    string s;
    getline(cin,s);
    for(int i=0; i < s.size(); i ++){
        int j = i;
        while(j < s.size() && s[j] != ' ') j ++;
        // 具体题目的逻辑
        for(int k = i; k < j; k ++) cout<<s[k];
        cout<<endl;
        i = j;
    }
    return 0;
}

最长连续不重复子序列的长度

# include<iostream>
# include<cstring>
using namespace std;
const int N = 100010;
int a[N], s[N];//每个数出现的次数
int n;
int main(){
    cin >>n;
    for(int i=0; i<n;i++) cin>>a[i];
    
    int res = 0;
    for(int i=0, j=0; i < n; i ++){
        s[a[i]] ++;
        while(s[a[i]]>1){ // 计数最少为 1
            s[a[j]]--; 
            j++; // 过渡掉重复数
        } 
       res = max(res, i-j+1);
    }
    cout<<res<<endl;
}

问题，如何输出序列？

位运算

$x\&-x=x\&(~x+1)$ 取二进制的最后一位 $1$

更多位运算知识参考另一篇文章：https://librariestoner.com/archives/wei-yun-suan

离散化

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> pii;
const int N = 300010;
int a[N], s[N];
vector<int> axis; //所有待离散化的坐标点x
vector<pii> add, query;

int find(int x) { // 相当于找 x 在数组 axis 中的位置
    int l = 0, r = axis.size() - 1;
    while(l < r) {
        int mid = l + r >> 1;
        if(axis[mid] >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1; // 数组下标从 1 开始
}

int main() {
    int n, m; cin >> n >> m;
    while(n --){
        int x, c; cin >> x >> c;
        add.push_back({x,c});
        axis.push_back(x);
    }
    
    while(m --){
        int l, r; cin >> l >> r;
        query.push_back({l, r});
        axis.push_back(l);
        axis.push_back(r);
    }
    
    // 坐标去重
    sort(axis.begin(), axis.end());
    axis.erase(unique(axis.begin(), axis.end()), axis.end());
    
    for(auto item: add) {
        int index = find(item.first);
        a[index] += item.second;
    }
    //预处理前缀和
    for(int i = 1; i <= axis.size(); i ++) s[i] = s[i-1] + a[i];
    //处理query
    for(auto q: query){
        int l = find(q.first), r = find(q.second);
        cout << s[r] - s[l-1] << endl;
    }
}

区间合并

• 按区间左端点排序
• 扫描合并

# include<iostream>
# include<vector>
# include<algorithm>
using namespace std;

typedef pair<int,int> PII;
vector<PII> segs;

void merge(vector<PII>&segs){
    vector<PII> res;
    sort(segs.begin(),segs.end());
    int l = -2e9,r = -2e9;
    for(auto item:segs){
        if(r < item.first){
            if(l != -2e9) res.push_back({l,r});//if(r!=-2e9)也可，是判定是否为正常区间，仅在第一个区间加入时起作用
            l = item.first;
            r = item.second;
        }
        else r = max(r,item.second);//区间有交集,但不是包含关系
	}
    if(l != -2e9) res.push_back({l,r});
    segs = res;
}
int main(){
    int n;
    cin >> n;

    while(n--){
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge(segs);
    cout << segs.size() << endl;
    return 0;
}

Q.E.D.