写在最前面：

此系列中的所有模板全为大佬所写，我只是一个搬运工（？）。

记录

双指针

双指针其实平常用到的很多（我之前用过也不知道叫双指针，，，大意了），也算是非常常用的一种算法。主要的作用是节省时间，把平常需要双循环的朴素算法（时间复杂度O(n^2））根据i和j之间的关系简化成双指针算法（时间复杂度O（n^2））,从而避免时间超限的后果。一般常见的双指针有两种，一种是两个指针分别指向两个数组，一种是两个指针指向同一个数组（这个更为常见）。

双指针的核心是找到双循环里面i和j的关系，所以可以先把题目用双循环写出，然后在简化为双指针的方法。

下面是模板：

#include <iostream>

using namespace std;
bool check(int i,int j)//由题意决定,这里就是随便写了一个方便编译
{
    if(i>j)
        return true;
    return false;
}
int main()
｛
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int j=0;//根据题意而定
        while(j<n&&check(i,j))//j的具体范围&&题目判断条件
            j++;
        //根据题意决定下面的具体内容
    }
    return 0;
}

位运算

大部分都是由简单的符号完成的。

下面是常见的运算符号：

"&" 与（11为1，其余为0）

"|" 或（00为0，其余为1）

"^" 异或（相同0不同1）

"~" 取反（0->1,1->0）

"<<"左移（二进制位左移，e.g n<<k表示n * 2^k）

">>"右移（二进制位右移，e.g n>>k表示n / 2^k）

题目如 n的二进制表示下第k为是几。

解题过程如下：

把第k位排到最后一位 n>>k（n不用化为二进制）
读取k x&1（与运算，11为1，10为0）

下面是该题目模板:

#include <iostream>
#include <cstdio>
using namespace std;
int lowbits(int x)
{
    return x&-x;
}
int main()//计算二进制数里面1的个数
{
    int n;
    int a;
    scanf("%d",&n);
    while(n--)
    {
        int num=0;
        scanf("%d",&a);
        while (a) a-=lowbits(a),num++;
        printf("%d ",num);
    }
    cout << endl;
    return 0;
}

离散化

题目如：先输入n个a b，把在数轴上a对应的位置+b（本来都为0），然后给定k个区间，算每个区间内的总和（这其实是离散化+前缀和）

离散化就是把很大范围但是很分散的数据用新的容器来统装起来，按照出现的顺序排序编号。

解决过程如下：

把原数组去重。
寻找x所对应的离散化后的位置。

下面是例题模板：

#include <iostream>
#include <vector>//相当于一个功能更多的数组
#include <algorithm>


using namespace std;
typedef pair<int,int> range; //pair对象可以存储两个值，这两个值可以是不同的数据类型。
const int N=1e5*3+10;
int n,m;
int a[N],s[N];

vector<int>alls;
vector<range>add,query;

int find1(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;
}

int main()
{
    cin>>n>>m;
    //读入数组
    for(int i=0; i<n; i++)
    {
        int x,c;
        cin>>x>>c;
        add.push_back({x,c});
        alls.push_back(x);
    }
    //读入所求区间
    for(int i=0; i<m; i++)
    {
        int l,r;
        cin>>l>>r;
        query.push_back({l,r});

        alls.push_back(l);
        alls.push_back(r);

    }
    //排序去重
    sort (alls.begin(),alls.end());
    alls.erase((unique(alls.begin(),alls.end())),alls.end());


    //处理插入
    for(auto item:add)//c++特性遍历，遍历整个add
    {
        int x=find1(item.first);//x离散化之后的值
        a[x]+=item.second;//在离散化之后的坐标上加上要加的数

    }

    //预处理前缀和
    for(int i=1; i<=alls.size(); i++) s[i]=s[i-1]+a[i];

    //处理询问
    for(auto item:query)
    {
        //item.first:左区间离散化之后的值。item.second:右区间离散化之后的值
        int l=find1(item.first),r=find1(item.second);
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}

（离散化折磨了我很久，，，蚌埠住了。）

区间合并

题目如：给你n个区间把它们有交集的合并，求最少区间数。

题目解决过程如下：（和贪心里面的区间覆盖类似）把区间按照左端点从小到大排序。比较当前区间右端点和下一个区间里左端点，如果当前区间右端点大，则可以把下一个区间放进来，同时该区间的右端点更新为两个区间右端点中较大的一方。否则，开下一个新区间，并以这里所指的下一个区间当做样例。进行递归求解。

下面是模板：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef  pair<int,int> PII;
vector<PII> segs;
int n;

void merge1(vector<PII> &segs)
{
    vector<PII> tmp;
    sort(segs.begin(),segs.end());//pair默认的按照左端点排序再按照右端点排序
    int st=-2e9,ed=-2e9;
    for(auto item:segs)//c++特有遍历
    {
        if(ed < item.first)//如果ed小于该区间最小值那么就开一个新区间
        {
            if(st!=-2e9) tmp.push_back({st,ed});//避免把最初的区间录入进去
            st = item.first;
            ed = item.second;
        }
        else ed=max(ed,item.second);
    }
    if(st!=-2e9) tmp.push_back({st,ed});

    segs=tmp;
}

int main()
{
    cin>>n;
    for(int i=0; i<n; i++)
    {
        int l,r;
        cin>>l>>r;
        segs.push_back({l,r});
    }
    merge1(segs);
    cout << segs.size() << endl;
    return 0;
}

over.

【算法】双指针、位运算、离散化、区间合并

写在最前面：

记录

双指针

位运算

下面是常见的运算符号：

离散化

区间合并