1. 双指针
没啥好说的，就两种类型，俩指针在一个序列上和俩指针在俩序列上
核心思想：运用某种性质把O(n2)的暴力双重循环优化成O(n)了
怎么做呢，写个暴力解先，然后看到模板的check函数没有，暴力解的话那个地方一般就是直接套了个循环，也就是说其实优化的是check函数，也就是先写暴力解然后找规律优化，比如根据单调性再结合别的方法把check优化为O(1)，O(logn)就比暴力快一点咯
简单案例：把一个字符串中每个单词分别输出（也就是把空格去掉）
输入为abc def ghi一个指针指着每个单词的首位然后另一个单词往后指就行了案例：找出最长连续不重复子列长度（一堆数字找出不含重复的最长的有多长）
这个如果数据小就可以check函数写成开一个新数组去记录每个数字出现多少次，当有个数字出现第二次的时候去再移动j和记录长度，这就优化成O(1)了整体就变成O(n)了哎呀没什么好讲的，要是忘了就自己悟吧，悟不出来就飞起来，说明题刷少了。
模板：
for (int i = 0, j = 0; i < n; i ++ )
{
while (j < i && check(i, j)) j ++ ;
// 具体问题的逻辑
}
常见问题分类：
(1) 对于一个序列，用两个指针维护一段区间，如快排的那部分处理
(2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作
2. 位运算
- & | ~ << >> 操作呗
- 常用的：看看数字x的二进制表示中第k位是多少？x>>k &1
- lowbit操作:
- 原理是：负数是原数的补码，补码是取反+1(-x=~x+1)导致会使原码和补码在低位第一个1及之前是一样的，后面就全相反了，所以使用 x&-x 就会得到最低位第一个1的值
- 可以用来统计x里面有多少个1，拿x一直减x&-x看看减了多少次就行了，哈哈了
int lowbit(int x)
{
return x&-x;
}
- 也不重要
3. 离散化
- 一堆有序的数，值域很大eg:0 ~ 109，但是数的数量不是很多比如105个，但是要用他的值做下标，开个109的数组就有点抽象了，怎么办捏，比如映射为1~n（开个数组用坐标的感觉）这个过程叫离散化，哈哈
但问题在于：
最开始给的一堆数里面可能有重复数，就得去重
还得想想如何快速算出离散化后的值是多少
模板什么意思捏，就是把一堆数里面你要用的数都放进一个数组，然后直接用了数组的下标就好了，这就是离散化
模板:
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 将所有值排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去掉重复元素
//这里unique是去重后把重复的都挑出来放到数组中不重复的后面，然后返回不重复的最后一个的下标
// 二分求出x对应的离散化的值
int find(int x) // 找到第一个大于等于x的位置
{
int l = 0, r = alls.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (alls[mid] >= x) r = mid;
else l = mid + 1;
}
return r + 1; // 映射到1, 2, ...n
}
4. 区间合并
- 俩区间有交集的话(端点相同也算)，就给他合并起来
- 实现：
①把所有区间按左端点排序
②维护一个区间直到没有交集，然后就维护刚刚没有交集的这个
模板：
// 将所有存在交集的区间合并
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;
}
