Halo，这里是Ppeua。平时主要更新C语言，C++，数据结构算法......感兴趣就关注我吧！你定不会失望。
🌈个人主页：主页链接
🌈算法专栏：专栏链接
我会一直往里填充内容哒。
🌈LeetCode专栏：专栏链接
目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目，也会当天做完发出
🌈代码仓库：Gitee链接
🌈点击关注=收获更多优质内容🌈
用一篇Blog来讲解下最近学到的双指针、位运算、离散化、区间合并等算法，为日后的刷题打下坚实的基础。
双指针：
双指针，顾名思义就是两个指针。
在解题当中，往往分为两种情况：指向两个不同的序列，指向一个序列。
其核心思想是由暴力算法优化而来，通常暴力算法的时间复杂度为O(n^2)，这样解题的过程中显然无法凸显出算法之美（doge
基于此，我们优化了一下解题方式，其核心思想就是有：两个指针i,j当符合某种条件的时候j++，两个指针都不会走已经走过的路
如何理解呢？下面我们来看一个例子
寻找不重复最长区间，就是一个区间里的数字出现次数<=1
之后返回最优解即可：本题就是每当j移动时就更新下区间
代码模板:
#include<iostream> using namespace std; const int N=100010; int n=0,ans=0; int a[N],s[N]; void in() { cin>>n; for(int i=0;i<n;i++)cin>>a[i]; return; } int main() { in(); for(int i=0,j=0;j<n;j++) { s[a[j]]++; while(s[a[j]]>1) { s[a[i]]--; i++; } ans=max(ans,j-i+1); } cout<<ans; }
Leetcode相关题目推荐：
至此双指针算法结束.
位运算:
这里先简单介绍一下数据的存储格式，在x86也就是32位的环境下数据是以32个1或0存储在计算机当中的。
抽象来看一个int类型的数据，就可以存储32种情况（有代表1，无代表0）
通常情况下，我们可以利用位运算来存储某几种情况是否出现，若不用位运算，我们就另外需要开辟几个空间来存储这几种情况的bool值。
所以n>>k&1就可以很好的解释上面的算法。
n向右位移k位（这里的k为4），之后与1的二进制位进行&的比较，若有1则输出1.
比较常用的还有一种算法 lowbit(x)
作用是输出一个数二进制位中的最后一个1，通常是用来统计一个数二进制中有几个1等问题。
代码就简单的一行，我们来一起看看他的原理是怎样的。
先来理解一个概念对一个数取相反数 得到的是这个数的补码。（不看符号位）
然后执行&运算，他就会输出最后一位1所代表的十进制。
代码模板:
int lowbit(x){ return x&-x; }
至此位运算结束.
区间合并:
这个算法比较少用，其大意是将所有有重合的区间进行合并。
首先我们先将所有端点的头位置（st）进行排序，将尾位置（ed）作为比较依据
所以就有以下这三种情况
第一种情况是ed1<ed的情况 也就是这整个区间被包含在比较区间当中，所以我们做的是保留原区间进行下一个比较。
第二种情况是ed2>ed的情况 也就是比较区间被包含在了其中，所以我们要将比较区间尾端更新，进行下一个比较。
第三种情况是st3>ed 因为我们已经将所有端头进行排序，所以出现这种情况只能说明上一个模板已经排完序了，这时候我们更新比较区间就可以了。
代码模板:
#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 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);//max只能放两个数据类型相同的值 } if(st!=-2e9)res.push_back({st,ed});//放最后一个区间 segs=res; } int main() { int n=0; cin>>n; for(int i=0;i<n;i++) { int l,r; cin>>l>>r; segs.push_back({l,r}); } merge(segs); cout<<segs.size(); }
至此区间合并算法结束.
离散化:
离散化先来介绍下是用来干什么的：他是用来解决跨度（10^9）很大，但非常稀疏的数据(10^5)，若用数组来存储，则会很浪费空间。
举个例子：
图中的key相当于数组下标，而value则是对应的值。我们想要在key为1 10000 5000000的三个地方加上值1，因为数组的空间是连续的，所以这样会造成非常大的空间浪费。
所以为了避免这种浪费，想到了数学中离散化的方法。
首先先来考虑几个问题：
1、key可能会有重复如何去重？（若不去重则会出现相同的下标）
2、如何算出a[i]离散化后的值呢？
先来解决第一个问题：去重
先来认识两个函数，erase与unique。
erase是vector的方法，目的是去除连续的区间
unique是去除指定区间内连续相同数据的函数（从名字也可以来理解 unique唯一的），并返回去除后的尾坐标。
下面我们先对容器进行预处理
sort(alss.begin(),alss.end()); alss.erase(unique(alss.begin(),alss.end()),alss.end());//去除重复下标
至于第二个问题我们暂且按下不表。
拿acwing上的一道例题来举例：
分析题目可以得到，我们要做的有两件事，第一 在x的位置上加上常数c，第二访问l，r区间和，看其数据描述，很符合我们上方提到的离散化模型，接下来我们就开始试一试。
先定义变量，其中alss用来存储下标，而add用来将存储的下标与相加的数进行绑定，query用来存储查找的区间。
const int N=300010; typedef pair<int, int>PII; int n,m; int a[N],s[N];//a为离散数组 s为前缀和 vector<int>alss;//原始数组数组 vector<PII>add,query;
接下来进行数据读入。
cin>>n>>m; for(int i=0;i<n;i++) { int x,c; cin>>x>>c; add.push_back({x,c});//将对应坐标与要加的值放在一起之后访问 alss.push_back(x);//将要访问的下标存入hash }
接下来读入要访问的区间，这里区间也等于是两个坐标，为了之后方便求和，我们也将他放入alss坐标集中
for(int i=0;i<m;i++) { int l,r; cin>>l>>r; query.push_back({l,r});//将访问下标存入pair alss.push_back(l);//将访问下标也映射到hash中 alss.push_back(r); }
接下来就是上文提到的去重等问题这里不过多赘述
sort(alss.begin(),alss.end()); alss.erase(unique(alss.begin(),alss.end()),alss.end());//去除重复下标
接下来就是将add中要加的坐标x与要加的数r进行加减。
首先先访问一下要加的坐标是哪个。
这里解答刚刚还剩下的问题，用二分查找去寻找在alss中x放在了哪里，之后返回alss中hash过的坐标，放入a中，最后在a中进行操作。
for(auto item:add) { int x=find(item.first);//为什么不直接将已经排完序的vector下标各加一作为hash值？ a[x]+=item.second;//因为这样不知道你要访问的值是哪个 也就是说 在alss中 下标是作为value的存在而你要用的是把这个value做成key key对应的value才是你要操作的空间 }//总的来说就是节省了时间 也可以一个for去找用的那个值 然后返回其下标但这样无疑慢了很多
二分查找函数
int find(int x) { int l=0,r=alss.size()-1; while(l<r) { int mid=l+r>>1; if(alss[mid]>=x)r=mid; else l=mid+1; } return r+1;//整体向前偏移1 }
最后就是求前缀和，同样要访问的l，r坐标还是通过二分查找去寻找，前缀和前几篇blog已经讲过，不懂的朋友再去看看吧，这里就不再赘述
for(int i=1;i<=alss.size();i++)s[i]=s[i-1]+a[i];//求前缀和 for(auto item:query) { int l=find(item.first),r=find(item.second); cout<<s[r]-s[l-1]<<endl; }
代码模板:
#include<iostream> #include <utility> #include<algorithm> #include<vector> using namespace std; const int N=300010; typedef pair<int, int>PII; int n,m; int a[N],s[N];//a为离散数组 s为前缀和 vector<int>alss;//原始数组数组 vector<PII>add,query; int find(int x) { int l=0,r=alss.size()-1; while(l<r) { int mid=l+r>>1; if(alss[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});//将对应坐标与要加的值放在一起之后访问 alss.push_back(x);//将要访问的下标存入hash } for(int i=0;i<m;i++) { int l,r; cin>>l>>r; query.push_back({l,r});//将访问下标存入pair alss.push_back(l);//将访问下标也映射到hash中 alss.push_back(r); } sort(alss.begin(),alss.end()); alss.erase(unique(alss.begin(),alss.end()),alss.end());//去除重复下标 for(auto item:add) { int x=find(item.first);//为什么不直接将已经排完序的vector下标各加一作为hash值？ a[x]+=item.second;//因为这样不知道你要访问的值是哪个 也就是说 在alss中 下标是作为value的存在而你要用的是把这个value做成key key对应的value才是你要操作的空间 }//总的来说就是节省了时间 也可以一个for去找用的那个值 然后返回其下标但这样无疑慢了很多 for(int i=1;i<=alss.size();i++)s[i]=s[i-1]+a[i];//求前缀和 for(auto item:query) { int l=find(item.first),r=find(item.second); cout<<s[r]-s[l-1]<<endl; } return 0; }
至此离散化算法结束.
完结撒花：
🌈本篇博客的内容【双指针、位运算、离散化、区间合并思路讲解及代码实现】已经结束。
🌈若对你有些许帮助，可以点赞、关注、评论支持下博主，你的支持将是我前进路上最大的动力。
🌈若以上内容有任何问题，欢迎在评论区指出。若对以上内容有任何不解，都可私信评论询问。
🌈诸君，山顶见！
