基础算法

方法：上课理解思想——>背模板——>做模板题（多敲几遍以增加熟练度）

快速排序

分治
1. 确定分界点
2. 调整区间（左<=x ，右>=x）
3. 递归处理左右两段

归并排序

1. 确定分界点 mid=(l+r)/2
2. 递归排序 left right
3. 归并——合二为一

双指针算法

先暴力，再找性质（i j 单调关系）优化，复杂度n^2变n

for (int i = 0, j = 0; i < n; i ++ )
{
    while (j < i && check(i, j)) j ++ ;

    // 具体问题的逻辑
}
常见问题分类：
    (1) 对于一个序列，用两个指针维护一段区间
    (2) 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作

位运算

1. n的2进制表示中第k位是几
2. n>>k （所求移到最后一位）
3. 看个位数 n&1
4. lowbit(x)：返回x的最后一位1（带上后缀0
5. x&-x
6. 原理：x&(~x+1)负数补码
7. 应用：统计1的个数，树状数组

离散化

特殊哈希
数据大且离散——>映射
==Points==
- 去重 sort+unique
- 二分求离散化的值
整数，保序

vector<int>alls;
sort(alls.begin(),alls.end());
alls.erase(unique(alls.begin(),alls,end()),end());//把多余的去掉

//二分找x对应的离散化的值
int find(int 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
}

区间合并

把有交集的区间合并在一起
1. 按区间左端点排序
2. 扫描 列关系
- 包含 不变
- 后相交 扩ed
- 不相交 ans++，更新st

void merge(vector<PII>&segs){
    vector<PII>res;
    sort(segs.begin(),segs,end());

    int st=-0x7fffffff,ed=-0x7fffffff;
    for(auto seg:segs){
        if(ed<seg.first){
            if(st!=-0x7fffffff)
                res.push_back({st,ed});
                st=seg.first,ed=seg.second;
        }
        else
            ed=max(ed,seg.second);//扩ed
    }
    if(st!=-0x7fffffff)
        res.push_back({st,ed});//不相交
    segs=res;
}